考研数据结构与算法（七）图论

一、图的基本概念 1.1 图的定义

图 G 由顶点集 V V V 边集 E E E 组成，记为 G = ( V , E ) G=(V, E) G=(V,E) ， 其中 V ( G ) V(G) V(G) 表示图 G G G 中顶点的有限非空集； E ( G ) E(G) E(G) 表示图 G G G 中顶点之间的关系 （边） 集合。 若 V = V 1 , V 2 ， … ， V n V= {V_1 , V_2，…， V_n} V=V1​,V2​，…，Vn​，则用 ∣ V ∣ |V| ∣V∣ 叫表示图中顶点的个数，也称图 G G G 的阶， E = ( u , v )   ∣   u ∈ V , v ∈ V E = {(u,v) \ | \ u∈V,v∈V} E=(u,v) ∣ u∈V,v∈V，用 ∣ E ∣ |E| ∣E∣ 表示图 G G G 中边的条数。

注意：图的顶点集 V V V 一定为非空，而图的边集 E E E 可能为空

1.2 基本术语 1.2.1 有向图

图中的边集是由方向的，例如有一个从点 A A A 到 B B B 的有向边，那么我们从 A A A 点可以到达 B B B 点，而不能从 B B B 点到达 A A A 点，这样就是一个有向边，在这条边中点 A A A 被称为 弧尾 ，而点 B B B 被称为 弧头 ，我们通常用这样的符号来记录这条边：

1.2.2 无向图

很显然没有方向的边和顶点集构成的图就为无向图，按照上面的情况，在无向图中顶点之间是互相连通的，即若有一个点 A A A 到点 B B B 的边，从 B B B 出发也是能到达 A A A 点的，我们通常使用这样的符号来记录这条边：(A,B)

1.2.3 简单图

一个图 G G G 若满足：

• ①不存在重复边
• ②不存在顶点到自身的边，则称图 G G G 为简单图

1.2.4 多重图

若图 G G G 中某两个结点之间的边数多于一条，又允许顶点通过同一条边也和自己关联，则 G G G 为多重图。多重图的定义和简单图是相对的

1.2.5 完全图

• 在一个顶点数量为 n n n 的无向图中，若边的数量为 ( n − 1 ) × n 2 \frac{(n-1)\times n}{2} 2(n−1)×n​ ，则该无向图为完全图
• 在一个顶点数量为 n n n 的有向图中，若边的数量为 ( n − 1 ) × n (n-1)\times n (n−1)×n ，则该有向图为完全图

1.2.6 子图

设有两个图 G = ( V , E ) G = (V,E) G=(V,E) 和 G ′ ＝ ( V ′ , E ′ ) G'＝(V',E') G′＝(V′,E′)， 若 V ′ V' V′是 V V V 的子集，且 E ′ E' E′是 E E E 的子集，则称 G ′ G' G′ 是 G G G 的子图，若满足 V ′ = V V' = V V′=V 且 E ′ ⊂ E E' \subset E E′⊂E 那么子图 G ′ G' G′ 为 G G G 的生成子图

注意：并非 V V V 和 E E E 的任何子集都能构成 G G G 的子图，因为这样的子集可能不是图， 即 E E E 的子集中的某些边关联的顶点可能不在这个 V V V 的子集中

1.2.7 连通、连通分量、连通图

关于连通方面的定义都是基于无向图的

• 连通：在无向图中若从顶点 u u u 到顶点 v v v 有路径存在，那么称 u u u 和 v v v 是连通的
• 连通图：若无向图中任意两点是连通的，那么这个无向图就称为连通图，否则称为非连通图
• 连通分量：对于一个连通图而言，其连通分量只有一个就是其本身，而对于非连通图而言，连通分量有多个，其每一个子图（或者称为极大联通子图）都是一个连通分量

很显然一个 n n n 个点的连通图最少有 n − 1 n-1 n−1 条边（即后面提到的生成树），最多有 ( n − 1 ) × n 2 \frac{(n-1)\times n}{2} 2(n−1)×n​ 个边

这里再补一下 极小连通子图 的定义：一个顶点为 n n n 的子图的边数为 n − 1 n-1 n−1 （其实后面也能知道这其实是生成树的定义） ，就称其为极小连通子图，很显然这样的子图也是一个极大连通子图，因为它是一个连通分量。

例如，对于下面的这个非连通图，其连通分量有三个：

1.2.8 强连通

关于强连通方面的定义都是基于有向图的

• 强连通：在有向图中，若从顶点 v v v 到顶点 w w w 和从顶点 w w w 到顶点 v v v 之间都有路径 ，则称这两个顶点为强连通的
• 强连通图：若有向图中任意两点之间都是强连通的，那么称这个有向图为强连通图，否则称为非强连通图
• 强连通分量：对于一个强连通图而言，其强连通分量就是本身，而对于一个非强连通图而言，其极大强连通子图就为该非强连通分量（在子图中任意两点仍满足强连通）

例如，对于如下的非强连通图，其中点 A A A 和 B B B 构成的子图就为极大联通子图，即强连通分量，而点 C C C 和 D D D 构成的子图则不是强连通分量

1.2.9 生成树、森林

生成树、森林一般是基于无向图的

连通图的生成树是包含图中全部顶点的一个极小连通子图，即一个 n n n 个点的连通图中有 n − 1 n-1 n−1 条边

很显然这样的连通图，如果减去一条边就会形成非连通图，而若是加上一条边，则会形成回路

例如，下图中的连通图就为一个生成树：

而生成森林其实就是多个连通子图都是极小连通子图（生成树），那么就称这个森林为生成森林，例如下图中左边森林为生成森林，而右边的森林不是连通森林：

1.2.10 顶点的度

• 无向图：对于无向图而言，顶点的度就是和该顶点相连接的边数
• 有向图：对于有向图而言，指向该顶点的边数称为入度，而从该顶点指出的边数称为出度

• 无向图的全部顶点的度之和等于两倍的边数
• 有向图的全部顶点的出度等于全部顶点的入度等于边数

1.2.11 边权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。 这种边上带有权值的图称为带权图，也称网 。 网中通常分为， A O V AOV AOV 网和 A O E AOE AOE 网

• A O V AOV AOV 网：没有权值，或者权值都相同，主要是在于点与点之间的先后关系
• A O E AOE AOE 网：有权值，每一个点称为事件，而边称为活动

1.2.12 稠密、稀疏图

• 稠密图：点数较大，而边数较少的图称为稀疏图
• 稠密图：点数较小，而边数较多的图称为稠密图

一般来说当图 G G G 满足 ∣ E ∣ < ∣ V ∣ l o g 2 ∣ V ∣ |E| < |V|log_2|V| ∣E∣ 是 E ( G ) 中的边 0 , 若 ( V i , V j ) 或者 < V i , V j > 不是 E ( G ) 中的边 A[i][j] = \begin{cases} 1 ,若(V_i,V_j)或者 是E(G)中的边 \\ 0 ,若(V_i,V_j)或者 不是E(G)中的边\\ \end{cases} A[i][j]={1,若(Vi​,Vj​)或者是E(G)中的边0,若(Vi​,Vj​)或者不是E(G)中的边​

对于有权图 A [ i ] [ j ] A[i][j] A[i][j] 的含义如下： A [ i ] [ j ] = { V [ i ] [ j ] , 若 ( V i , V j ) 或者 < V i , V j > 是 E ( G ) 中的边 0 或 ∞ , 若 ( V i , V j ) 或者 < V i , V j > 不是 E ( G ) 中的边 A[i][j] = \begin{cases} V[i][j] ,若(V_i,V_j)或者 是E(G)中的边 \\ 0或∞ ,若(V_i,V_j)或者 不是E(G)中的边\\ \end{cases} A[i][j]={V[i][j],若(Vi​,Vj​)或者是E(G)中的边0或∞,若(Vi​,Vj​)或者不是E(G)中的边​ 我们可以将这个结构进行封装为如下形式：

#define MaxVertexNum 100
typedef struct {
	int Vex[MaxVertexNum];//存储当前顶点的表
	int Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵表
	int vexnum, arcnum;//当前的顶点数和弧数
}

邻接矩阵存储表示法的特点：

• ①无向图的邻接矩阵一定是一个对称矩阵且唯一，因此我们可以使用三角矩阵压缩存储，就能节省一半的空间
• ②对于无向图邻接矩阵的第 i i i 行（列）的非 0 0 0 元素的个数就为第 i i i 个顶点的度
• ③对于有向图邻接矩阵，第 i i i 行（列）的非 0 0 0 元素的个数就为第 i i i 个顶点的出度（入度）
• ④邻接矩阵适合存储稠密图

一些通过邻接矩阵存储的图的示例如下：

2.2 邻接表

我们对图中每一个顶点建一个单链表，然后链表的元素就为其所连接的点，这样就能节省大量的空间，这样的邻接表中存在两种类型的结点：顶点结点、边表结点 这个顶点结点就类似我们之前的头节点，下面是无向图和有向图的邻接链表的例子：

无向图： 有向图： 我们可以简单得到一下这个邻接表的结构：

#define MaxVertexNum 100 
typedef struct ArcNode{ //边表结点
	int adjvex; //该弧指向的顶点的位置
	struct ArcNode *next; //下一条弧的位置
	// infoType info;
}ArcNode; 
typedef struct VNode{ //顶点结点
	VertexType data; //顶点的信息，例如值之类的
	ArcNode *first;//第一个边表结点的位置
}VNode , AdjList[MaxVertexNum]; 
typedef struct{ 
	VNode AdjList[MaxVertexNum]; //顶点结点数组
	int vexnum,arcnum;//顶点数和弧数
} ALGraph;//封装的邻接表的图

邻接表存储方法特点：

• ①若图 G G G 为无向图，则邻接表所需的存储空间为 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(|V|+2|E|) O(∣V∣+2∣E∣) ，若图 G G G 为有向图，则邻接表所需的存储空间为 O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)
• ②邻接表适合稀疏图
• ③图的邻接表表示不唯一，取决于边的读入顺序

2.3 十字链表

首先来说，十字链表是对于有向图而言的，有一点邻接表和邻接矩阵结合的感觉，首先对于每一个顶点来说有一个顶点结点的概念，然后对于其指向的边结点有一个弧结点的概念

• 顶点结点有三个域

  • data 域存放顶点相关的数据信息，
  • firstin 域指向以该顶点为弧头的第一个弧结点（比如这个结点是第二个结点，那么就指向第二列，从上往下看的第一个弧节点元素，当然若是没有的话则指向NULL）
  • firstout 域指向以该顶点为弧尾的第一个弧结点（比如这个结点是第三个结点，那么就指向第三行 的第一个弧结点元素）

• 弧结点有五个域

  • tailvex 尾域表示弧尾的位置（显然对于某一行数据来说，弧尾域都是一样的）
  • headvex 头域表示弧头的位置（显然对于某一列数据来说，弧头域都是一样的）
  • hlink 链域指向弧头相同的下一条弧（其实就是对于每一列的弧结点元素来说，上下相邻的元素从上往下指）
  • tlink 链域指向弧尾相同的下一条弧（其实就是对于每一行的弧结点元素来说，左右相邻的元素从左往右指）
  • info 域一般用于弧的值的存储

例如如下有向图构建的十字链表：

注意：上图中的弧结点没有info 域

2.4 邻接多重链表

邻接多重表是无向图的另一种链式存储结构，着重于边与边以及边与点的关系，与十字链表类似，邻接多重表也有顶点结点以及边结点

• 顶点结点有两个域

  • data 域
  • firstedge 用于存储与该结点相连的第一条边

• 边结点有六个域（但是一般只用其中间的四个）

  • mark 域用于标记这个边是否进行操作过， 0 0 0 表示没操作过， 1 1 1 表示操作过了
  • ivex 用于表示该边的其中一个结点在图中的下标
  • ilink 用于表示与结点 ivex 相邻的第一条边
  • jvex 用于表示该边的另一个结点在图中的下标
  • jlink 用于表示与结点 jvex 相邻的第一条边
  • info 用于表示该边的一些权值等信息

下面是一些绘制邻接多重表的步骤：

• ①我们仍然可以先画出该图的邻接表(但不要画箭头)
• ②因为该图是一个无向图，所以我们需要将重复的边进行删除（统一规划一下可以尽量从往上删除）
• ③然后从每一个顶点结点出发，指向边结点中与之对应的 i l i n k ilink ilink 或者 j l i n k jlink jlink 这里的话有两种方式
  • 第一种按照 D F S DFS DFS 的方法，不断在边结点中找到下一个边结点的位置，直到完成所有的边，再从下一个顶点结点出发
  • 第二种按照 B F S BFS BFS 的方法，首先找到第一个顶点结点的下一个相邻结点，然后再完成下一个顶点结点，然后再不断完成边界点的关系指向 例如假设我们有如下的图结构： 我们需要绘制邻接表，然后删除重复的边： 然后我们采用BFS的方法先完成顶点结点的指向 然后就是不断根据边结点进行连接了，于是我们就得到了多重邻接表的画法(当然多重邻接表不一定唯一)

三、图的遍历方法

也可参见我的另一篇介绍：https://acmer.blog.csdn.net/article/details/122310835

3.1 广度优先搜索（BFS）

图的广度优先搜索类似于树的层序遍历，不断地将未访问的结点放入队列，然后出队，再将出队元素所连接的所有未访问点放入队列，这个当队列为空的时候，我们就完成了图的广度优先搜索，简单的搜索如下：

bool vis[N];
void bfs(int s){
	queue que;
	que.push(s);
	vis[s] = true;
	while(!que.empty()){
		int t = que.front();
		que.pop();
		printf("%d\t",t);
		for(int i = 0,l = V[t].size();i