数据结构—图

目录

一、图的定义

二、图的基本概念和术语

2.1有向图

2.2无向图

2.3简单图

2.4多重图

2.5完全图

2.6子图

2.7连通、连通图和连通分量

2.8强连通图、强联通分量

2.9生成树，生成森林

2.10顶点的度、入度和出度

2.11边的权和网

2.12稠密图、稀疏图

2.13路径、路径长度和回路

2.14简单路径、简单回路

2.15距离

2.16有向树

三、图的储存结构

3.1邻接矩阵

3.2邻接表

3.3十字链表

3.4邻接多重表

3.5边集数组

四、图的遍历

4.1深度优先遍历

4.2广度优先遍历

4.3图的遍历与图的连通性

五、最小生成树

5.1普里姆算法

5.2克鲁斯卡尔算法

六、最短路径

6.1迪杰斯特拉算法

6.2弗洛伊德算法

七、拓扑排序

7.1定义

7.2算法

八、关键路径

8.1定义

8.2算法

---

一、图的定义

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。而图是一种较线性表和树更加复杂的数据结构。

在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

图(Graph)是由顶点的有穷非空集合V(G)和顶点之间边的集合E(G)组成，通常表示为: G=(V,E)，其中，G表示个图，V是图G中顶点的集合，E是图G中边的集合。若V={v1,v2,...,vn}，则用∣V∣表示图G中顶点的个数，也称图G的阶，E={(u,v)∣u∈V,v∈V}，用|E|表示图G中边的条数。

注意:线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

二、图的基本概念和术语

2.1有向图
若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v, w>，其中v,w是顶点，v称为弧尾，w称为弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。

2.2无向图
若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v, w相关联。

2.3简单图
一个图G若满足:①不存在重复边;②不存在顶点到自身的边，则称图G为简单图。

注：数据结构中仅仅讨论简单图

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

2.5完全图（也称简单完全图）
对于无向图，∣E∣的取值范围是0到n(n−1)/2，有n(n−1)/2条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，∣E∣的取值范围是0到)n(n−1)，有n(n−1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。

2.6子图
设有两个图G=(V,E)和G'=(V',E')，若V’是V的子集，且E’是E的子集，则称G’是G的子图。若有满足V(G')=V(G)的子图G’，则称为G的生成子图。

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

2.7连通、连通图和连通分量
在无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。若一个图有n个顶点，并且边数小于n−1，则此图必是非连通图。
注意:弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图。

2.8强连通图、强连通分量
在有向图中，若从顶点v到顶点w和从顶点w到项点v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。
注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

2.9生成树、生成森林
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n,则它的生成树含n−1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

注意:包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。

2.10顶点的度、入度和出度
图中每个顶点的度定义为以该项点为一个端点的边的数目。
对于无向图，顶点v的度是指依附于该顶点的边的条数，记为TD(v)。
在具有n个顶点、e条边的无向图中，若和为2e；无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。

对于有向图,顶点v的度分为入度和出度,入度是以顶点v为终点的有向边的数目，记为ID(v); 而出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度和出度之和，即 TD(v) = ID(v) + OD(v）。

在具有n个顶点、e条边的有向图中，若和为e；即有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。

2.11边的权和网
在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

2.12稠密图、稀疏图
边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足∣E∣<∣V∣log∣V∣时，可以将G视为稀疏图。

2.13路径、路径长度和回路
当然关联的边也可以理解为路径的构成要素。路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n nn个顶点，并且有大于n − 1 n-1n−1条边，则此图一定有环。

2.14简单路径、简单回路
在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

2.15距离
从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷(∞)。

2.16有向树
一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

三、图的储存结构

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。而多重链表的方式，要么会造成很多存储单元的浪费，要么又带来操作的不便。因此，对于图来说，如何对它实现物理存储是个难题，接下来我们介绍五种不同的存储结构。

3.1邻接矩阵

图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

在这种储存方式中：

1.无向图的邻接矩阵一定是一个对称矩阵(即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的)。 因此，在实际存储邻接矩阵时只需存储上(或下)三角矩阵的元素。
2.对于无向图，邻接矩阵的第i行非零元素的个数正好是第i个顶点的度TD（vi)。比如顶点v1的度就是1+0+1+0=2。

3.求顶点vi的所有邻接点就是将矩阵中的第i行元素扫描一遍，A[i][j]为1就是邻接点。

4.对于有向图来说，主对角线上数值依旧为0.但因为是有向图，所以此矩阵并不对称。

5.有向图讲究入度与出度，顶点v1的入度为1，正好是第v1列各数之和。顶点v1的出度为2，即第v1行的各数之和。

6.有向图与无向图可以采取同样的方法，判断顶点vi到vj是否存在弧，只需要查找矩阵中A[i][j]是否为1即可。

代码实现如下：

#define MaxVertexNum 100	//顶点数目的最大值
typedef char VertexType;	//顶点的数据类型
typedef int EdgeType;	//带权图中边上权值的数据类型
typedef struct{VertexType Vex[MaxVertexNum];	//顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum];	//邻接矩阵，边表int vexnum, arcnum;	//图的当前顶点数和弧树
}MGraph;

3.2邻接表

定义如下：

#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;	//图中当前顶点数和边数
}

3.3十字链表

代码实现如下：

#include <iostream>
using namespace std;// 定义十字链表的节点结构
struct Node {int row, col;int value;Node* right, * down;
};// 初始化十字链表
Node* createOrthogonalList(int** matrix, int rows, int cols) {Node* head = new Node;head->row = rows;head->col = cols;head->right = head->down = nullptr;Node* rowHeaders[rows];Node* colHeaders[cols];for (int i = 0; i < rows; ++i) {rowHeaders[i] = new Node;rowHeaders[i]->row = i;rowHeaders[i]->col = -1;rowHeaders[i]->right = rowHeaders[i]->down = nullptr;if (i == 0) {head->down = rowHeaders[i];} else {rowHeaders[i - 1]->down = rowHeaders[i];}}for (int i = 0; i < cols; ++i) {colHeaders[i] = new Node;colHeaders[i]->row = -1;colHeaders[i]->col = i;colHeaders[i]->right = colHeaders[i]->down = nullptr;if (i == 0) {head->right = colHeaders[i];} else {colHeaders[i - 1]->right = colHeaders[i];}}for (int i = 0; i < rows; ++i) {Node* prev = rowHeaders[i];for (int j = 0; j < cols; ++j) {if (matrix[i][j] != 0) {Node* newNode = new Node;newNode->row = i;newNode->col = j;newNode->value = matrix[i][j];newNode->right = nullptr;newNode->down = nullptr;prev->right = newNode;prev = newNode;Node* colPrev = colHeaders[j];while (colPrev->down != nullptr && colPrev->down->row < i) {colPrev = colPrev->down;}newNode->down = colPrev->down;colPrev->down = newNode;}}}return head;
}// 打印十字链表
void printOrthogonalList(Node* head) {Node* row = head->down;while (row != nullptr) {Node* col = row->right;while (col != nullptr) {cout << "(" << col->row << ", " << col->col << ", " << col->value << ") ";col = col->right;}cout << endl;row = row->down;}
}// 释放十字链表的内存
void destroyOrthogonalList(Node* head) {Node* row = head->down;while (row != nullptr) {Node* col = row->right;while (col != nullptr) {Node* temp = col;col = col->right;delete temp;}Node* temp = row;row = row->down;delete temp;}Node* col = head->right;while (col != nullptr) {Node* temp = col;col = col->right;delete temp;}delete head;
}int main() {int rows, cols;cout << "请输入矩阵的行数和列数：";cin >> rows >> cols;int** matrix = new int*[rows];for (int i = 0; i < rows; ++i) {matrix[i] = new int[cols];for (int j = 0; j < cols; ++j) {cin >> matrix[i][j];}}Node* orthogonalList = createOrthogonalList(matrix, rows, cols);cout << "十字链表表示的稀疏矩阵：" << endl;printOrthogonalList(orthogonalList);destroyOrthogonalList(orthogonalList);for (int i = 0; i < rows; ++i) {delete[] matrix[i];}delete[] matrix;return 0;
}

3.4邻接多重表

代码实现如下：

#include <iostream>
#include <vector>
using namespace std;// 定义图的边
struct Edge {int dest; // 目标顶点int weight; // 边的权重Edge* next; // 指向下一条边的指针
};// 定义图的顶点
struct Vertex {int data; // 顶点的数据Edge* firstEdge; // 指向第一条边的指针
};// 定义图
class Graph {
private:vector<Vertex> vertices; // 顶点列表public:// 添加顶点void addVertex(int data) {Vertex v;v.data = data;v.firstEdge = nullptr;vertices.push_back(v);}// 添加边void addEdge(int src, int dest, int weight) {Edge* edge = new Edge;edge->dest = dest;edge->weight = weight;edge->next = nullptr;if (vertices[src].firstEdge == nullptr) {vertices[src].firstEdge = edge;} else {Edge* curr = vertices[src].firstEdge;while (curr->next != nullptr) {curr = curr->next;}curr->next = edge;}}// 打印图void printGraph() {for (int i = 0; i < vertices.size(); i++) {cout << "Vertex " << vertices[i].data << ": ";Edge* curr = vertices[i].firstEdge;while (curr != nullptr) {cout << "(" << curr->dest << ", " << curr->weight << ") ";curr = curr->next;}cout << endl;}}
};int main() {Graph g;g.addVertex(1);g.addVertex(2);g.addVertex(3);g.addVertex(4);g.addEdge(0, 1, 10);g.addEdge(0, 2, 20);g.addEdge(1, 2, 30);g.addEdge(2, 3, 40);g.addEdge(3, 0, 50);g.printGraph();return 0;
}

3.5边集数组

代码实现如下：

#include <iostream>
#include <vector>
using namespace std;// 定义图的边
struct Edge {int src; // 源顶点int dest; // 目标顶点int weight; // 边的权重
};// 定义图
class Graph {
private:vector<Edge> edges; // 边集数组public:// 添加边void addEdge(int src, int dest, int weight) {Edge edge;edge.src = src;edge.dest = dest;edge.weight = weight;edges.push_back(edge);}// 打印图void printGraph() {for (int i = 0; i < edges.size(); i++) {cout << "Edge " << i + 1 << ": (" << edges[i].src << ", " << edges[i].dest << ", " << edges[i].weight << ")" << endl;}}
};int main() {Graph g;g.addEdge(0, 1, 10);g.addEdge(0, 2, 20);g.addEdge(1, 2, 30);g.addEdge(2, 3, 40);g.addEdge(3, 0, 50);g.printGraph();return 0;
}

四、图的遍历

图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次， 这一过程就叫做图的遍历(Traversing Graph)。
对于图的遍历来，通常有两种遍历次序方案:它们是深度优先遍历和广度优先遍历。

4.1深度优先遍历（DFS算法）
深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点v，然后由v出发，访问与v邻接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。
在这种情况下，其递归形式的算法十分简洁，算法过程如下:

bool visited[MAX_VERTEX_NUM];	//访问标记数组
/*从顶点出发，深度优先遍历图G*/
void DFS(Graph G, int v){int w;visit(v);	//访问顶点visited[v] = TRUE;	//设已访问标记//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点vfor(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){if(!visited[w]){	//w为u的尚未访问的邻接顶点DFS(G, w);}}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){int v; for(v=0; v<G.vexnum; ++v){visited[v] = FALSE;	//初始化已访问标记数据}for(v=0; v<G.vexnum; ++v){	//从v=0开始遍历if(!visited[v]){DFS(G, v);}}
}

4.2广度优先遍历（BFS算法）

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。
以下是广度优先遍历的代码：

/*邻接矩阵的广度遍历算法*/
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]){vivited[i] = TRUE;	//设置当前访问过visit(i);	//访问顶点EnQueue(&Q, i);	//将此顶点入队列//若当前队列不为空while(!QueueEmpty(Q)){DeQueue(&Q, &i);	//顶点i出队列//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点vfor(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){//检验i的所有邻接点if(!visited[j]){visit(j);	//访问顶点jvisited[j] = TRUE;	//访问标记EnQueue(Q, j);	//顶点j入队列}}}}}
}

4.3图的遍历与图的连通性

图的遍历算法可以用来判断图的连通性。
对于无向图来说，若无向图是连通的，则从任一结点出发， 仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。

五、最小生成树

一个连通图的生成树是一个极小的连通子图，它含有图中全部的顶点，但只有足以构成一棵树的n−1条边，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。对于一个带权连通无向图G=(V,E)，生成树不同，其中边的权值之和最小的那棵生成树（构造连通网的最小代价生成树），称为G的最小生成树(Minimum-Spanning-Tree, MST)。

代码实现：

GENERIC_MST(G){T=NULL;while T 未形成一棵生成树;do 找到一条最小代价边(u, v)并且加入T后不会产生回路;T=T U (u, v);
}

一、普利姆算法

Prim算法构造最小生成树的过程如下图所示。初始时从图中任取一顶点(如顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1。以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。
通俗点说就是：从一个顶点出发，在保证不形成回路的前提下，每找到并添加一条最短的边，就把当前形成的连通分量当做一个整体或者一个点看待，然后重复“找最短的边并添加”的操作。
 

/*Prim算法生成最小生成树*/
void MiniSpanTree_Prim(G){int min, i, j, k;int adjvex[MAXVEX];	//保存相关顶点下标int lowcost[MAXVEX];	//保存相关顶点间边的权值lowcost[0] = 0;	//初始化第一个权值为0，即v0加入生成树//lowcost的值为0，在这里就是此下标的顶点已经加入生成树adjvex[0] = 0;	//初始化第一个顶点下标为0for(i=1; i<G.numVertexes; i++){lowcost[i] = G.arc[0][i];	//将v0顶点与之组成边的权值存入数组adjvex[i] = 0;	//初始化都为v0的下标}for(i=1; i<G.numVertexes; i++){min = INFINITY;	//初始化最下权值为∞，通常设置一个不可能的很大的数字j = 1; k = 0;//循环全部顶点while(j < G.numVertexes){//如果权值不为0且权值小于minif(lowcost[j] != 0 && lowcost[j] < min){min = lowcost[j];	//则让当前权值成为最小值k = j;	//将当前最小值的下标存入k}j++;}print("(%d, %d)", adjvex[k], k);	//打印当前顶点边中权值的最小边for(j=1; j<G.numvertexes; j++){//若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){lowcost[j] = G.arc[k][j];	//将较小权值存入lowcostadjvex[j] = k;	//将下标为k的顶点存入adjvex}}}
}

二、克鲁斯卡尔算法

与Prim算法从顶点开始扩展最小生成树不同，Kruskal 算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

Kruskal算法构造最小生成树的过程如下图所示。初始时为只有n个顶点而无边的非连通图T，每个顶点自成一个连通分量，然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至T中所有顶点都在一个连通分量上。

定义代码：

/*对边集数组Edge结构的定义*/
typedef struct{int begin;int end;int weight;
}Edge;

简单实现：

/*Kruskar算法生成最小生成树*/
void MiniSpanTree_Kruskal(MGraph G){int i, n, m;Edge edges[MAXEDGE];	//定义边集数组int parent[MAXVEX];	//定义一数组用来判断边与边是否形成环路/*此处省略将邻接矩阵G转化为边集数组edges并按照权由小到大排序的代码*/for(i=0; i<G.numVertexes; i++){parent[i] = 0;	//初始化数组为0}for(i=0; i<G.numVertexes; i++){n = Find(parent, edges[i].begin);m = Find(parent, edge[i],end);/*假如n与m不等，说明此边没有与现有生成树形成环路*/if(n != m){/*将此边的结尾顶点放入下标为起点的parent中表示此顶点已经在生成树集合中*/parent[n] = m;printf("(%d, %d, %d)", edges[i].begin, edges[i].end, edges[i].weight);}}
}/*查找连线顶点的尾部下标*/
int Find(int *parent, int f){while(parent[f] > 0){f = parent[f];}return f;
}

六、最短路径

一、迪杰斯特拉算法

代码实现：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;// 定义图的边
struct Edge {int dest; // 目标顶点int weight; // 边的权重
};// 定义图
class Graph {
private:vector<vector<Edge>> adjList; // 邻接表表示的图public:// 构造函数，初始化图Graph(int numVertices) {adjList.resize(numVertices);}// 添加边void addEdge(int src, int dest, int weight) {Edge edge;edge.dest = dest;edge.weight = weight;adjList[src].push_back(edge);}// 迪杰斯特拉算法vector<int> dijkstra(int start) {int numVertices = adjList.size();vector<int> distance(numVertices, numeric_limits<int>::max()); // 距离数组，初始化为最大值distance[start] = 0; // 起始顶点的距离为0priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 优先队列，用于选择最小距离的顶点pq.push(make_pair(0, start));while (!pq.empty()) {int u = pq.top().second; // 获取当前距离最小的顶点pq.pop();// 遍历当前顶点的所有邻接边for (const auto& edge : adjList[u]) {int v = edge.dest;int weight = edge.weight;// 如果通过当前顶点可以得到更短的路径，则更新距离if (distance[u] + weight < distance[v]) {distance[v] = distance[u] + weight;pq.push(make_pair(distance[v], v));}}}return distance;}
};int main() {Graph g(6);g.addEdge(0, 1, 4);g.addEdge(0, 2, 1);g.addEdge(1, 2, 2);g.addEdge(1, 3, 5);g.addEdge(2, 3, 8);g.addEdge(2, 4, 10);g.addEdge(3, 4, 2);g.addEdge(3, 5, 6);g.addEdge(4, 5, 7);int startVertex = 0;vector<int> shortestDistances = g.dijkstra(startVertex);cout << "Shortest distances from vertex " << startVertex << ":" << endl;for (int i = 0; i < shortestDistances.size(); ++i) {cout << "Vertex " << i << ": " << shortestDistances[i] << endl;}return 0;
}

二、弗洛伊德算法

代码实现：

#include <iostream>
#include <vector>
#include <limits>
using namespace std;// 定义图的边
struct Edge {int dest; // 目标顶点int weight; // 边的权重
};// 定义图
class Graph {
private:vector<vector<Edge>> adjList; // 邻接表表示的图public:// 构造函数，初始化图Graph(int numVertices) {adjList.resize(numVertices);}// 添加边void addEdge(int src, int dest, int weight) {Edge edge;edge.dest = dest;edge.weight = weight;adjList[src].push_back(edge);}// 弗洛伊德算法vector<vector<int>> floydWarshall() {int numVertices = adjList.size();vector<vector<int>> distance(numVertices, vector<int>(numVertices, numeric_limits<int>::max())); // 距离矩阵，初始化为最大值// 初始化距离矩阵for (int i = 0; i < numVertices; ++i) {distance[i][i] = 0; // 顶点到自身的距离为0for (const auto& edge : adjList[i]) {distance[i][edge.dest] = edge.weight;}}// 弗洛伊德算法核心逻辑for (int k = 0; k < numVertices; ++k) {for (int i = 0; i < numVertices; ++i) {for (int j = 0; j < numVertices; ++j) {if (distance[i][k] != numeric_limits<int>::max() && distance[k][j] != numeric_limits<int>::max() && distance[i][k] + distance[k][j] < distance[i][j]) {distance[i][j] = distance[i][k] + distance[k][j];}}}}return distance;}
};int main() {Graph g(4);g.addEdge(0, 1, 5);g.addEdge(0, 3, 10);g.addEdge(1, 2, 3);g.addEdge(2, 3, 1);vector<vector<int>> shortestDistances = g.floydWarshall();cout << "Shortest distances between all pairs of vertices:" << endl;for (int i = 0; i < shortestDistances.size(); ++i) {for (int j = 0; j < shortestDistances.size(); ++j) {cout << "Distance from vertex " << i << " to vertex " << j << ": " << shortestDistances[i][j] << endl;}cout << endl;}return 0;
}

七、拓扑排序

一、定义

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网( Activity On VertexNetwork)。所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。

二、算法

bool TopologicalSort(Graph G){InitStack(S);	//初始化栈，存储入度为0的顶点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);	//输出顶点icount++;for(p=G.vertices[i].finstarc; p; p=p->nextarc){//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈Sv = p->adjvex;if(!--indegree[v]){Push(S, v);	//入度为0，则入栈}}}if(count < G.vexnum){return false;	//输出顶点少了，有向图中有回路，排序失败}else{return true;	//拓扑排序成功}
}

八、关键路径

一、定义

拓扑排序主要是为解决一个工程能否顺序进行的问题，但有时我们还需要解决工程完成需要的最短时间问题。
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网。

AOE网和AOV网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE网中的边有权值；而AOV网中的边无权值，仅表示顶点之间的前后关系。

在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始；网中也仅存在一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。我们把路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。
完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

二、算法

代码实现：

#include <iostream>
#include <vector>
#include <stack>
#include <climits>
using namespace std;// 定义图的边
struct Edge {int dest; // 目标顶点int weight; // 边的权重
};// 定义图
class Graph {
private:vector<vector<Edge>> adjList; // 邻接表表示的图int numVertices; // 顶点数量public:// 构造函数，初始化图Graph(int numVertices) {this->numVertices = numVertices;adjList.resize(numVertices);}// 添加边void addEdge(int src, int dest, int weight) {Edge edge;edge.dest = dest;edge.weight = weight;adjList[src].push_back(edge);}// 计算关键路径void criticalPath() {vector<int> earliest(numVertices, 0); // 最早开始时间vector<int> latest(numVertices, INT_MAX); // 最晚开始时间stack<int> topologicalOrder; // 拓扑排序栈// 计算最早开始时间和拓扑排序computeEarliestTimes(topologicalOrder, earliest);// 初始化最晚开始时间为最早开始时间for (int i = 0; i < numVertices; ++i) {latest[i] = earliest[i];}// 计算最晚开始时间while (!topologicalOrder.empty()) {int u = topologicalOrder.top();topologicalOrder.pop();for (const auto& edge : adjList[u]) {int v = edge.dest;int weight = edge.weight;if (latest[v] > latest[u] - weight) {latest[v] = latest[u] - weight;}}}// 打印关键路径cout << "Critical Path:" << endl;for (int i = 0; i < numVertices; ++i) {if (earliest[i] == latest[i]) {cout << "Vertex " << i << ": Earliest time = " << earliest[i] << ", Latest time = " << latest[i] << endl;}}}private:// 计算最早开始时间和拓扑排序void computeEarliestTimes(stack<int>& topologicalOrder, vector<int>& earliest) {vector<bool> visited(numVertices, false);for (int i = 0; i < numVertices; ++i) {if (!visited[i]) {dfs(i, visited, topologicalOrder, earliest);}}}// 深度优先搜索计算最早开始时间void dfs(int u, vector<bool>& visited, stack<int>& topologicalOrder, vector<int>& earliest) {visited[u] = true;for (const auto& edge : adjList[u]) {int v = edge.dest;int weight = edge.weight;if (!visited[v]) {dfs(v, visited, topologicalOrder, earliest);}if (earliest[u] < earliest[v] + weight) {earliest[u] = earliest[v] + weight;}}topologicalOrder.push(u);}
};int main() {Graph g(9);g.addEdge(0, 1, 6);g.addEdge(0, 2, 4);g.addEdge(0, 3, 5);g.addEdge(1, 4, 1);g.addEdge(2, 4, 1);g.addEdge(3, 5, 2);g.addEdge(4, 6, 9);g.addEdge(4, 7, 7);g.addEdge(5, 7, 4);g.addEdge(6, 8, 2);g.addEdge(7, 8, 4);g.criticalPath();return 0;
}