图（Graph）的概念和遍历

定义

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成

通常表示为：G(V,E)，其中，G（Graph）表示一个图，V(Vertex）是图G中顶点的集合，E（Edg）是图G中边的集合

图的顶点与边间关系

邻接点（Adjacent）

有边/弧相连的两个顶点之间的关系
- 存在（vᵢ，vⱼ），则称 vᵢ 和vⱼ 互为领接点
- 存在<vᵢ，vⱼ>，则称 vᵢ 领接到 vⱼ，vⱼ 领接于 vᵢ

关联（依附）

边/弧与顶点之间的关系
- 存在（vᵢ，vⱼ）/<vᵢ，vⱼ>，则称该边/弧关联于 vᵢ 和 vⱼ

顶点的度

无向图的度（Degree）：顶点 v 的度是和 v 相关联的边的数目，记为TD(v)
在有向图中，顶点的度等于该顶点的入度和出度之和
- 顶点 v 的入度（InDegree），是以 v 为终点的有向边的条数，记做 ID(v)
- 顶点 v 的出度（OutDegree），是以 v 为始点的有向边的条数，记做 OD(v)

例：图中各顶点的度

有向树

Q：当有向图中仅 1 个顶点的入度为 0，其余顶点的入度均为 1，此时是何形状？

A：是一棵有向树

路径

连续的边构成的顶点序列

路径长度

路径上边或弧的数目/权值之和

回路（环）（Cycle）

起点和终点相同的路径称为回路或环

起点、终点为0，是回路

简单路径

序列中顶点不重复出现的路径称为简单路径

简单路径：0→1→3→2

非简单路径：0→1→3→0→1→2

简单回路（简单环）

除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环

连通图相关术语

连通图（Connected Graph）

在无向图 G=(V,{E}) 中，若对任何两个顶点 v、u 都存在从 v 到 u 的路径，则称 G 是连通图（在有向图中，则称为强连通图）

无向图中的连通图

任意两个顶点之间都存在路径，是连通图（在无向图中）

非连通图

有向图中的强连通图

强连通图（在有向图中）

非强连通图

连通分量

无向图 G 中的极大连通子图称为 G 的连通分量，连通分量可以有多个（有向图中，称为强连通分量）
极大连通子图
- 首先，该子图是 G 的连通子图
- 其次，如果此时加入任何一个不在该子图中的顶点，就会导致它不再连通

无向图中的连通分量

有向图中的连通分量

极小连通子图

该子图是 G 的连通子图，在该子图中删除任何一条边，就会导致子图不再连通

生成树

包含无向图 G 所有顶点的极小连通子图

生成森林

对非连通图，由各个连通分量的生成树的集合

图的抽象数据类型

ADT 图(Graph)
Data顶点的有穷非空集合和边的集合
OperationCreateGraph(*G, V, VR)：按照顶点集 V 和边弧集 VR 的定义构造图 GDestroyGraph(*G)：图 G 存在则销毁LocateVex(G, u)：若图 G 中存在顶点 u， 则返回图中的位置GetVex(G, v)：返回图 G 中顶点 v 的值PutVex(G, v, value)：将图 G 中顶点 v 赋值 valueFirstAdjVex(G, *v)：返回顶点 v 的一个邻接顶点， 若顶点在 G 中无邻接顶点返回空NextAdjVex(G, v, *w)：返回顶点 v 相对于顶点 w 的下一个邻接顶点，若 w 是 v 的最后一个邻接点则返回空InsertVex(*G, v)：在图 G 中增添新节点 vDeleteVex(*G, v)：删除图 G 中顶点 v 及其相关的弧InsertArc(*G, v, w)：在图 G 中增点弧 <v, w>， 若 G 是无向图，还需要增添对称弧 <w, v>。DeleteArc(*G, v, w)：在图 G 中删除弧 <v, w>，若 G 是无向图，则还需要删除对称弧 <w, v>。DFSTraverse(G)：对图 G 中进行深度优先遍历，在遍历过程对每个顶点调用HFSTraverse(G)：对图 G 中进行广度优先遍历，在遍历过程对每个顶点调用
endADT

邻接矩阵表示法

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图
- 一个一维数组存储图中顶点信息
- 一个二维数组（称为邻接矩阵）存储图中的边或弧的信息（有 n 个顶点，邻接矩阵是一个 n×n 的方阵）
设图 A=（V,E）有 n 个顶点，则顶点表 Vexs[n]

i	0	1	2	...	n-1
Vexs[i]	V₁	V₂	V₃	...	Vₙ

图的邻接矩阵是一个二维数组 A.arcs[n][n]，定义为：

无向图的邻接矩阵表示法

如果存在邻接关系，邻接矩阵的值就是1，不存在就是0

无向图的邻接关系是对称的
顶点 i 的度 = 第 i 行（列）中 1 的个数
特别地，如果是在完全图的邻接矩阵中，对角元素为0，其余为1

因为有 5 个顶点，所以需要 5×5 的方阵
V₁和V₂、V₄有边，是邻接关系，邻接矩阵的值为1，其余为0
V₂和V₁、V₃、V₅有边，邻接矩阵的值为1，其余为0
……

有向图的邻接矩阵表示法

如果存在着由当前顶点，发出的弧，邻接矩阵值为1，其余为0

有向图的邻接矩阵可能是不堆成的
顶点的出度 = 第 i 行元素之和
顶点的入度 = 第 i 列元素之和
顶点的度 = 第 i 列元素之和 + 第 i 列元素之和

V₁ 对 V₂、V₃ 发出弧，邻接矩阵值为1，其余为0
V2 没有发出弧，邻接矩阵值为0
……

网（即有权图）的邻接矩阵表示法

由当前顶点，发出的弧，邻接矩阵值为其权，其余为∞（因为负数和0都可能是权值，所以用∞）

定义为 A.arcs[ i ][ j ]
- Wᵢⱼ，<vᵢ，vⱼ>或（vᵢ，vⱼ）存在
- ∞，无边（弧）

邻接矩阵的存储表示

typedef char VertexType; 			/* 顶点类型应由用户定义  */
typedef int EdgeType; 				/* 边上的权值类型应由用户定义 */
#define MAXVEX 100 					/* 最大顶点数，应由用户定义 */
#define INFINITY 65535				/* 用65535来代表∞ */typedef struct
{VertexType vexs[MAXVEX]; 		/* 顶点表 */EdgeType arc[MAXVEX][MAXVEX];	/* 邻接矩阵，可看作边表 */int vexnum, edgesnum; 		    /* 图中当前的顶点数和边数  */
}AMGraph;                           /* Adjacency Matrix Graph */

采用邻接矩阵表示法创建无向网

算法思路

输入总顶点数和总边数
依次输入点的信息存入顶点表中
初始化邻接矩阵，使每个权值初始化为极大值
构造邻接矩阵

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(AMGraph* G)
{int i, j, k, w;printf("输入顶点数和边数:\n");scanf("%d,%d", &G->vexnum, &G->edgesnum); 		/* 输入顶点数和边数 */for (i = 0; i < G->vexnum; i++) 					/* 读入顶点信息,建立顶点表 */scanf(&G->vexs[i]);for (i = 0; i < G->vexnum; i++)for (j = 0; j < G->vexnum; j++)G->arc[i][j] = INFINITY;					/* 邻接矩阵初始化 */for (k = 0; k < G->edgesnum; k++) 					/* 读入numEdges条边，建立邻接矩阵 */{printf("输入边(vi,vj)上的下标i，下标j和权w:\n");scanf("%d,%d,%d", &i, &j, &w); 				/* 输入边(vi,vj)上的权w */G->arc[i][j] = w;G->arc[j][i] = G->arc[i][j]; 				/* 因为是无向图，矩阵对称 */}
}

邻接表表示法（链式）

顶点
- 按编号顺序将顶点数据存储在一维数组中
关联同一顶点的边发（以顶点为尾的弧）
- 用线性链表存储

无向图的邻接表

特点

邻接表不唯一
若无向图中有 n 个顶点、e 条边，则其邻接表需 n 个头结点和 2e 个表结点。适合存储稀疏图
无向图中顶点 vᵢ 的度为第 i 个单链表中的结点数

有向图的邻接表和逆邻接表

邻接表特点

顶点 vᵢ 的出度为第 i 个单链表中的结点个数
顶点 vᵢ 的入度为整个单链表中邻接点域值是 i-1 的结点个数

逆邻接表特点

顶点 vᵢ 的入度为第 i 个单链表中的结点个数
顶点 vᵢ 的出度为整个单链表中邻接点域值是 i-1 的结点个

图的邻接表存储表示

typedef char VertexType; 	/* 顶点类型应由用户定义 */
typedef int EdgeType; 		/* 边上的权值类型应由用户定义 */typedef struct EdgeNode 	/* 边表结点  */
{int adjvex;    			/* 邻接点域,存储该顶点对应的下标 */EdgeType weight;		/* 用于存储权值,对于非网图可以不需要 */struct EdgeNode *next; 	/* 链域,指向下一个邻接点 */
}EdgeNode;typedef struct VertexNode 	/* 顶点表结点 */
{VertexType data; 		/* 顶点域,存储顶点信息 */EdgeNode *firstedge;	/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];/* 图的结构定义 */
typedef struct
{AdjList adjList; int numNodes,numEdges; 	/* 图中当前顶点数和边数 */
}GraphAdjList;

采用邻接表表示法创建无向网

/* 建立图的邻接表结构 */
void  CreateALGraph(GraphAdjList *G)
{int i,j,k;EdgeNode *e;printf("输入顶点数和边数:\n");scanf("%d,%d",&G->numNodes,&G->numEdges); 	/* 输入顶点数和边数 */for(i = 0;i < G->numNodes;i++) 				/* 读入顶点信息,建立顶点表 */{scanf(&G->adjList[i].data); 			/* 输入顶点信息 */G->adjList[i].firstedge=NULL; 			/* 将边表置为空表 */}for(k = 0;k < G->numEdges;k++)				/* 建立边表 */{printf("输入边(vi,vj)上的顶点序号:\n");scanf("%d,%d",&i,&j); 					/* 输入边(vi,vj)上的顶点序号 */     e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */     e->adjvex=j;							/* 邻接序号为j */                  e->next=G->adjList[i].firstedge;		/* 将e的指针指向当前顶点上指向的结点 */G->adjList[i].firstedge=e;				/* 将当前顶点的指针指向e */          e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */     e->adjvex=i;							/* 邻接序号为i */                  e->next=G->adjList[j].firstedge;		/* 将e的指针指向当前顶点上指向的结点 */G->adjList[j].firstedge=e;				/* 将当前顶点的指针指向e */           }
}

十字链表（Orthogonal List）

把邻接表和逆邻接表结合起来

顶点结点
- firstin，第一条入弧
- firstout，第一条出弧
弧结点
- tailvex，弧尾位置
- headvex，弧头位置
- hlink，弧头相同的下一条弧
- tlink，弧尾相同的下一条弧

a 的出度有2条，a 的出度 b（01），a 的出度 c（02）
a的入度有2条，a 的入度 c（20），a 的入度 d（30）

b 没有出度，记为空（^）
b 的入度有2条，b 的入度 a（01），b 的入度 d（31）

邻接多重表

邻接表的优点：容易求得顶点和边的信息
缺点：某些操作不方便，如：删除一条边需找表示此边的两个结点

顶点结点
- firstedage，指向第一条依附于该顶点的边
边结点
- mark，标志域，标记此边是否被搜索过
- ivex，该边依附的两个顶点在表头数组中位置
- ilink，指向依附于 ivex 的下一条边
- jvex，该边依附的两个顶点在表头数组中位置
- jlink，指向依附于 jvex 的下一条边

0号位的 v₁ 和 1 号位的 v₂ 有一条边，和 3 号位的 v₄ 有一条边

和 v₂ 顶点有关的边

最后

图的遍历

深度优先遍历（Depth_First_Search，DFS）

用邻接矩阵表示图，遍历图中每一个顶点都要从头扫描该顶点所在行
- 时间复杂度为O(n2)
- 稠密图适与在邻接矩阵上进行深度遍历
用邻接表来表示图，有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间
- 时间复杂度为O(n+e)
- 稀疏图适于在邻接表上进行深度遍历

思路（一条路走到黑，直到往回退）

假设 2 为起点

将辅助数组的2改为1，意思是访问过2号顶点了

看第2行（是2顶点），邻接点1没有访问过，所以访问1

然后再从1顶点去找（看下标为1的行），1与2的值为1，但以及访问过2了
1与3的值为1，且没有访问过，所以访问3

看下标为3的这一行，3与1的值为1，但1已经访问过了
3与5的值为1，且5没有访问，所以访问5
然后看下标为5的这一行，发现5与2和3的值为1，但都访问过了
于是，往回退（从哪来，往哪退）
5退回3，发现3与1和5的值为1，但也都访问过了，继续往回退
3退回1，下标为1的这一行，与2和3的值为1，但都访问过了。与4的值为1，而4没有访问过，所以访问4
下标为4的这一行，因为4与6的值为1，且没访问过，所以访问6
到下标为6的这一行，发现与4的值为1，访问过了，所以往回退
6退回4，4退回1，1退回2，退回起点了，发现所以结点都访问过了，访问结束

邻接矩阵的深度优先遍历算法

#define MAXVEX 9
Boolean visited[MAXVEX]; 				/* 访问标志的数组 *//* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G, int i)
{int j;visited[i] = TRUE;printf("%c ", G.vexs[i]);			/* 打印顶点，也可以其它操作 */for(j = 0; j < G.numVertexes; j++)if(G.arc[i][j] == 1 && !visited[j])DFS(G, j);					/* 对为访问的邻接顶点递归调用 */
}/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G)
{int i;for(i = 0; i < G.numVertexes; i++)visited[i] = FALSE; 			/* 初始所有顶点状态都是未访问过状态 */for(i = 0; i < G.numVertexes; i++)if(!visited[i]) 				/* 对未访问过的顶点调用DFS，若连通图仅执行一次 */ DFS(G, i);
}

广度优先遍历（Breadth_First_Search, BFS）

如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素）
- 时间复杂度为O(n2)
用邻接表表示图，有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间
- 时间复杂度为O(n+e)

思路（把顶点的所以邻接点全访问）

从1结点开始，访问它的所有结点，依次为2和3

然后访问2的所有邻接点，依次访问4和5
然后访问3的所有邻接点，一次访问6和7
再访问4的所有邻接点8
所有邻接点访问完

用队列实现图的广度优先遍历思路

从结点1开始，v₁的下标是0，0入队
这时，v₁就被访问过了

然后v₁出队

把v₁的邻接点v₂，v₃依次入队

v₂出队

将v₂的邻接点入队，0号已经入了，将3、4号入队

将2号出队（访问v₃），将v₃的邻接点5、6号入队，0号已经访问过了，不入

将3号出队（访问v₄），将v₄的邻接点7号入队
再访问下一个，直到所有都访问

邻接矩阵的广度优先遍历算法

/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{int i, j;Queue Q;for(i = 0; i < G.numVertexes; i++)visited[i] = FALSE;InitQueue(&Q);									/* 初始化一辅助用的队列 */for(i = 0; i < G.numVertexes; i++)  			/* 对每一个顶点做循环 */{if (!visited[i])							/* 若是未访问过就处理 */{visited[i]=TRUE;						/* 设置当前顶点访问过 */printf("%c ", G.vexs[i]);				/* 打印顶点，也可以其它操作 */EnQueue(&Q,i);							/* 将此顶点入队列 */while(!QueueEmpty(Q))					/* 若当前队列不为空 */{DeQueue(&Q,&i);						/* 将队首元素出队列，赋值给i */for(j=0;j<G.numVertexes;j++) { 							/* 判断其它顶点若与当前顶点存在 *//* 边且未访问过 */if(G.arc[i][j] == 1 && !visited[j]) { 					visited[j]=TRUE;			/* 将找到的此顶点标记为已访问 */printf("%c ", G.vexs[j]);	/* 打印顶点 */EnQueue(&Q,j);				/* 将找到的此顶点入队列  */} } }}}
}