图
1. 图的基本概念
1.1 图的定义
图 G G 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 ∣ \left|V\right| ∣V∣表示图 G G G中顶
点的个数， E = { ( u , v ) ∣ u ∈ V , v ∈ V } E=\{(u,v)|u\in V,v\in V\} E={(u,v)∣u∈V,v∈V}，用 ∣ E ∣ \left|E\right| ∣E∣表示图 G G G中边的条数。
下面介绍一些图的专业术语：
1.有向图
若 E E E是有向边(也称弧)的有限集合，则图 G G G为有向图。弧是顶点的有序对，记为 < v , w > <v,w> <v,w>其中 v , w v,w v,w是顶点， v v v称为弧尾， w w w称为弧头， < v , w > <v,w> <v,w>称为从 v v v到 w w w的弧，也称 v v v邻接到 w w w。
下图所示的有向图可以表示为：
G 1 = ( V 1 , E 1 ) V 1 = { 1 , 2 , 3 } E 1 = { < 1 , 2 > , < 2 , 1 > , < 2 , 3 > } G_1=(V_1,E_1)\\V_1=\{1,2,3\}\\E_1=\{<1,2>,<2,1>,<2,3>\} G1=(V1,E1)V1={1,2,3}E1={<1,2>,<2,1>,<2,3>}
2.无向图
若 E E E是无向边(也称弧)的有限集合，则图 G G G为无向图。弧是顶点的无序对，记为 ( v , w ) (v,w) (v,w)或 ( w , v ) (w,v) (w,v)，可以说 w 、 w、 w、 v v v互为邻接点， w w w称为弧头，边 ( v , w ) (v,w) (v,w)和 v v v到 w w w相关联。
G 2 G_2 G2所示的无向图可以表示为：
G 2 = ( V 2 , E 2 ) V 2 = { 1 , 2 , 3 , 4 } E 1 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } G_2=(V_2,E_2)\\V_2=\{1,2,3,4\}\\E_1=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} G2=(V2,E2)V2={1,2,3,4}E1={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
3.完全图
对于无向图，E的取值范围为0到 n ( n − 1 ) 2 \frac{n(n-1)}2 2n(n−1)，有 n ( n − 1 ) 2 \frac{n(n-1)}2 2n(n−1)条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，E的取值范围为0到 n ( n − 1 ) n(n-1) n(n−1)，有 n ( n − 1 ) n(n-1) n(n−1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。
G 2 G_2 G2为无向完全图， G 3 G_3 G3为有向完全图。
4.子图
设有两个图 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的子集，若满足 V ( G ′ ) = V ( G ) V(G')=V(G) V(G′)=V(G)，则称 G ′ G' G′是 G G G的子图。 G 3 G_3 G3是 G 1 G_1 G1的子图。需要注意的是，并非任何子集都能构成子图。
5.连通、连通图、连通分量
在无向图中，若从顶点 v v v到顶点 w w w有路径存在，则称 v v v和 w w w是连通的。若图 G G G中任意两个顶点都是连通的，则称图 G G G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量，图 G 4 G_4 G4有3个连通分量如图(b)所示。若一个图有n个顶点，边数小于n-1，一定是非联通的。非联通图边最多的情况就是n-1个顶点构成连通图，再加入一个顶点变非联通。
6.强连通图、强连通分量
在有向图中，若有一对顶点 v v v和 w w w，从 v v v到 w w w和从 w w w到 v v v之间都有路径，则称这两个顶点是强连通的。若图中任意一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量，图 G 1 G_1 G1的强连通分量如下图所示。假设一个有向图有 n n n个顶点，若是强连通图，则最少需要有 n n n条边，构成一条回路。
7.生成树和生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n n n，则它的生成树含有 n − 1 n-1 n−1条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。图 G 2 G_2 G2的一个生成树如下图所示。
8.顶点的度、入度和出度
在无向图中，顶点 v v v的度是指依附于顶点 v v v的边的条数，记为 T D ( v ) TD(v) TD(v)。在图 G 2 G_2 G2中，每个顶点的度均为3。无向图的全部顶点的度之和等于边数的2倍，因为每条边和两个顶点相关联。
在有向图中，顶点 v v v的度分为入度和出度，入度是以顶点 v v v为终点的有向边的数目，记为 I D ( v ) ID(v) ID(v)；而出度是以顶点 v v v为起点的有向边的数目，记为 O D ( v ) OD(v) OD(v)。在图 G 1 G_1 G1中，顶点 2的出度为2、入度为 1。顶点 v v v的度等于其入度与出度之和，即 T D ( V ) = I D ( v ) + O D ( V ) TD(V)=ID(v)+OD(V) TD(V)=ID(v)+OD(V)。有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点。
n（顶点）， e（边）, TD（度）之间的关系：（有向图与无向图都适用）
e = 1 2 ∑ i = 1 n T D ( v i ) e=\frac{1}{2}\sum_{i=1}^nTD(v_i) e=21i=1∑nTD(vi)
9.边的权和网
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。
10.稀疏图和稠密图
边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模煳的概念，稀疏图和稠密图常常是相对而言的。一般当图 G G G满足 ∣ E ∣ < ∣ V ∣ l o g ∣ V ∣ \left|E|<|V|log|V\right| ∣E∣<∣V∣log∣V∣时，可以将 G G G视为稀疏图。
11.路径、路径长度、回路
顶点 v p v_p vp到顶点 v q v_q vq之间的一条路径是指顶点序列 v p , v i 1 , v i 2 , . . . . . . , v q v_p,v_{i_1},v_{i_2},......,v_q vp,vi1,vi2,......,vq，当然关联的边也可理解为路径的构成要素。路径上的边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有 n n n个顶点，且有大于 n − 1 n-1 n−1条边，则此图一定有环。
12.简单路径、简单回路
在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外其余顶点不重复出现的回路称为简单回路。
13.距离
从顶点 u u u出发到顶点 v v v的最短路径若存在，则此路径的长度称为从 u u u到 v v v的距离。若从 u u u到 v v v根本不存在路径，则记该距离为无穷( ∞ \infty ∞ )。
14.有向树
一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。
2. 图的存储
2.1 邻接矩阵
2.1.1 邻接矩阵定义
所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中
边的信息(即各顶点之间的邻接关系)，存储顶点之间邻接关系的二维数组称为邻接矩阵。
顶点数为 n n n的图 G = ( V , E ) G=(V,E) G=(V,E)的邻接矩阵是 A A A的，将 G G G的顶点编号为 v 1 , v 2 , ⋯ , v n v_1,v_2,\cdots,v_n v1,v2,⋯,vn，则
A [ i ] [ j ] = { 1 , ( 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}1, & (v_i,v_j)\text{或}<v_i,v_j>\text{是}E(G)\text{中的边} \\0, & (v_i,v_j)\text{或}<v_i,v_j>\text{不是}E(G)\text{中的边} & \end{cases} A[i][j]={1,0,(vi,vj)或<vi,vj>是E(G)中的边(vi,vj)或<vi,vj>不是E(G)中的边
对带权图而言, 若顶点 v i v_i vi 和 v j v_j vj 之间有边相连, 则邻接矩阵中对应项存放着该边对应的权值, 若顶点 v i v_i vi和 v j v_j vj不相连, 则通常用 0 或 ∞ \infty ∞ 来代表这两个顶点之间不存在边:
$$
A[i][j]= \begin{cases}w_{i j}, & \left(v_i, v_j\right) \text { 或 }\left\langle v_i, v_j>\text { 是 } E(G)\right. \text { 中的边 } \ 0 \text { 或 } \infty, & \left(v_i, v_j\right) \text { 或 }\left\langle v_i, v_j>\text { 不是 } E(G)\right. \text { 中的边 }\end{cases}
$$
#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
int vexnum, arcnum; //图的当前顶点数和弧树
}MGraph;
void addEdge(const V &src, const V &dst, const W &w)// 邻接矩阵添加结点
{
int srci = getVertexIndex(src);
int dsti = getVertexIndex(dst);
_matrix[srci][dsti] = w;
if (Direction == false)
{
_matrix[dsti][srci] = w;
}
}
注意:
①在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点信息等均可省略)。
②当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType可定义为值为0和1的枚举类型。
③无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可采用压缩存储。
④邻接矩阵表示法的空间复杂度为 O ( n 2 ) O(n^2) O(n2)，其中 n n n为图的顶点数|V|。
⑤ 用邻接矩阵法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
⑥ 稠密图适合使用邻接矩阵的存储表示。
2.1.2 特点
①无向图的邻接矩阵是对称矩阵，可以压缩存储空间数为 n ( n + 1 ) 2 \frac{n(n+1)}2 2n(n+1)。
②对于无向图，邻接矩阵的第 i i i行(或第 i i i列)非零元素(或非 ∞ \infty ∞元素)的个数正好是顶点
i i i的度 T D ( v i ) TD(v_i) TD(vi)。
③对于有向图，邻接矩阵的第 i i i行非零元素(或非 ∞ \infty ∞元素)的个数正好是顶点 i i i的出度
O D ( v i ) OD(v_i) OD(vi)；第 i i i列非零元素(或非 ∞ \infty ∞元素)的个数正好是顶点 i i i的入度 I D ( v i ) ID(v_i) ID(vi)。
④用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。
⑤稠密图(即边数较多的图)适合采用邻接矩阵的存储表示。
⑥设图 G G G的邻接矩阵为 A , A n A,A^n A,An的元素 A n [ i ] [ j ] A^n[i][j] An[i][j]等于由顶点 i i i到顶点 j j j的长度为 n n n的路径的数目。该结论了解即可，证明方法可参考离散数学教材。
2.2 邻接表
当一个图为稀疏图时（边数相对顶点较少），使用邻接矩阵法显然要浪费大量的存储空间，
而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
所谓邻接表，是指对图 G G G中的每个顶点 v i v_i vi建立一个单链表，第 i i i个单链表中的结点表示依附于顶点 v i v_i vi的边(对于有向图则是以顶点 v i v_i vi为尾的弧)，这个单链表就称为顶点 v i v_i vi的边表(对于有向图则称为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种结点:顶点表结点和边表结点，如下图所示。
无向图和有向图的邻接表的实例如下图所示。
#define MAXVEX 100 //图中顶点数目的最大值
type char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
/*边表结点*/
typedef struct EdgeNode{
int adjvex; //该弧所指向的顶点的下标或者位置
EdgeType weight; //权值，对于非网图可以不需要
struct EdgeNode *next; //指向下一个邻接点
}EdgeNode;
/*顶点表结点*/
typedef struct VertexNode{
Vertex data; //顶点域，存储顶点信息
EdgeNode *firstedge //边表头指针
}VertexNode, AdjList[MAXVEX];
/*邻接表*/
typedef struct{
AdjList adjList;
int numVertexes, numEdges; //图中当前顶点数和边数
}ALGraph;
// 严尉敏数据结构写法
int LocateVex(ALGraph G, VerTexType v) {
//确定点v在G中的位置
for (int i = 0; i < G.vexnum; ++i)
if (G.vertices[i].data == v)
return i;
return -1;
}//LocateVex
int CreateUDG(ALGraph& G) {
//采用邻接表表示法，创建无向图G
int i, k;
cout << "请输入总顶点数，总边数中间以空格隔开:";
cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
cout << endl;
cout << "输入点的名称，如 a " << endl;
for (i = 0; i < G.vexnum; ++i) { //输入各点，构造表头结点表
cout << "请输入第" << (i + 1) << "个点的名称:";
cin >> G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc = NULL; //初始化表头结点的指针域为NULL
}//for
cout << endl;
cout << "请输入一条边依附的顶点,如 a b" << endl;
for (k = 0; k < G.arcnum; ++k) { //输入各边，构造邻接表
VerTexType v1, v2;
int i, j;
cout << "请输入第" << (k + 1) << "条边依附的顶点:";
cin >> v1 >> v2; //输入一条边依附的两个顶点
i = LocateVex(G, v1); j = LocateVex(G, v2);
//确定v1和v2在G中位置，即顶点在G.vertices中的序号
ArcNode* p1 = new ArcNode; //生成一个新的边结点*p1
p1->adjvex = j; //邻接点序号为j
p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1;
//将新结点*p1插入顶点vi的边表头部
ArcNode* p2 = new ArcNode; //生成另一个对称的新的边结点*p2
p2->adjvex = i; //邻接点序号为i
p2->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p2;
//将新结点*p2插入顶点vj的边表头部
}//for
return OK;
}//CreateUDG
// 自己的写法
void addEdge(const V &src, const V &dst, const W &w)
{
int dsti = getVertexIndex(dst);
int srci = getVertexIndex(src);
Edge *eg = new Edge(dsti, w);
eg->next = _linkTable[srci]; // 头插，初始化的边表都是空指针，便于节省空间
_linkTable[srci] = eg;
if (Direction == false)
{
Edge *eg1 = new Edge(srci, w);
eg1->next = _linkTable[dsti];
_linkTable[dsti] = eg1;
}
}
①若 G G G为无向图，则所需的存储空间为 O ( ∣ V ∣ + 2 ∣ E ∣ ) O(\left|V|+2|E\right|) O(∣V∣+2∣E∣)；若 G G G为有向图，则所需的存储空间为 O ( ∣ V ∣ + ∣ E ∣ ) O(\left|V|+|E\right|) O(∣V∣+∣E∣)。前者的倍数2是由于无向图中,每条边在邻接表中出现了两次
②对于稀疏图，采用邻接表表示将极大地节省存储空间。
③在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为 O ( n ) O(n) O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。
④在无向图的邻接表中，求某个顶点的度只需计算其邻接表中的边表结点个数。在有向图的邻接表中，求某个顶点的出度只需计算其邻接表中的边表结点个数；但求某个顶点的入度则需遍历全部的邻接表，统计邻接点(adivex)域为x的边表结点个数。所以求有向图某个顶点的度需要遍历整个邻接表。
⑤图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。
此外还有临界多重表存储无向图，十字链表存储有向图，但不常用。
3. 图的遍历
3.1 广度优先遍历
广度优先搜索(Breadth-First-Search,BFS)类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点 v v v，接着由 v v v出发，依次访问，的各个未访问过的邻接顶点 w 1 , w 2 , . . . , w i w_1,w_2,...,w_i w1,w2,...,wi，然后依次访问 w 1 , w 2 , . . . , w i w_1,w_2,...,w_i w1,w2,...,wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。Dijkstra单源最短路径算法和 Prim 最小生成树算法也应用了类似的思想。
换句话说，广度优先搜索遍历图的过程是以 v v v为起始点，由近至远依次访问和 v v v有路径相通且路径长度为 1.2.…的顶点。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。
为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。广度优先搜索算法的代码如下：
严尉敏教材写法：
// 邻接表
// 非联通图BFS
void BFSTraverse(struct ALGraph *G)
{
for (v=0; v<G.vexnum; v++) visited[v]=FALSE;
InitQueue(Q);
for (v=0; v<G.vexnum; v++)
if (!visited[v]) {
visited[v]=TRUE; Visit(v);
EnQueue(Q, v);
While (!QueueEmpty(Q)) {
DeQueue(Q, u);
for (w=G.vertices[u].firstarc; (w!=NULL); w=w->nextarc)
if (!visited[w->adjvex]) {
visited[w->adjvex]=TRUE; Visit(w->adjvex);
EnQueue(Q, w->adjvex)
} //if
} // while
}//if
}
// 邻接矩阵
void BFS(MGraph, int i)
{
visit(i);
visited[i] = true;
EnQueue(Q, i);
while (!IsEmpyt(Q))
{
DeQueue(Q, v);
for (w = 0; w < G.vexnum; w++)
{
if (visited[w] == false && G.edge[v][w] == 1)
{
visit(w);
visited[w] = true;
EnQueue(Q, w);
}
}
}
}
我的写法详见附录。
时间复杂度分析：
邻接矩阵： O （ ∣ V ∣ 2 ） O（\left|V\right|^2） O（∣V∣2）
邻接表： O ( ∣ V ∣ + ∣ E ∣ ) O(\left|V|+|E\right|) O(∣V∣+∣E∣)
空间复杂度： O ( ∣ V ∣ ) O(\left|V\right|) O(∣V∣)
下图的BFS为abcdefgh
3.2 深度优先遍历
与广度优先搜索不同，深度优先搜索(Depth-First-Search，DFS)类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点，然后由 v v v出发，访问与 v v v邻接且未被访问的任意一个顶点 w 1 w_1 w1，再访问与 w 1 w_1 w1邻接且未被访问的任意一个顶点 w 2 w_2 w2……重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。
// 邻接表
void DFSTraverse(Graph G)
{
for(int i=0;i<G.vexnum;i++)
visited[i]=true;
for(int i=0;i<G.vexnum;i++)
{
if(!visited[i])
DFS(G,i);
}
}
void DFS(ALGraph G,int i)
{
visit(i);
visited[i]=true;
for(p=G.vertices[i].firstarc;p;p=p->next)
{
j=p->adjvex;
if(!visited[j])
DFS(G,j);
}
}
// 邻接矩阵
void DFS(MGraph G, int i)
{
visit(i);
visited[i] = true;
for (int j = 0; j < G.vexnum; j++)
{
if (!visited[j] && G.edge[i][j] != 0)
DFS(G, j)
}
}
我的写法详见附录。
时间复杂度分析：
邻接矩阵： O （ ∣ V ∣ 2 ） O（\left|V\right|^2） O（∣V∣2）
邻接表： O ( ∣ V ∣ + ∣ E ∣ ) O(\left|V|+|E\right|) O(∣V∣+∣E∣)
空间复杂度： O ( ∣ V ∣ ) O(\left|V\right|) O(∣V∣)
下图的DFS为abdehcfg
图遍历的应用：
| 连通图的生成树 | DFS/BFS |
|---|---|
| 非连通图的生成森林 | DFS/BFS |
| 连通性检测 | DFS/BFS |
| 无向图环路检测 | DFS/BFS |
| 有向图环路检测 | DFS |
| 顶点之间可达性检测/路径求解 | DFS/BFS |
| 顶点之间的最短距离 | BFS |
| 直径 | BFS |
| 拓扑排序 | DFS |
4. 图的应用
4.1 最小生成树
4.1.1 最小生成树定义
一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的 n − 1 n-1 n−1条边，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图 G = ( V , E ) G=(V,E) G=(V,E)，生成树不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树），称为 G G G的最小生成树(Minimum-Spanning-Tree, MST)。
最小生成树有以下性质：
- 若图中存在权值相同的边，最小生成树可能不唯一；当权值互不相等，最小生成树是唯一的；若无向连通图的边数比 顶点数少1，它的最小生成树是它本身。
- 最小生成树不唯一。但是它的边的权值的和是唯一的且是最小的。
- 最小生成树的边数为定点数减1
构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质：假设 G = ( V , E ) G=(V,E) G=(V,E)是一个带权连通无向图， U U U是顶点集 V V V的一个非空子集。若 ( u , v ) (u,v) (u,v)是一条具有最小权值的边，其中 u ∈ U u\in U u∈U , v ∈ V − U v\in V-U v∈V−U，则必存在一棵包含边( ( u , v ) (u,v) (u,v)的最小生成树。
伪代码如下：
GENERIC_MST(G){
T=NULL;
while T 未形成一棵生成树;
do 找到一条最小代价边(u, v)并且加入T后不会产生回路;
T=T U (u, v);
}
通用算法每次加入一条边以逐渐形成一棵生成树，下面介绍两种实现上述通用算法的途径。
4.1.2 Prim算法
Prim算法与Dijkstra算法非常类似，后续会讲到。
Prim算法构造最小生成树的过程如下图所示。初始时从图中任取一顶点(如顶点1)加入树 T T T，此时树中只含有一个顶点，之后选择一个与当前 T T T中顶点集合距离最近的顶点，并将该顶点和相应的边加入 T T T，每次操作后T中的顶点数和边数都增1。以此类推，直至图中所有的顶点都并入 T T T，得到的 T T T就是最小生成树。此时 T T T中必然有 n − 1 n-1 n−1条边。
通俗点说就是：从一个顶点出发，在保证不形成回路的前提下，每找到并添加一条最短的边，就把当前形成的连通分量当做一个整体或者一个点看待，然后重复“找最短的边并添加”的操作。
下图是一个详细推理过程：
下面是基于课本的代码实现，附录中我使用了优先队列优化。
// 辅助数组的定义，用来记录从顶点集U到V-U的权值最小的边
struct
{
VerTexType adjvex; // 最小边在U中的那个顶点
ArcType lowcost; // 最小边上的权值
} closedge[MVNum];
//- - - - -图的邻接表存储表示- - - - -
typedef char VerTexType; // 假设顶点的数据类型为字符型
typedef int ArcType; // 假设边的权值类型为整型
typedef struct
{
VerTexType vexs[MVNum]; // 顶点表
ArcType arcs[MVNum][MVNum]; // 邻接矩阵
int vexnum, arcnum; // 图的当前点数和边数
} AMGraph;
int Min(AMGraph G)
{
// 返回权值最小的点
int i;
int index = -1;
int min = MaxInt;
for (i = 0; i < G.vexnum; ++i)
{
if (min > closedge[i].lowcost && closedge[i].lowcost != 0)
{
min = closedge[i].lowcost;
index = i;
}
} // for
return index;
} // Min
void MiniSpanTree_Prim(AMGraph G, VerTexType u)
{
// 无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边
int k, j, i;
VerTexType u0, v0;
k = LocateVex(G, u); // k为顶点u的下标
for (j = 0; j < G.vexnum; ++j)
{ // 对V-U的每一个顶点vi，初始化closedge[i]
if (j != k)
{
closedge[j].adjvex = u;
closedge[j].lowcost = G.arcs[k][j]; //{adjvex, lowcost}
} // if
} // for
closedge[k].lowcost = 0; // 初始，U = {u}
for (i = 1; i < G.vexnum; ++i)
{ // 选择其余n-1个顶点，生成n-1条边(n= G.vexnum)
k = Min(G); // 每一次选取最小的边
// 求出T的下一个结点：第k个顶点，closedge[k]中存有当前最小边
u0 = closedge[k].adjvex; // u0为最小边的一个顶点，u0∈U
v0 = G.vexs[k]; // v0为最小边的另一个顶点，v0∈V-U
cout << "边 " << u0 << "--->" << v0 << endl; // 输出当前的最小边(u0, v0)
closedge[k].lowcost = 0; // 第k个顶点并入U集
for (j = 0; j < G.vexnum; ++j) // 更新边表，将与该顶点连接的边添加，如果比当前的小就更新
if (G.arcs[k][j] < closedge[j].lowcost)
{ // 新顶点并入U后重新选择最小边
closedge[j].adjvex = G.vexs[k];
closedge[j].lowcost = G.arcs[k][j];
} // if
} // for
} // MiniSpanTree_Prim
Prim算法的时间复杂度为 O ( ∣ V ∣ 2 ) O(\left|V\right|^2) O(∣V∣2)，不依赖于边数，适用于求解稠密图的最小生成树。
Prim算法可以使用优先队列优化，见附录，优先队列便可以不用每次寻找最小值，优先队列的堆顶就是最小值。时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ l o g ∣ V ∣ ) O(\left|V|+|E|log|V\right|) O(∣V∣+∣E∣log∣V∣)
4.1.3 Kruskal算法
与Prim算法从顶点开始扩展最小生成树不同，Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。 Kruskal算法构造最小生成树的过程如下图所示。初始时为只有 n n n个顶点而无边的非连通图 T = { V , { } } T=\{V,\{\}\} T={V,{}}，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 T T T中不同的连通分量上，则将此边加入 T T T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至 T T T中所有顶点都在一个连通分量上。
Kruskal算法使用并查集来实现，这里不赘述其代码了。
在 Kruskal算法中，最坏情况需要对 ∣ E ∣ \left|E\right| ∣E∣条边各扫描一次。通常采用堆来存放边的集合，每次选择最小权值的边需要 O ( l o g ∣ E ∣ ) O(log\left|E\right|) O(log∣E∣)的时间；每次使用并查集来快速判断两个顶点是否属于一个集合所需的时间为 O ( α ∣ V ∣ ) O(\alpha \left|V\right|) O(α∣V∣)， α ∣ V ∣ \alpha \left|V\right| α∣V∣的增长极其缓慢，可视为常数。算法的总时间复杂度为 O ( ∣ E ∣ l o g ∣ E ∣ ) O(\left|E|log|E\right|) O(∣E∣log∣E∣)，不依赖于 ∣ V ∣ \left|V\right| ∣V∣，因此 Kruskal 算法适合于边稀疏而顶点较多的图。
4.2 最短路径
4.2.1 最短路径定义
在网图和非网图中，最短路径的含义是不同的。由于非网图它没有边上的权值，所谓的最短路径，其实就是指两顶点之间经过的边数最少的路径；而对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。
求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。带权有向图 G G G的最短路径问题一般可分为两类：一是单源最短路径，即求图中某一顶点到其他各顶点的最短路径，可通过经典的Diikstra(迪杰斯特拉)算法求解;二是求每对顶点间的最短路径，可通过Floyd(弗洛伊德)算法来求解。
4.2.2 Dijkstra算法
Dijkstra算法用于构建单源点的最短路径—，即图中某个点到任何其他点的距离都是最短的。例如，构建地图应用时查找自己的坐标离某个地标的最短距离。可以用于有向图，但是不能存在负权值。
通俗点说，这个迪杰斯特拉(Dijkstra) 算法，它并不是一下子求出了 v s r c v_{src} vsrc到 v d s t v_{dst} vdst的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。它是基于贪心策略来进行的。
Dijkstra算法设置一个集合 S S S记录已求得的最短路径的顶点。
在构造的过程中还设置了个辅助数组:
dist[]：记录从源点 v 0 v_0 v0到其他各顶点当前的最短路径长度，它的初态为：若从 v 0 v_0 v0到 v i v_i vi有弧，则dist[i]为弧上的权值；否则置dist[i]为 ∞ \infty ∞。
Dijkstra 算法的步骤如下：
1）初始化：集合 S S S初始为 0 {0} 0, dist []的初始值 d i s t [ i ] = a r c s [ 0 ] [ i ] dist [i]=arcs [0] [i] dist[i]=arcs[0][i], i = 1 , 2 , ⋯ , n − 1 i=1,2, \cdots, n-1 i=1,2,⋯,n−1 。
2）从顶点集合 V − S V-S V−S中选出 v j v_j vj, 满足 d i s t [ j ] = M i n { d i s t [ i ] ∣ v i ∈ V − S } , v j dist [j]=Min\{dist [i]| \left.v_i \in V-S\right\}, v_j dist[j]=Min{dist[i]∣vi∈V−S},vj 就是当前求得的一条从 v 0 v_0 v0出发的最短路径的终点, 令 S = S ∪ { j } S=S \cup\{j\} S=S∪{j} 。
3）修改从 v 0 v_0 v0出发到集合 V − S V-S V−S上任意一个顶点 v k v_k vk可达的最短路径长度：若 d i s t [ j ] + arcs [ j ] [ k ] < dist [ k ] dist[j]+ \operatorname{arcs}[j][k]<\operatorname{dist}[k] dist[j]+arcs[j][k]<dist[k] ，则更新 d i s t [ k ] = d i s t [ j ] + arcs [ j ] [ k ] dist[k]=dist[j]+\operatorname{arcs}[j][k] dist[k]=dist[j]+arcs[j][k]。
4）重复 2)~3）操作共 n − 1 n-1 n−1次，直到所有的顶点都包含在集合 S S S中。
步骤 3）也就是开头留下的疑问，每当一个顶点加入集合 S S S后，可能需要修改源点 v 0 v_0 v0到集合 V − S V-S V−S 中可达顶点当前的最短路径长度, 下面举一简单例子证明。如下图所示, 源点为 v 0 v_0 v0, 初始时 S = { v 0 } , dist [ 1 ] = 3 , dist [ 2 ] = 7 S=\left\{v_0\right\}, \operatorname{dist}[1]=3, \operatorname{dist}[2]=7 S={v0},dist[1]=3,dist[2]=7, 当将 v 1 v_1 v1并入集合 S S S 后， d i s t [ 2 ] dist [2] dist[2]需要更新为 4 。
下面是一个Dijkstra算法进行的流程。
基于课本的代码如下：
void Dijkstra(MGraph G, int s)
{
// 从顶点s生成到其他顶点的最短路径
for (p = G.vertices[s].firstarc; p; p = p->nextarc)
D[p->adjvex] = {s, p->weight}; // weight边权值
D[s].lowcost = 0; // 初始，S＝{s}
visited[s] = true;
for (i = 1; i < G.vexnum; ++i)
{
k = minimum(D);
visited[k] = true; // 第k顶点并入S集
for (p = G.vertices[k].firstarc; p; p = p->nextarc)
if (D[k].lowcost + p->weight < D[p->adjvex].lowcost)
D[p->adjvex] = {k, D[k].lowcost + p->weight};
}
}
显然，Dijkstra算法是基于贪心策略的。使用邻接矩阵时，时间复杂度为 O ( ∣ V ∣ 2 ) O(\left|V\right|^2) O(∣V∣2)，附录中我的代码使用了优先队列优化。
我们能够看到Prim算法的流程和Dijkstra非常相似，都是基于贪心策略，那么他们有什么区别呢？
①目的不同：Dijkstra 算法的目的是构建单源点的最短路径树；Prim 算法的目的是构建最小生成树。
②算法思路略有不同:Prim 算法从一个点开始，每次选择权值最小的边，将其连接到已构建的生成树上，直至所有顶点都已加入；而 Dijkstra 算法每次找出到源点距离最近且未归入集合的点，并把它归入集合，同时以这个点为基础更新从源点到其他所有顶点的距离。
③适用的图不同：Prim 算法只能用于带权无向图:Diikstra算法可用于带权有向图或带权无向图。
4.2.3 Floyd算法
Floyd算法的基本思想是：定义一个n阶方阵序列 A ( − 1 ) , A ( 0 ) , . . . , A ( n − 1 ) A^{(-1)},A^{(0)},...,A^{(n-1)} A(−1),A(0),...,A(n−1)其中，
A ( − 1 ) [ i ] [ j ] = a r c s [ i ] [ j ] A^{(-1)}[i][j]=arcs[i][j] A(−1)[i][j]=arcs[i][j]
A ( k ) [ i ] [ j ] = M i n { A ( k − 1 ) [ i ] [ j ] , A ( k − 1 ) [ i ] [ k ] + A ( k − 1 ) [ k ] [ j ] , k = 0 , 1 , . . . , n − 1 } A^{(k)}[i][j]=Min\{A^{(k-1)}[i][j],A^{(k-1)}[i][k]+A^{(k-1)}[k][j],k=0,1,...,n-1\} A(k)[i][j]=Min{A(k−1)[i][j],A(k−1)[i][k]+A(k−1)[k][j],k=0,1,...,n−1}
式中， ， A ( 0 ) [ i ] [ j ] ，A^{(0)}[i][j] ，A(0)[i][j]是从顶点 v i v_i vi到、中间顶点的序号不大于k的最短路径的长度。Floyd算法是一个迭代的过程，每迭代一次，在从 v i v_i vi到 v j v_j vj的最短路径上就多考虑了一个顶点；经过 n n n次迭代后，所得到的 A ( n − 1 ) [ i ] [ j ] A^{(n-1)}[i][j] A(n−1)[i][j]就是 v i v_i vi 到 v j v_j vj 的最短路径长度，即方阵 A ( n − 1 ) A^{(n-1)} A(n−1)中就保存了任意一对顶点之间的最短路径长度。
Floyd算法流程如下：
代码如下：
int graph[NUM][NUM];
int n, m;
void Floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (graph[i][j] > graph[i][k] + graph[k][j])
graph[i][j] = graph[i][k] + graph[k][j]);
}
Floyd算法的时间复杂度为 O ( ∣ V ∣ 3 ) O(\left|V\right|^3) O(∣V∣3)，但是代码简单。
Floyd算法允许图中有负权值的边，但不允许有负边回路。
BFS、Dijksra算法、Floyd算法比较如下：
4.3 拓扑排序
4.3.1 拓扑排序定义
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网( Activity On VertexNetwork)。
AOV 网：若用有向无环图表示一个工程，其顶点表示活动，用有向边 < V i , V j > <V_i,V_j> <Vi,Vj>表示活动 V i V_i Vi必须先于活动 V j V_j Vj进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，简称 AOV 网。在 AOV网中，活动 V i V_i Vi是活动 V j V_j Vj的直接前驱， V j V_j Vj是的 V i V_i Vi直接后继，这种前驱和后继关系具有传递性，且任何活动不能以它自己作为自己的前驱或后继。
拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时称为该图的一个拓扑排序:
- 每个顶点出现且只出现一次。
- 若顶点A在序列中排在顶点B的前面，则在图中不存在从B到4的路径。
或定义为:拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中B出现在A的后面。每个AOV网都有一个或多个拓扑排序序列。
4.3.2 拓扑排序算法
对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：
①从AOV网中选择一个没有前驱的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。
上图所示为拓扑排序过程的示例。每一轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为{ 1 , 2 , 4 , 3 , 5 }。
拓扑排序的代码如下：
bool TopologicalSort(Graph G){
InitStack(S); //初始化栈，存储入度为0的顶点
// indegree要事先计算好
for(int i=0; i<G.vexnum; i++){
if(indegree[i] == 0){
Push(S, i); //将所有入度为0的顶点进栈
}
}
int count = 0; //计数，记录当前已经输出的顶点数
while(!IsEmpty(S)){ //栈不空，则存在入度为0的顶点
Pop(S, i); //顶点元素出栈
printf("%d ", i); //输出顶点i
count++;
for(p=G.vertices[i].finstarc; p; p=p->nextarc){
//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
v = p->adjvex;
if(!--indegree[v]){
Push(S, v); //入度为0，则入栈
}
}
}
if(count < G.vexnum){
return false; //输出顶点少了，有向图中有回路，排序失败
}else{
return true; //拓扑排序成功
}
}
用拓扑排序算法处理AOV网时，应注意以下问题:
①入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
②若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
③由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成AOV网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。
4.4 关键路径
4.4.1 关键路径定义
拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网。AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中的边有权值；而AOV网中的边无权值，仅表示顶点之间的前后关系。
AOE网具有以下性质：
①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始；网中也仅存在一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。
完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。
下面先给出在寻找关键路径时的几个定义：
事件 v k v_k vk最早的发生时间 v e ( k ) v_e(k) ve(k)
它是指从源点 v 1 v_1 v1到顶点 v k v_k vk的最长路径长度。事件 v k v_k vk的最早发生时间决定了所有从 v k v_k vk开始的活动能够开工的最早时间。可用下面的递推公式来计算：
v e ( 源点 ) = 0 v_e(源点)=0 ve(源点)=0
v e ( k ) = Max { v e ( j ) + W e i g h t ( v j , v k ) } , v k v_{e}(k)=\operatorname*{Max}\{v_{e}(j)+Weight(v_j,v_k)\},v_k ve(k)=Max{ve(j)+Weight(vj,vk)},vk 为 v j v_j vj的任意后继， W e i g h t ( v j , v k ) Weight (v_j,v_k) Weight(vj,vk)表示 < v j , v k > <v_j,v_k> <vj,vk>上的权值
事件 v k v_k vk最迟的发生时间 v l ( k ) v_l(k) vl(k)
它是指在不推迟整个工程完成的前提下，即保证它的后继事件 v j v_j vj在其最迟发生时间 v l ( j ) v_l{(j)} vl(j)能够发生时，该事件最迟必须发生的时间。可用下面的递推公式来计算：
v l ( 汇点 ) = v e ( 汇点 ) v_{l}(汇点)=v_e(汇点) vl(汇点)=ve(汇点)
v l ( k ) = M i n { v l ( j ) − W e i g h t ( v k , v j ) } v_{l}(k)=Min\left\{v_l(j)-{Weight}(v_k,v_j)\right\} vl(k)=Min{vl(j)−Weight(vk,vj)}， v k v_k vk为 v j v_j vj的任意前驱
活动 a i a_i ai的最早开始时间 e ( i ) e(i) e(i)
活动的数量是弧的数量。
它是指该活动弧的起点所表示的事件的最早发生时间。若边 < v k , v j > <v_k,v_j> <vk,vj>表示活动 a i a_i ai，则有 e ( i ) = v e ( k ) e(i)=v_e(k) e(i)=ve(k)
活动 a i a_i ai的最迟开始时间 l ( i ) l(i) l(i)
它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边 < v k , v j > <v_k,v_j> <vk,vj>表示活动 a i a_i ai，则有 l ( i ) = v l ( j ) − W e i g h t ( v k , v j ) l(i)=v_l(j)- Weight(v_k,v_j) l(i)=vl(j)−Weight(vk,vj)。
一个活动 a i a_i ai的最迟开始时间 l ( i ) l(i) l(i)和其最早开始时间 e ( i ) e(i) e(i)的差额 d ( i ) = l ( i ) − e ( i ) d(i)=l(i)-e(i) d(i)=l(i)−e(i)
它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动 a i a_i ai可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称 l ( i ) − e ( i ) l(i)-e(i) l(i)−e(i) 即 l ( i ) = e ( i ) l(i)=e(i) l(i)=e(i)的活动 a i a_i ai是关键活动。
4.4.2 关键路径算法
对于关键路径，需要注意以下几点:
①关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
②网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
附录
附录主要为图相关代码，本人将图封装为类，实现了大多数的图算法，有邻接矩阵和邻接表：
#pragma once
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <string>
#include <algorithm>
/*
*图的表示方式 G=(V,E) V是顶点 E是边
*
*/
using namespace std;
template <class V, class W, bool Direction = false> // Direction为是否有向
class Graph_Matrix
{
typedef Graph_Matrix<V, W, Direction> Self;
public:
Graph_Matrix(const V *vertex, size_t n) // 初始化顶点
{
// _vertex.reserve(n);
for (int i = 0; i < n; i++)
{
_vertex.push_back(vertex[i]);
_vIndex[vertex[i]] = i;
}
// 初始化邻接矩阵
_matrix.resize(n);
for (auto &e : _matrix)
{
e.resize(n, INT_MAX);
}
for (int i = 0; i < n; i++)
{
_matrix[i][i] = 0;
}
}
// 以邻接矩阵初始化
Graph_Matrix(const std::vector<std::vector<W>> &m)
{
for (int i = 0; i < m.size(); i++)
{
for (int j = 0; j < m[0].size(); j++)
{
_matrix[i][j] = m[i][j];
}
}
}
int getVertexIndex(const V &v)
{
auto ret = _vIndex.find(v);
if (ret != _vIndex.end())
{
return ret->second;
}
else
{
std::cerr << "error, don't have this vertex\n";
return 0;
}
}
void addEdge(const V &src, const V &dst, const W &w)
{
int srci = getVertexIndex(src);
int dsti = getVertexIndex(dst);
_matrix[srci][dsti] = w;
if (Direction == false)
{
_matrix[dsti][srci] = w;
}
}
void Print()
{
// 打印顶点和下标映射关系
std::cout << "顶点和下标映射关系: ";
for (size_t i = 0; i < _vertex.size(); i++)
{
std::cout << _vertex[i] << "-" << i << " ";
}
std::cout << std::endl
<< std::endl;
std::cout << "邻接矩阵:\n";
std::cout << " ";
for (size_t i = 0; i < _vertex.size(); ++i)
{
std::cout << i << " ";
}
std::cout << std::endl;
// 打印邻接矩阵
for (size_t i = 0; i < _matrix.size(); ++i)
{
std::cout << i << " ";
for (size_t j = 0; j < _matrix[i].size(); ++j)
{
if (_matrix[i][j] != INT_MAX)
std::cout << _matrix[i][j] << " ";
else
std::cout << "#" << " ";
}
std::cout << std::endl;
}
std::cout << std::endl;
// 打印所有的边
std::cout << "所有边的情况:\n";
for (size_t i = 0; i < _matrix.size(); ++i)
{
for (size_t j = 0; j < _matrix[i].size(); ++j)
{
if (i != j && _matrix[i][j] != INT_MAX)
{
std::cout << _vertex[i] << "-" << _vertex[j] << ":" << _matrix[i][j] << " ";
}
}
std::cout << std::endl;
}
// 打印每个顶点的度
std::cout << "\n所有顶点的度:\n";
if (Direction == false) // 无向图
{
for (int i = 0; i < _vertex.size(); i++)
{
int degree = 0;
for (int j = 0; j < _vertex.size(); j++)
{
if (_matrix[i][j] != INT_MAX && i != j)
{
degree++;
}
}
std::cout << "顶点 " << _vertex[i] << " 的度为 " << degree << std::endl;
}
}
else // 有向图
{
for (int i = 0; i < _vertex.size(); i++)
{
int in_degree = 0;
int out_degree = 0;
for (int j = 0; j < _vertex.size(); j++)
{
if (_matrix[j][i] != INT_MAX && j != i)
{
in_degree++;
}
if (_matrix[i][j] != INT_MAX && i != j)
{
out_degree++;
}
}
std::cout << "顶点 " << _vertex[i] << " 的入度为 " << in_degree << "，出度为 " << out_degree << std::endl;
}
}
std::cout << std::endl;
}
void BFS(const V &src) // 从哪一个开始BFS
{
int srci = getVertexIndex(src);
std::vector<bool> visited(_vertex.size(), false);
std::queue<int> q;
std::cout << "The graph from point " << _vertex[srci] << "'s BFS: " << std::endl;
q.push(srci);
visited[srci] = true;
std::cout << srci << src << " ";
while (!q.empty())
{
int font = q.front();
q.pop();
for (int i = 0; i < _vertex.size(); i++)
{
if (_matrix[font][i] != INT_MAX && visited[i] == false)
{
visited[i] = true;
std::cout << i << _vertex[i] << " ";
q.push(i);
}
}
// std::cout << std::endl;
}
std::cout << std::endl
<< std::endl;
}
void DFS(const V &src)
{
int srci = getVertexIndex(src);
std::cout << "The graph from point " << _vertex[srci] << "'s DFS: " << std::endl;
std::vector<bool> visited(_vertex.size(), false);
_DFS(srci, visited);
std::cout << std::endl
<< std::endl;
}
void Prim(const V &src)
{
if (Direction)
{
std::cerr << "Prim's algorithm is not applicable to directed graphs." << std::endl;
return;
}
int srci = getVertexIndex(src);
std::vector<W> minWeight(_vertex.size(), INT_MAX);
std::vector<int> parent(_vertex.size(), -1); // 记录最小生成树的双亲节点
std::vector<bool> visited(_vertex.size(), false);
minWeight[srci] = 0;
// 使用优先队列优化，greater是变小堆
std::priority_queue<std::pair<W, int>, std::vector<std::pair<W, int>>, std::greater<std::pair<W, int>>> pq;
pq.push({minWeight[srci], srci});
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (visited[u])
continue;
visited[u] = true;
for (int i = 0; i < _vertex.size(); i++)
{
if (_matrix[u][i] != INT_MAX && !visited[i] && _matrix[u][i] < minWeight[i])
{
minWeight[i] = _matrix[u][i]; // 更新
parent[i] = u;
pq.push({minWeight[i], i});
}
}
}
std::cout << "Prim's MST from " << src << ": " << "\n";
for (int i = 0; i < _vertex.size(); i++)
{
if (parent[i] != -1)
{
std::cout << _vertex[parent[i]] << " - " << _vertex[i] << " : " << _matrix[parent[i]][i] << "\n";
}
}
std::cout << std::endl;
}
W Dijkstra(const V &src, const V &dst)
{
int srci = getVertexIndex(src);
int dsti = getVertexIndex(dst);
std::vector<W> dist(_vertex.size(), INT_MAX);
std::vector<int> parent(_vertex.size(), -1); // 记录路径
std::vector<bool> visited(_vertex.size(), false);
dist[srci] = 0;
// 使用优先队列优化，greater是变小堆
std::priority_queue<std::pair<W, int>, std::vector<std::pair<W, int>>, std::greater<std::pair<W, int>>> pq;
pq.push({dist[srci], srci});
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (visited[u])
continue;
visited[u] = true;
for (int i = 0; i < _vertex.size(); i++)
{
if (_matrix[u][i] != INT_MAX && !visited[i] && dist[u] + _matrix[u][i] < dist[i])
{
dist[i] = dist[u] + _matrix[u][i]; // 与prime算法的区别
parent[i] = u;
pq.push({dist[i], i});
}
}
}
// 打印路径
std::cout << "Dijkstra's shortest path from " << src << " to " << dst << ": ";
if (dist[dsti] == INT_MAX)
{
std::cout << "No path found." << std::endl;
return INT_MAX;
}
std::vector<int> path;
for (int v = dsti; v != -1; v = parent[v])
{
path.push_back(v);
}
std::reverse(path.begin(), path.end());
for (int i = 0; i < path.size(); ++i)
{
std::cout << _vertex[path[i]];
if (i != path.size() - 1)
{
std::cout << " -> ";
}
}
std::cout << std::endl;
return dist[dsti];
}
private:
void _DFS(int srci, std::vector<bool> &visited)
{
std::cout << srci << _vertex[srci] << " ";
visited[srci] = true;
for (int i = 0; i < _vertex.size(); i++)
{
if (visited[i] == false && _matrix[srci][i] != INT_MAX)
{
_DFS(i, visited);
}
}
}
// std::vector<std::pair<V,int>> _vIndex;
std::unordered_map<V, int> _vIndex; // 下标索引
std::vector<V> _vertex; // 顶点
std::vector<std::vector<W>> _matrix; // 矩阵存储
};
#pragma once
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>
template <class W>
struct LinkEdge
{
int _dstIndex;
LinkEdge<W> *next;
W _w;
LinkEdge(int dsti, const W &w) : _dstIndex(dsti), _w(w), next(nullptr)
{
}
};
template <class V, class W, bool Direction = false>
class Graph_Link
{
typedef LinkEdge<W> Edge;
public:
Graph_Link(const V *vertex, int n)
{
for (int i = 0; i < n; i++)
{
_vertex.push_back(vertex[i]);
_vIndex[vertex[i]] = i;
}
_linkTable.resize(n, nullptr);
}
int getVertexIndex(const V &v)
{
auto ret = _vIndex.find(v);
if (ret != _vIndex.end())
{
return ret->second;
}
else
{
std::cerr << "error, don't have this vertex\n";
return 0;
}
}
void addEdge(const V &src, const V &dst, const W &w)
{
int dsti = getVertexIndex(dst);
int srci = getVertexIndex(src);
Edge *eg = new Edge(dsti, w);
eg->next = _linkTable[srci]; // 头插，初始化的边表都是空指针，便于节省空间
_linkTable[srci] = eg;
if (Direction == false)
{
Edge *eg1 = new Edge(srci, w);
eg1->next = _linkTable[dsti];
_linkTable[dsti] = eg1;
}
}
void Print()
{
// 打印顶点和下标映射关系
std::cout << "顶点和下标映射关系: ";
for (size_t i = 0; i < _vertex.size(); i++)
{
std::cout << _vertex[i] << "-" << i << " ";
}
std::cout << std::endl
<< std::endl;
std::cout << "邻接表表示: \n";
for (size_t i = 0; i < _linkTable.size(); ++i)
{
std::cout << _vertex[i] << "[" << i << "]->";
Edge *cur = _linkTable[i];
while (cur)
{
std::cout << "[" << _vertex[cur->_dstIndex] << ":" << cur->_dstIndex << ":" << cur->_w << "]->";
cur = cur->next;
}
std::cout << "nullptr" << std::endl;
}
std::cout << std::endl;
// 打印所有顶点的度:
std::cout << "所有顶点的度:\n";
if (Direction == false) // 无向图的度
{
for (size_t i = 0; i < _vertex.size(); ++i)
{
int degree = 0;
Edge *cur = _linkTable[i];
while (cur)
{
degree++;
cur = cur->next;
}
std::cout << "顶点 " << _vertex[i] << " 的度为 " << degree << std::endl;
}
}
else // 有向图的度，入度、出度
{
// 计算每个顶点的入度
std::vector<int> in_degree(_vertex.size(), 0);
for (size_t i = 0; i < _linkTable.size(); ++i)
{
Edge *cur = _linkTable[i];
while (cur)
{
in_degree[cur->_dstIndex]++;
cur = cur->next;
}
}
// 打印每个顶点的入度和出度
for (size_t i = 0; i < _vertex.size(); ++i)
{
int out_degree = 0;
Edge *cur = _linkTable[i];
while (cur)
{
out_degree++;
cur = cur->next;
}
std::cout << "顶点 " << _vertex[i] << " 的入度为 " << in_degree[i] << "，出度为 " << out_degree << std::endl;
}
}
std::cout << std::endl;
}
void BFS(const V &src)
{
int srci = getVertexIndex(src);
std::vector<bool> visited(_vertex.size(), false);
std::queue<int> q;
std::cout << "The graph from point " << _vertex[srci] << "'s BFS: " << std::endl;
q.push(srci);
visited[srci] = true;
while (!q.empty())
{
int font = q.front();
q.pop();
std::cout << _vertex[font] << " ";
for (Edge *cur = _linkTable[font]; cur != nullptr; cur = cur->next)
{
if (!visited[cur->_dstIndex])
{
visited[cur->_dstIndex] = true;
q.push(cur->_dstIndex);
}
}
}
std::cout << std::endl
<< std::endl;
}
void DFS(const V &src)
{
int srci = getVertexIndex(src);
std::cout << "The graph from point " << _vertex[srci] << "'s DFS: " << std::endl;
std::vector<bool> visited(_vertex.size(), false);
_DFS(srci, visited);
std::cout << std::endl
<< std::endl;
}
void Prim(const V &src)
{
int srci = getVertexIndex(src);
std::vector<W> key(_vertex.size(), INT_MAX);
std::vector<int> parent(_vertex.size(), -1);
std::vector<bool> inMST(_vertex.size(), false);
key[srci] = 0;
// 优先队列，存储 (key值, 顶点索引)
std::priority_queue<std::pair<W, int>, std::vector<std::pair<W, int>>, std::greater<std::pair<W, int>>> pq;
pq.push({0, srci});
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (inMST[u])
continue;
inMST[u] = true;
for (Edge *cur = _linkTable[u]; cur != nullptr; cur = cur->next)
{
int v = cur->_dstIndex;
W weight = cur->_w;
if (!inMST[v] && weight < key[v])
{
key[v] = weight;
parent[v] = u;
pq.push({key[v], v});
}
}
}
// 打印最小生成树
std::cout << "Prim's MST starting from " << src << ": " << std::endl;
for (int i = 0; i < _vertex.size(); ++i)
{
if (i != srci && parent[i] != -1)
{
std::cout << _vertex[parent[i]] << " - " << _vertex[i] << " : " << key[i] << std::endl;
}
}
std::cout << std::endl;
}
W Dijkstra(const V &src, const V &dst)
{
int srci = getVertexIndex(src);
int dsti = getVertexIndex(dst);
std::vector<W> dist(_vertex.size(), INT_MAX);
std::vector<int> parent(_vertex.size(), -1); // 记录路径
std::vector<bool> visited(_vertex.size(), false);
dist[srci] = 0;
// 优先队列，存储 (距离, 顶点索引)
std::priority_queue<std::pair<W, int>, std::vector<std::pair<W, int>>, std::greater<std::pair<W, int>>> pq;
pq.push({0, srci});
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (visited[u])
continue;
visited[u] = true;
for (Edge *cur = _linkTable[u]; cur != nullptr; cur = cur->next)
{
int v = cur->_dstIndex;
W weight = cur->_w;
if (!visited[v] && dist[u] + weight < dist[v])
{
dist[v] = dist[u] + weight;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
// 打印路径
std::cout << "Dijkstra's shortest path from " << src << " to " << dst << ": ";
if (dist[dsti] == INT_MAX)
{
std::cout << "No path found." << std::endl;
return INT_MAX;
}
std::vector<int> path;
for (int v = dsti; v != -1; v = parent[v])
{
path.push_back(v);
}
std::reverse(path.begin(), path.end());
for (int i = 0; i < path.size(); ++i)
{
std::cout << _vertex[path[i]];
if (i != path.size() - 1)
{
std::cout << " -> ";
}
}
std::cout << std::endl;
return dist[dsti];
}
private:
void _DFS(int srci, std::vector<bool> &visited)
{
visited[srci] = true;
std::cout << _vertex[srci] << " ";
for (Edge *cur = _linkTable[srci]; cur != nullptr; cur = cur->next)
{
if (!visited[cur->_dstIndex])
_DFS(cur->_dstIndex, visited);
}
}
std::unordered_map<V, int> _vIndex;
std::vector<V> _vertex;
std::vector<Edge *> _linkTable;
};