图（Graph）是表示物件与物件之间的关係的数学对象，是图论的基本研究对象。一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。
对于一个拥有n个顶点的无向连通图，它的边数一定多于n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这 n-1条边（弧）组成的图被称为原无向图的生成树。
基本介绍
- 中文名：图
- 外文名：Graph
- 学科：数学
- 分类：有/无向图等
定义
主要有以下两种定义。
二元组的定义
图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与V不相交。它们亦可写成V(G)和E(G)。
E的元素都是二元组，用(x,y)表示，其中x,y∈V。
三元组的定义
图G是指一个三元组(V,E,I)，其中V称为顶集，E称为边集，E与V不相交；I称为关联函式，I将E中的每一个元素映射到
。如果e被映射到(u,v)，那幺称边e连线顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u相邻。
分类
有/无向图
如果给图的每条边规定一个方向，那幺得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。
单图
一个图如果任意两顶点之间只有一条边（在有向图中为两顶点之间每个方向只有一条边）；边集中不含环，则称为单图。
基本术语
阶（Order）：图G中点集V的大小称作图G的阶。
子图（Sub-Graph）：当图G'=(V',E')其中V‘包含于V，E’包含于E，则G'称作图G=(V,E)的子图。每个图都是本身的子图。
生成子图（Spanning Sub-Graph）：指满足条件V(G') = V(G)的G的子图G'。
导出子图（Induced Subgraph）：以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图；以图G的边集E的非空子集E1为边集，以E1中边关联的顶点的全体为顶点集的G的子图，称为E1导出的导出子图。
度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。
入度（In-degree）和出度（Out-degree）：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数；出度则是相对的概念，指以该顶点为起点的边数。
自环（Loop）：若一条边的两个顶点为同一顶点，则此边称作自环。
路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。
行迹（Trace）：如果路径P(u,v)中的边各不相同，则该路径称为u到v的一条行迹。
轨道（Track）：如果路径P(u,v)中的顶点各不相同，则该路径称为u到v的一条轨道。
闭的行迹称作迴路（Circuit），闭的轨称作圈（Cycle）。
（另一种定义是：walk对应上述的path，path对应上述的track。Trail对应trace。）
桥（Bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。
图的存储表示
数组（邻接矩阵）存储表示（有向或无向）
邻接表存储表示
有向图的十字鍊表存储表示
无向图的邻接多重表存储表示
一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单鍊表（并按建立的次序编号），第i个单鍊表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单鍊表中结点的个数即为该顶点的出度(与该顶点连线的边的总数)。无论是存储图或网，都需要在每个单鍊表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向鍊表中第一个结点。
在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。
在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi,vj>，它表示从顶点vi到顶点vj有一条边。
若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和<vj,vi>两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧，我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。
路径长度是指路径上边或弧的数目。
若第一个顶点和最后一个顶点相同，则这条路径是一条迴路。
若路径中顶点没有重複出现，则称这条路径为简单路径。
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。
在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
图的基本操作
（1）创建一个图结构 CreateGraph(G)
（2）检索给定顶点 LocateVex(G,elem)
（3）获取图中某个顶点 GetVex(G,v)
（4）为图中顶点赋值 PutVex(G,v,value)
（5）返回第一个邻接点 FirstAdjVex(G,v)
（6）返回下一个邻接点 NextAdjVex(G,v,w)
（7）插入一个顶点 InsertVex(G,v)
（8）删除一个顶点 DeleteVex(G,v)
（9）插入一条边 InsertEdge(G,v,w)
（10）删除一条边 DeleteEdge(G,v,w)
（11）遍历图 Traverse(G,v)
生成树
图的生成树和森林
显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。
最小生成树
在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。
图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边
下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。
构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值儘可能小的边，为了保证加入到生成树中的边不会造成迴路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设定2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重複这个操作n-1次。
下面我们考虑一下如何实现这个操作过程的算法。
分析 ：（1）它主要有两项操作：按条件选择一条边和将顶点加入到U集合中；（2）网中的每个顶点不是在U集合中，就是在V-U集合中。为了提高算法的时间、空间效率，我们将为这个算法设计一个辅助数组closedge，用来记录从集合U到集合V-U具有最小权值的边。对每个属于V-U集合的顶点，在辅助数组中存在一个相应的分量closedge[i-1]，它包括两个域，一个域用来表示在该顶点与V-U集合中某些顶点构成的边中权最小的那条边的权值，若该顶点进入U集合，则值为0；另一个域表示这条最小权值的边对应的在V-U集合中的顶点下标。其类型定义如下所示：
#define MAX_NUM 10struct{int adjvex;float lowcist;}closedge[MAX_NUM];整个算法的执行过程可以描述为：
{初始化closedge数组的内容；选择某个顶点k作为生成树的根结点，并将它加入到U集合中；重複下列操作n-1次：l选择一条满足条件的边；l输出这条边的两个端点；l修改V-U集合中的顶点信息，即与U集合中构成最小权值的边。}假设该网以邻接矩阵的形式给出，则完整的算法为：
void Mini_SpanTree(GraphG,intk,intn){//G是网的邻接矩阵，k是生成树根结点的序号，n是网的顶点数目for(j=0;j<n;j++)if(j!=k)closedge[j]={k,G[k][j]};closedge[k].lowcost=0;for(i=1;i<n;i++){k=minmun(closedge);printf(k,closedge[k].adjvex);closedge[k].lowcost=0;//将顶点加入U集合中for(j=0;j<n;j++)if(closedge&&G[k][j]<closedge[j].lowcost)closedge[j]={k,G[k][j]};}}存储结构
邻接矩阵:
有向图的邻接矩阵
具有n个顶点的有向图可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当<vi,vj>是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数；入度为第i列中"1"的个数，并且有向图弧的条数等于矩阵中"1"的个数。
无向图的邻接矩阵
具有n个顶点的无向图也可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i 行中"1"的个数或第i列中"1"的个数。图中边的数目等于矩阵中"1"的个数的一半，这是因为每条边在矩阵中描述了两次。
在C 语言中，实现邻接矩阵表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 20typedef struct graph{Elemtype elem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];int n;}Graph;邻接表
边结点的结构为：
adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧结点的指针
elem是顶点内容，firstedge是指向第一条边或弧结点的指针。
在C语言中，实现邻接表表示法的类型定义如下所示：
#define MAX_VERTEX_NUM 30//最大顶点个数typedef struct EdgeLinklist{//边结点int adjvex;struct EdgeLinklist*next;}EdgeLinklist;typedef struct VexLinklist{//顶点结点Elemtype elem;EdgeLinklist* firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];创建有向图和无向图邻接表的算法实现：
（1） 创建有向图邻接表
void Create_adj(AdjListad j,int n){for(i=0;i<n;i++){//初始化顶点数组scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//输入弧while(i){s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));//创建新的弧结点s->adgvex=j-1;s->next=adj[i-1].firstedge;//将新的弧结点插入到相应的位置adj[i-1].firstegde=s;scanf(&i,&j);//输入下一条弧}}（2）创建无向图的邻接表
void Create_adj(AdjListadj,intn){for(i=0;i<n;i++){//初始化邻接表scanf(&adj.elem);adj.firstedge=NULL;}scanf(&i,&j);//输入边while(i){s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s1->adgvex=j-1;s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));s2->adgvex=i-1;s1->next=adj[i-1].firstedge;adj[i-1].firstegde=s1;s2->next=adj[j-1].firstedge;adj[j-1].firstegde=s2;scanf(&i,&j);}}图的遍历
常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。
深度优先遍历
深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。
深度优先遍历算法实现：
为了便于在算法中区分顶点是否已被访问过，需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来设定访问标誌，其初始值visited（0≤i≤n-1）为"0"，表示邻接表中下标值为i的顶点没有被访问过，一旦该顶点被访问，将visited置成"1"。
int visited[0..n-1]={0,0,...0};
void DFS(AdjList adj,int v)
{//v是遍历起始点的在邻接表中的下标值，其下标从0开始
visited[v]=1; visited(adj[v].elem);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) DFS(adj,w->adjvex);
}
对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；而对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测：
int visited[0..n-1]={0,0,...0};void DFSTraverse(AdjListadj){for(v=0;v<n;v++)if(!visited[v])DFS(adj,v);}广度优先遍历
对图的广度优先遍历方法描述为：从图中某个顶点v出发，在访问该顶点v之后，依次访问v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。下面是对一个无向图进行广度优先遍历的过程。
下面我们讨论一下实现广度优先遍历算法需要考虑的几个问题：
（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个伫列结构记录顶点访问顺序，就可以利用伫列结构的操作特点，将访问的每个顶点入队，然后，再依次出队，并访问它们的邻接点；
（2）在广度优先遍历过程中同深度优先遍历一样，为了避免重複访问某个顶点，也需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。
int visited[0..n-1]={0,0,...0};
void BFS(AdjList adj,int v)
{//v是遍历起始点在邻接表中的下标，邻接表中下标从0开始
InitQueue(Q); //Q是伫列
visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);
while (!QueueEmpty(Q)) {
DeQueue(Q,v);
for (w=adj[v].firstedge;w;w=w->next)
if (!visited[w->adjvex]) {
visited[w->adjvex]=1;
visite(adj[w->adjvex].elem);
EnQueue(Q,w->adjvex); }
}
}
拓扑排序
拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。
拓扑排序的方法：
（1）从图中选择一个入度为0的顶点且输出之；
（2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；
反覆执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为0的顶点，选择注：表中c1~c9列表示的是每个顶点的入度。
下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。
下面给出算法实现的基本过程：
{ 将所有入度为0的顶点入栈；
当栈非空时重複执行下列操作：
从栈中退出顶点k；
（1）将k顶点的信息输出；
（2）将与k邻接的所有顶点的入度减1。
}
#define MAX_VERTEX_NUM 30//最大顶点个数typedef struct EdgeLinklist{//边结点int adjvex;struct EdgeLinklist*next;}EdgeLinklist;typedef struct VexLinklist{//顶点结点Elemtype elem;int indegree;//记录顶点的入度EdgeLinklist* firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];下面是拓扑排序的完整算法。
Status TopologicalSort(AdjListadj){InitStack(s);for(i=0;i<MAX_VERTEX_NUM-1;i++)if(adj.indegree==0)Push(s,i);while(!StackEmpty(s)){Pop(s,i);printf(i);for(p=adj.firstedge;p;p=p->next){adj.indegree-=1;if(adj.indegree==0)Push(s,i);}重要的图
树
平面图
连通图
强连通图
有向无环图
AOV网
AOE网
完全图：每一对不同顶点间都有边相连的的图，记作Kn。
二分图：顶集，且每一条边都有一个顶点在X中，而另一个顶点在Y中。
完全二分图：二分图G中若任意两个X和Y中的顶点都有边相连。若，则图G记作Km,n。
正则图：如果图中所有顶点的度皆相等，则此图称为正则图
二叉图
基本概念
h图是一个有序对<V，E>，V是结点集，E是边集，当½V½,½E½有限时，<V,E>称为有限图；否则称无限图.
h无向边, 与无序结点(v,u)相关联的边；有向边，与有序结点<v,u>相关联的边.
h无向图，每条边都是无向边的图，记作G=<V,E>; 每条边都是有向边的图，记作D=<V,E>.
h混合图，既有有向边，也有无向边的图.
h平凡图，仅有一个结点的图；零图，边集为空集的图<V, Æ>，即仅有结点的图.
h自迴路(环)，关联于同一个结点的边.
h无向平行边，联结相同两个结点的多于1条的无向边；有向平行边，联结两个结点之间的多于1条且方向相同的有向边.
h简单图，不含平行边和自迴路的图.
h在无向图G=<V,E>中，与结点v(ÎV)关联的边数，即为结点度数deg(v)或d(v).；在有向图中，结点v的出度和入度之和为度数.
h在有向图D=<V,E>中，以v(ÎV)为起点的边之条数为出度deg+(v)；以v(ÎV)为终点的边之条数为入度deg－(v)..
h最大度数，D(G)=max{d(v)½vÎV}；最小度数，d(G)=min{d(v)½vÎV}
h有n个结点的且每对结点都有边相连无向简单图，无向完全图Kn. 此时有 ；有n个结点的且每对结点之间都有两条方向相反的边相关连的有向简单图为有向完全图，.此时有
h设G=<V,E>, V，E的子集V¢,E¢构成的图G¢=<V¢,E¢>是图G的子图；若G¢ÍG且G¢¹G，(V¢ÌV或E¢ÌE)，G¢是G的真子图.
h生成子图，设图G=<V,E>, 若E¢ÍE, 则图<.V,E¢>是<V,E>的生成子图. 即结点与原图G相同的子图，为生成子图.
h补图`G=<V,E¢>，设G=<V,E>, 以V为结点集，以使G成为完全图所添加的边为边集E¢的图，就是图G的补图G¢,.，即<V,EÈE¢>是完全图, 其中EÇE¢=Æ.
h图的同构，设G1=<V1,E1>和G2=<V2,E2>, 存在双射f：V1®V2，"(vi,vj)ÎE1, 若且唯若 (f(vi),f(vj))ÎE2，且(vi,vj)与 (f(vi),f(vj))的重数相同. 则G1≌G2.
同构充分条件：建立两个图的对应关係，这个关係是双射函式.
同构必要条件：①结点数相同；②边数相同；③度数相同的结点个数相同.
图的遍历
图的遍历方法有深度优先搜寻法和广度(宽度)优先搜寻法。
深度优先搜寻法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0齣发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：
Boolean visited[MAX_VERTEX_NUM];//访问标誌数组Status(*VisitFunc)(intv);//VisitFunc是访问函式，对图的每个顶点调用该函式void DFSTraverse(Graph G,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//访问标誌数组初始化for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);//对尚未访问的顶点调用DFS}void DFS(Graph G,int v){//从第v个顶点出发递归地深度优先遍历图Gvisited[v]=TRUE;VisitFunc(v);//访问第v个顶点for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)，//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。//若w是v的最后一个邻接点，则返回空(0)。if(!visited[w])DFS(G,w);//对v的尚未访问的邻接顶点w调用DFS}图的广度优先搜寻是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, …, vi t，并均标记已访问过，然后再按照vi1,vi2, …, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：
Boolean visited[MAX_VERTEX_NUM];//访问标誌数组Status(*VisitFunc)(intv);//VisitFunc是访问函式，对图的每个顶点调用该函式void BFSTraverse(Graph G,Status(*Visit)(intv)){VisitFunc=Visit;for(v=0;v<G.vexnum,++v)visited[v]=FALSE;initQueue(Q);//置空辅助伫列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){visited[v]=TRUE;VisitFunc(v);EnQueue(Q,v);//v入伫列while(!QueueEmpty(Q)){DeQueue(Q,u);//队头元素出队并置为ufor(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!Visited[w]){//w为u的尚未访问的邻接顶点Visited[w]=TRUE;VisitFunc(w);EnQueue(Q,w);}}}}