devbox
爱喝兽奶帝天荒
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之图的基本概念及应用（超详细）_有向图和无向图

作者：爱喝兽奶帝天荒 | 2024-07-24 09:38:44

赞

踩

有向图和无向图

引言：

图是一种一对多的关系，是一种较线性表和树更加复杂的线性结构。

与线性表和树相比，我们需要注意图的哪些区别呢？

  1. 线性表中可以没有数据元素，称为空表；树中可以没有结点，称为空树。但！图中不允许没有顶点，从定义中我们可以得知，顶点集合V是有穷非空的。
  2. 图中顶点间的逻辑关系用边来表示，边集可以为空。

目录

一、图的术语概念

1、有向图&&无向图

2、简单图

3、无向完全图&&有向完全图

​编辑

4、稀疏图&&稠密图

5、权&&网

6、子图

7、有向连通图&&无向连通图

8、极大连通&&极小连通

9、极大强连通&&极小强连通

二、存储结构

1、邻接矩阵

2、邻接表

3、十字链表

4、邻接多重表

三、图的遍历

1、深度优先遍历（DFS）

2、广度优先遍历（BFS）

四、图的应用

1、最小生成树

（1）Prim算法（选择点）

（2）Kruskal算法（选择边）

 2、最短路径

（1）Dijkstra算法

（2）Floyd算法 

 3、拓扑排序

4、关键路径

五、总结

一、图的术语概念

1、有向图&&无向图

  • 有向图：任意两顶点间的边都是无向边（），如图7-2-2
  • 无向图：任意两顶点间的边都是有向边 <> ，如图7-2-3

注意：

<vi,vj>表示从vi到vj的有向边

其中vi称为弧尾，vj称为弧头（切忌惯性思维！）

2、简单图

  • 不存在顶点到自身的边
  • 同一条边不重复出现

我们一般讨论的都是简单图的情况，显然以下两种情况不属于我们讨论的范围

3、无向完全图&&有向完全图

  • 无向完全图：无向图中，任意两个顶点都存在边。含有n个顶点的无向完全图有n(n-1)/2条边。

  • 有向完全图：有向图中，任意两个顶点间都存在方向互为相反的两条弧。含有n个顶点的无向完全图有n(n-1)条边。

4、稀疏图&&稠密图

有很少条边或弧的图称为稀疏图，反之为稠密图

5、权&&网

  • 权：图的边或权相关的数
  • 网：带权的图

6、子图

如下图所示：

7、有向连通图&&无向连通图

  • 连通：顶点v到顶点v'间有路径
  • 连通图：任意两个顶点连通

注意连通图和完全图的区别（间接相连和直接相连）

8、极大连通&&极小连通

  • 均在无向图中讨论
  • 极大连通图：加入任一顶点，不再连通。=>对应连通分量

连通分量强调：

1、要是子图

2、子图要是连通的

3、含有极大顶点数

4、具有极大顶点数的连通子图包含依附于这些顶点的所有边

>>>如何判断？

①本身为连通图：只有一个极大连通（对应其本身）

②本身为非连通图：多个极大连通（即连通分量）

  • 极小连通图：删除任一边，不再连通。=>对应生成树

注意：

1、极小连通的每条边都必不可少

2、极小连通可以理解为保留所有顶点，删掉所有能删掉的边后仍能连通

（即它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边）

3、如果在生成树（极小连通）上添加一条边，一定会构成一条环

>>>如何判断

①本身为连通图：极小连通（生成树）不唯一

②本身为非连通图：不存在极小连通

9、极大强连通&&极小强连通

  • 在有向图中讨论
  • 极大强连通：定义同上，只是加了方向

>>>如何判断？

①本身为强连通图：只有一个极大强连通（对应其本身）

②本身为非强连通图：多个极大强连通（即强连通分量）

  • 极小强连通：不存在

二、存储结构

1、邻接矩阵

  • 用两个数组来表示图：①一维数组（存放顶点信息）②二维数组（存储邻接信息）
  • 无权的情况

如下图所示：

  • 有权的情况

如下图所示：

注意：

1、邻接矩阵的对角线一定为0

2、无向图的邻接矩阵一定对称，有向图可能不对称

3、度的计算

  • 创建邻接矩阵，以无权的情况为例
  1. //以下定义邻接矩阵类型
  2. typedef struct 
  3. {  	int no;						//顶点编号
  4. 	InfoType info;				//顶点其他信息
  5. } VertexType;					//顶点类型
  6. typedef struct  				//图的定义
  7. {  	int edges[MAXV][MAXV]; 		//邻接矩阵（二维数组）
  8.    	int n,e;   					//顶点数，弧数
  9. 	VertexType vexs[MAXV];		//存放顶点信息（一维数组）
  10. } MGraph;		
  11.  
  12. //创建邻接矩阵
  13. void createAdjMatrix(MGraph& graph) {
  14.     cout << "Enter the number of vertices: ";
  15.     cin >> graph.n;
  16.     //初始化邻接矩阵
  17.     for (int i = 0; i < graph.n; i++) {
  18.         for (int j = 0; j < graph.n; j++) {
  19.             graph.edges[i][j] = 0;
  20.         }
  21.     }
  22.     cout << "Enter the number of edges: ";
  23.     cin >> graph.e;
  24.     cout << "Enter the edges (from vertex to vertex):" << endl;
  25.     for (int i = 0; i < graph.e; i++) {
  26.         int from, to;
  27.         cin >> from >> to;
  28.         graph.edges[from][to] = 1;
  29.         graph.edges[to][from] = 1; // Assuming undirected graph
  30.     }
  31. }

邻接矩阵需注意：

1、不利于增加和修改顶点

2、空间复杂度为O(n^2) ，不适合稀疏图，更适合稠密图

2、邻接表

  • 一种数组与链表相结合的存储方法（减少了存储空间的浪费）
  • 存储方法

1、顶点：用一维数组（或单链表）来存储，每个顶点包括顶点本身信息和第一个邻接点的指针

2、邻接点：每个顶点的所有邻接点构成一个线性表，用单链表存储（个数不确定）

  • 无向图的邻接表结构

1、若无向图有n个顶点+e条边，则邻接表有n个头结点+2e个表结点

2、空间复杂度：O（n+2e）

  • 有向图的邻接表结构

出度易统计，入度不易

  • 有向图的逆邻接表结构（每个顶点存放以它为弧头的邻接顶点）

入度易统计，出度不易

  • 构建算法

1、定义邻接表结构

  1. // 边表结点
  2. typedef struct ArcNode {
  3.     int adjvex;              // 该边所指向的顶点位置
  4.     struct ArcNode* next;    // 指向下一条边的指针
  5.     // 可根据需要添加其他信息
  6. } ArcNode;
  7.  
  8. // 顶点表结点
  9. typedef struct VNode {
  10.     VertexType data;        // 顶点信息
  11.     ArcNode* firstArc;      // 指向第一条依附该顶点的边的指针
  12. } VNode;
  13.  
  14. // 邻接表
  15. typedef struct {
  16.     VNode adjList[MAXV];    // 邻接表的头结点数组
  17.     int n, e;               // 顶点数和边数
  18. } ALGraph;

2、创建邻接表（头插法）

  1. // 创建邻接表函数
  2. void createAdjList(ALGraph& graph) {
  3.     cout << "Enter the number of vertices: ";
  4.     cin >> graph.n;
  5.     cout << "Enter the number of edges: ";
  6.     cin >> graph.e;
  7.  
  8.     for (int i = 0; i < graph.n; i++) {
  9.         cout << "Enter the data for vertex " << i << ": ";
  10.         // 这里根据实际需求输入顶点数据
  11.         cin >> graph.adjList[i].data;
  12.         graph.adjList[i].firstArc = NULL;
  13.     }
  14.  
  15.     cout << "Enter the edges (from vertex to vertex):" << endl;
  16.     for (int i = 0; i < graph.e; i++) {
  17.         int from, to;
  18.         cin >> from >> to;
  19.         ArcNode* arcNode = new ArcNode;
  20.         arcNode->adjvex = to;
  21.         arcNode->next = graph.adjList[from].firstArc;
  22.         graph.adjList[from].firstArc = arcNode;
  23.  
  24.         // 若是无向图，需要添加下面一行
  25.         arcNode = new ArcNode;
  26.         arcNode->adjvex = from;
  27.         arcNode->next = graph.adjList[to].firstArc;
  28.         graph.adjList[to].firstArc = arcNode;
  29.     }
  30. }

邻接表和邻接矩阵对比：

1、邻接表方便找邻接点

2、邻接表节约空间

3、任一无向图，邻接矩阵唯一，邻接表不唯一

4、邻接矩阵适合稠密图，邻接表适合稀疏图

3、十字链表

  • 针对有向图邻接表进行改造
  • 邻接表和逆邻接表的结合
  • 顶点表结点

其中，firstin是入边表头指针，指向该顶点的入边表中第一个结点，firstout是出边表头指针，指向该顶点的出边表的第一个结点

  • 边表结点

其中，tailvex是弧起点在顶点表的下标，hairvex是弧终点在顶点表的下标，headlink是入边表指针域，指向终点相同的下一条边（逆邻接表），taillink是出边表指针域，指向起点相同的下一条边（邻接表）。（如果是网，还可以增加一个weight域来存储权值）

  • 如下图所示（虚线表示逆邻接表）

十字链表容易求得顶点的出度和入度。除了结构复杂，其创建图算法的时间复杂度和邻接表相同，所以是一种非常好的数据结构模型。

4、邻接多重表

  • 针对无向图邻接表进行改造
  • 重新定义边表结点结构

ivex，jvex：与某条边依附的两个顶点在顶点表中的下标

ilink：指向ivex的下一条边

jlink：指向jvex的下一条边

  • 如下图所示

邻接多重表与邻接表的差别：

仅仅在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点

这样对边的操作就方便多了

三、图的遍历

1、深度优先遍历（DFS）

实际上就是一个递归的过程

  • 邻接矩阵
  1. #include <iostream>
  2. #include <stack>
  3. using namespace std;
  4.  
  5. typedef struct 
  6. {  	int no;						
  7. 	// 其他信息，这里省略
  8. } VertexType;					
  9.  
  10. typedef struct  				
  11. {  	int edges[MAXV][MAXV]; 	
  12.    	int n,e;   					
  13. 	VertexType vexs[MAXV];		
  14. } MGraph;
  15.  
  16. void DFS(MGraph graph, int vertex, bool visited[]) {
  17.     visited[vertex] = true;//标记已访问
  18.     cout << graph.vexs[vertex].no << " ";
  19.  
  20.     for (int i = 0; i < graph.n; i++) {
  21.         if (graph.edges[vertex][i] == 1 && !visited[i]) {
  22.             DFS(graph, i, visited);
  23.         }
  24.     }
  25. }
  26.  
  27. int main() {
  28.     MGraph graph;
  29.     // 假设图已经创建并初始化
  30.  
  31.     bool visited[MAXV];
  32.     for (int i = 0; i < graph.n; i++) {
  33.         visited[i] = false;//初始化
  34.     }
  35.  
  36.     for (int i = 0; i < graph.n; i++) {
  37.         if (!visited[i]) {
  38.             DFS(graph, i, visited);
  39.         }
  40.     }
  41.  
  42.     return 0;
  43. }
  • 邻接表
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. using namespace std;
  5.  
  6. typedef struct 
  7. {  	int no;						
  8. 	// 其他信息，这里省略
  9. } VertexType;
  10.  
  11. typedef struct EdgeNode {
  12.     int adjvex;             // 邻接顶点
  13.     struct EdgeNode* next;  // 指向下一个邻接顶点的指针
  14. } EdgeNode;
  15.  
  16. typedef struct VertexNode {
  17.     VertexType data;        // 顶点信息
  18.     EdgeNode* firstEdge;    // 指向第一个邻接顶点的指针
  19. } VertexNode;
  20.  
  21. typedef struct 
  22. {  	vector<VertexNode> vertices; // 顶点数组
  23.    	int n,e;   					
  24. } ALGraph;
  25.  
  26. void DFS(ALGraph graph, int vertex, bool visited[]) {
  27.     visited[vertex] = true;
  28.     cout << graph.vertices[vertex].data.no << " ";
  29.  
  30.     EdgeNode* p = graph.vertices[vertex].firstEdge;
  31.     while (p != nullptr) {
  32.         if (!visited[p->adjvex]) {
  33.             DFS(graph, p->adjvex, visited);
  34.         }
  35.         p = p->next;
  36.     }
  37. }
  38.  
  39. int main() {
  40.     ALGraph graph;
  41.     // 假设图已经创建并初始化
  42.  
  43.     bool visited[graph.n];
  44.     for (int i = 0; i < graph.n; i++) {
  45.         visited[i] = false;
  46.     }
  47.  
  48.     for (int i = 0; i < graph.n; i++) {
  49.         if (!visited[i]) {
  50.             DFS(graph, i, visited);
  51.         }
  52.     }
  53.  
  54.     return 0;
  55. }

2、广度优先遍历（BFS）

层序遍历的思想 

  • 邻接矩阵
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. typedef struct 
  6. {  	int no;						
  7. 	// 其他信息，这里省略
  8. } VertexType;
  9.  
  10. typedef struct  				
  11. {  	int edges[MAXV][MAXV]; 	
  12.    	int n,e;   					
  13. 	VertexType vexs[MAXV];		
  14. } MGraph;
  15.  
  16. void BFS(MGraph graph, int start) {
  17.     bool visited[MAXV];
  18.     for (int i = 0; i < graph.n; i++) {
  19.         visited[i] = false;//初始化
  20.     }
  21.  
  22.     queue<int> q;
  23.     q.push(start);
  24.     visited[start] = true;
  25.  
  26.     while (!q.empty()) {
  27.         int current = q.front();
  28.         q.pop();
  29.         cout << graph.vexs[current].no << " ";
  30.  
  31.         for (int i = 0; i < graph.n; i++) {
  32.             if (graph.edges[current][i] == 1 && !visited[i]) {
  33.                 q.push(i);
  34.                 visited[i] = true;
  35.             }
  36.         }
  37.     }
  38. }
  39.  
  40. int main() {
  41.     MGraph graph;
  42.     // 假设图已经创建并初始化
  43.  
  44.     cout << "广度优先搜索遍历结果:" << endl;
  45.     BFS(graph, 0);
  46.  
  47.     return 0;
  48. }
  • 邻接表
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. typedef struct 
  7. {  	int no;						
  8. 	// 其他信息，这里省略
  9. } VertexType;
  10.  
  11. typedef struct EdgeNode {
  12.     int adjvex;             // 邻接顶点
  13.     struct EdgeNode* next;  // 指向下一个邻接顶点的指针
  14. } EdgeNode;
  15.  
  16. typedef struct VertexNode {
  17.     VertexType data;        // 顶点信息
  18.     EdgeNode* firstEdge;    // 指向第一个邻接顶点的指针
  19. } VertexNode;
  20.  
  21. typedef struct 
  22. {  	vector<VertexNode> vertices; // 顶点数组
  23.    	int n,e;   					
  24. } ALGraph;
  25.  
  26. void BFS(ALGraph graph, int start) {
  27.     bool visited[graph.n];
  28.     for (int i = 0; i < graph.n; i++) {
  29.         visited[i] = false;
  30.     }
  31.  
  32.     queue<int> q;
  33.     q.push(start);
  34.     visited[start] = true;
  35.  
  36.     while (!q.empty()) {
  37.         int current = q.front();
  38.         q.pop();
  39.         cout << graph.vertices[current].data.no << " ";
  40.  
  41.         EdgeNode* p = graph.vertices[current].firstEdge;
  42.         while (p != nullptr) {
  43.             if (!visited[p->adjvex]) {
  44.                 q.push(p->adjvex);
  45.                 visited[p->adjvex] = true;
  46.             }
  47.             p = p->next;
  48.         }
  49.     }
  50. }
  51.  
  52. int main() {
  53.     ALGraph graph;
  54.     // 假设图已经创建并初始化
  55.  
  56.     cout << "广度优先搜索遍历结果:" << endl;
  57.     BFS(graph, 0);
  58.  
  59.     return 0;
  60. }

选择什么样的遍历算法视不同情况而定

深度优先更适合目标比较明确，以找到目标为主要目的的情况

广度优先更适合在不断扩大遍历范围内找到相对最优解的情况 

注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的DFS序列和BFS序列是唯一的，基于邻接表的遍历所得到的DFS序列和BFS序列是不唯一的。

四、图的应用

1、最小生成树

  • 构造连通网的最小代价生成树（前提是生成树）

生成树的性质，注意：

1、n个顶点对应n-1条边

2、任意两个顶点间路径唯一

3、一个图可以有多棵不同的生成树

  • 经典应用：n个城市间建通信网，使成本最低（权值最小）

（1）Prim算法（选择点）

  • 算法思想

从一个起始顶点开始，逐步扩展生成树，每次选择与当前生成树连接的边中权值最小的边所连接的顶点加入生成树中，直到所有顶点都被加入生成树为止。

具体步骤如下：

1、选择一个起始顶点作为生成树的根节点。

2、将根节点加入生成树中，并标记为已访问。

3、从生成树中的所有顶点找到与之相连且未被访问过的边中权值最小的边所连接的顶点，将该顶点加入生成树，并标记为已访问。

4、重复第3步，直到所有顶点都被加入生成树为止。

记忆口诀：选根加边，建最小距，贪心来求

  • 算法实现
  1. #define MAXV 20			//最多顶点数
  2. #define INF 32767       //INF表示∞
  3. typedef char InfoType;
  4. typedef struct 
  5. {  	
  6. 	int no;						//顶点编号
  7. 	InfoType info;				//顶点其他信息
  8. } VertexType;					//顶点类型
  9. typedef struct  				//图的定义
  10. {  	
  11. 	int edges[MAXV][MAXV]; 		//邻接矩阵
  12.    	int n,e;   					//顶点数，弧数
  13. 	VertexType vexs[MAXV];		//存放顶点信息
  14. } MGraph;						//图的邻接矩阵类型
  15.  
  16. void Prim(MGraph g,int v)
  17. {
  18. 	int lowcost[MAXV];			//顶点i是否在U中
  19. 	int min;
  20. 	int closest[MAXV],i,j,k;
  21. 	for (i=0;i<g.n;i++)          	//给lowcost[]和closest[]置初值
  22. 	{	
  23. 		lowcost[i]=g.edges[v][i];
  24. 		closest[i]=v;
  25. 	}
  26. 	for (i=1;i<g.n;i++)          	//找出n-1个顶点
  27. 	{
  28. 		min=INF;
  29. 		for (j=0;j<g.n;j++)       //在(V-U)中找出离U最近的顶点k
  30. 			if (lowcost[j]!=0 && lowcost[j]<min) 
  31. 			{
  32. 				min=lowcost[j];
  33. 				k=j;			//k记录最近顶点的编号
  34. 			}
  35. 		printf(" 边(%d,%d)权为:%d\n",closest[k],k,min);
  36. 		lowcost[k]=0;         	//标记k已经加入U
  37. 		for (j=0;j<g.n;j++)   	//修改数组lowcost和closest
  38. 			if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j]) 
  39. 			{
  40. 				lowcost[j]=g.edges[k][j];
  41. 				closest[j]=k; 
  42. 			}
  43. 	}
  44. }
  45. void main()
  46. {
  47. 	int i,j;
  48. 	MGraph g;
  49. 	g.n=6;g.e=20;
  50. 	int a[6][MAXV]={
  51. 		{0,6,1,5,INF,INF},
  52. 		{6,0,5,INF,3,INF},
  53. 		{1,5,0,5,6,4},
  54. 		{5,INF,5,0,INF,2},
  55. 		{INF,3,6,INF,0,6},
  56. 		{INF,INF,4,2,6,0}};
  57. 	for (i=0;i<g.n;i++)		//建立图9.13(a)所示的图的邻接矩阵
  58. 		for (j=0;j<g.n;j++)
  59. 			g.edges[i][j]=a[i][j];
  60. 	printf("最小生成树构成:\n");
  61. 	Prim(g,0);
  62. 	printf("\n");
  63. }

时间复杂度：O(n^2)（n是顶点数）

更适合稠密图 

（2）Kruskal算法（选择边）

  • 算法思想

基于贪心策略，通过按权重顺序添加边来构建最小生成树。首先将所有边按权值进行排序，然后从最小权值的边开始逐个添加并不能形成环，直到生成最小生成树为止。

很多考题的破题点就是不能形成环

记忆口诀：从小到大不成环 

  • 算法实现
  1. #define MaxSize 100
  2. #define INF 32767	//INF表示∞
  3. #define	MAXV 100	//最大顶点个数
  4. typedef int InfoType;
  5.  
  6. typedef struct 
  7. {  	
  8. 	int no;						//顶点编号
  9. 	InfoType info;				//顶点其他信息
  10. } VertexType;					//顶点类型
  11. typedef struct  				//图的定义
  12. {  	
  13. 	int edges[MAXV][MAXV]; 		//邻接矩阵
  14.    	int n,e;   					//顶点数，弧数
  15. 	VertexType vexs[MAXV];		//存放顶点信息
  16. } MGraph;						//图的邻接矩阵类型
  17.  
  18. typedef struct 
  19. {	
  20. 	int u;			//边的起始顶点
  21.     int v;			//边的终止顶点
  22.     int w;			//边的权值
  23. } Edge;
  24.  
  25. void InsertSort(Edge E[],int n) //对E[0..n-1]按递增有序进行直接插入排序
  26. {
  27. 	int i,j;
  28. 	Edge temp;
  29. 	for (i=1;i<n;i++) 
  30. 	{
  31. 		temp=E[i];
  32. 		j=i-1;				//从右向左在有序区E[0..i-1]中找E[i]的插入位置
  33. 		while (j>=0 && temp.w<E[j].w) 
  34. 		{
  35. 			E[j+1]=E[j];	//将关键字大于E[i].w的记录后移
  36. 			j--;
  37. 		}
  38. 		E[j+1]=temp;		//在j+1处插入E[i] 
  39. 	}
  40. }
  41. void Kruskal(MGraph g)
  42. {
  43. 	int i,j,u1,v1,sn1,sn2,k;
  44. 	int vset[MAXV];
  45. 	Edge E[MaxSize];				//存放所有边
  46. 	k=0;							//E数组的下标从0开始计
  47. 	for (i=0;i<g.n;i++)				//由g产生的边集E
  48. 		for (j=0;j<g.n;j++)
  49. 			if (g.edges[i][j]!=0 && g.edges[i][j]!=INF)
  50. 			{
  51. 				E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];
  52. 				k++;
  53. 			}
  54. 	InsertSort(E,g.e);				//采用直接插入排序对E数组按权值递增排序
  55.  
  56. 	for (i=0;i<g.n;i++) 			//初始化辅助数组
  57. 		vset[i]=i;
  58. 	k=1;                 			//k表示当前构造生成树的第几条边,初值为1
  59. 	j=0;                 			//E中边的下标,初值为0
  60. 	while (k<g.n)       			//生成的边数小于n时循环
  61. 	{	
  62. 		u1=E[j].u;v1=E[j].v;        //取一条边的头尾顶点
  63. 		sn1=vset[u1];
  64. 		sn2=vset[v1]; 				//分别得到两个顶点所属的集合编号
  65. 		if (sn1!=sn2)     	  		//两顶点属于不同的集合,该边是最小生成树的一条边
  66. 		{	
  67. 			printf("  (%d,%d):%d\n",u1,v1,E[j].w);
  68. 			k++;                    //生成边数增1
  69. 			for (i=0;i<g.n;i++)     //两个集合统一编号
  70. 				if (vset[i]==sn2)  	//集合编号为sn2的改为sn1
  71. 				    vset[i]=sn1;
  72. 		}
  73. 		j++;   						//扫描下一条边
  74. 	}
  75. }
  76. void main()
  77. {
  78. 	int i,j;
  79. 	MGraph g;
  80. 	g.n=6;g.e=20;
  81. 	int a[6][MAXV]={
  82. 		{0,6,1,5,INF,INF},
  83. 		{6,0,5,INF,3,INF},
  84. 		{1,5,0,5,6,4},
  85. 		{5,INF,5,0,INF,2},
  86. 		{INF,3,6,INF,0,6},
  87. 		{INF,INF,4,2,6,0}};
  88. 	for (i=0;i<g.n;i++)		//建立图9.13(a)所示的图的邻接矩阵
  89. 		for (j=0;j<g.n;j++)
  90. 			g.edges[i][j]=a[i][j];
  91. 	printf("最小生成树构成:\n");
  92. 	Kruskal(g);
  93. 	printf("\n");
  94. }

时间复杂度： 取决于对边的排序和并查集操作，总体时间复杂度为O(ElogE)（E为边）

更适合稀疏图

 2、最短路径

  •  对于网图，即两顶点间经过的边上权值之和最小的路径（主要研究）
  • 对于非网图，即两顶点间经过的边数最少的路径

（1）Dijkstra算法

1、源点确认（单源最短路径）

2、可以用于有向图，但不能存在负权值

通俗点说，它并不是一下子求出了v0到v8的最短路径，而是一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径，最终得到你要的结果。

  • 算法思想

按路径长度递增的次序产生最短路径

算法的具体步骤如下：

1、初始化：将起始点的到自身的距离设置为0，将其他顶点到起始点的距离设置为无穷大。

2、选择当前距离起始点距离最短的顶点，将其加入最短路径中。

3、对于该顶点的相邻顶点，更新起始点到这些顶点的距离，如果新的距离比之前的距离小，则更新距离。

4、重复步骤2和3，直到所有顶点都加入最短路径。

5、最终得到起始点到其他所有顶点的最短路径。

  • 算法实现
  1. #define MaxSize 100
  2. #define INF 32767	//INF表示∞
  3. #define	MAXV 100	//最大顶点个数
  4. typedef int InfoType;
  5.  
  6. typedef struct 
  7. {  	
  8. 	int no;						//顶点编号
  9. 	InfoType info;				//顶点其他信息
  10. } VertexType;					//顶点类型
  11. typedef struct  				//图的定义
  12. {  	
  13. 	int edges[MAXV][MAXV]; 		//邻接矩阵
  14.    	int n,e;   					//顶点数,弧数
  15. 	VertexType vexs[MAXV];		//存放顶点信息
  16. } MGraph;						//图的邻接矩阵类型
  17.  
  18. void Ppath(int path[],int i,int v)  //前向递归查找路径上的顶点
  19. {
  20. 	int k;
  21. 	k=path[i];
  22. 	if (k==v)  return;			//找到了起点则返回
  23. 	Ppath(path,k,v);			//找顶点k的前一个顶点
  24. 	printf("%d,",k);			//输出顶点k
  25. }
  26. void Dispath(int dist[],int path[],int s[],int n,int v)
  27. {
  28. 	int i;
  29. 	for (i=0;i<n;i++)
  30. 		if (s[i]==1) 
  31. 		{	
  32. 			printf("  从%d到%d的最短路径长度为:%d\t路径为:",v,i,dist[i]);
  33. 			printf("%d,",v);	//输出路径上的起点
  34. 			Ppath(path,i,v);	//输出路径上的中间点
  35. 			printf("%d\n",i);	//输出路径上的终点
  36. 		}
  37. 		else  printf("从%d到%d不存在路径\n",v,i);
  38. }
  39. void Dijkstra(MGraph g,int v)
  40. {
  41. 	int dist[MAXV],path[MAXV];
  42. 	int s[MAXV];
  43. 	int mindis,i,j,u;
  44. 	for (i=0;i<g.n;i++) 
  45. 	{	
  46. 		dist[i]=g.edges[v][i];   	//距离初始化
  47. 		s[i]=0;                		//s[]置空
  48. 		if (g.edges[v][i]<INF)		//路径初始化
  49. 			path[i]=v;
  50. 		else
  51. 		    path[i]=-1;
  52. 	}
  53. 	s[v]=1;path[v]=0;        		//源点编号v放入s中
  54. 	for (i=0;i<g.n;i++)    			//循环直到所有顶点的最短路径都求出
  55. 	{	
  56. 		mindis=INF;					//mindis置最小长度初值
  57. 		for (j=0;j<g.n;j++)     	//选取不在s中且具有最小距离的顶点u
  58. 			if (s[j]==0 && dist[j]<mindis) 
  59. 			{ 	
  60. 				u=j;
  61. 				mindis=dist[j];	
  62. 			}
  63. 		s[u]=1;               		//顶点u加入s中
  64. 		for (j=0;j<g.n;j++)     	//修改不在s中的顶点的距离
  65. 			if (s[j]==0) 
  66. 				if (g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j]) 
  67. 				{	
  68. 					dist[j]=dist[u]+g.edges[u][j];
  69. 					path[j]=u;
  70. 				}  
  71. 	}
  72. 	Dispath(dist,path,s,g.n,v);  	//输出最短路径
  73. }
  74.  
  75. void main()
  76. {
  77. 	int i,j;
  78. 	MGraph g;
  79. 	g.n=7;g.e=12;
  80. 	int a[7][MAXV]={
  81. 		{0,4,6,6,INF,INF,INF},
  82. 		{INF,0,1,INF,7,INF,INF},
  83. 		{INF,INF,0,INF,6,4,INF},
  84. 		{INF,INF,2,0,INF,5,INF},
  85. 		{INF,INF,INF,INF,0,INF,6},
  86. 		{INF,INF,INF,INF,1,0,8},
  87. 		{INF,INF,INF,INF,INF,INF,0}};
  88. 	for (i=0;i<g.n;i++)		//建立图9.16所示的图的邻接矩阵
  89. 		for (j=0;j<g.n;j++)
  90. 			g.edges[i][j]=a[i][j];
  91. 	printf("最小生成树构成:\n");
  92. 	Dijkstra(g,0);
  93. 	printf("\n");
  94. }
时间复杂度:O(n^2)（n是顶点数）

（2）Floyd算法 

1、源点不确认（所有顶点最短路径） 

  • 算法思想

通过动态规划的方式求解所有顶点之间的最短路径。算法的具体步骤如下：

1、初始化：构建一个二维数组distances来存储任意两个顶点之间的最短路径长度。如果两个顶点之间有直接的边，则存储这条边的权重，否则存储无穷大。

2、对于每一对顶点i和j，检查是否存在一个顶点k，使得通过顶点k可以使顶点i到顶点j的距离更短。如果是，则更新distances[i][j] = distances[i][k] + distances[k][j]。

3、重复上述步骤，直到所有顶点之间的最短路径长度都被更新为最小值。

4、最终得到一个二维数组distances，其中distances[i][j]表示顶点i到顶点j的最短路径长度。

（即矩阵从A0到An-1，An-1为最终状态）

  • 算法实现
  1. #define MaxSize 100
  2. #define INF 32767	//INF表示∞
  3. #define	MAXV 100	//最大顶点个数
  4. typedef int InfoType;
  5.  
  6. typedef struct 
  7. {  	
  8. 	int no;						//顶点编号
  9. 	InfoType info;				//顶点其他信息
  10. } VertexType;					//顶点类型
  11. typedef struct  				//图的定义
  12. {  	
  13. 	int edges[MAXV][MAXV]; 		//邻接矩阵
  14.    	int n,e;   					//顶点数,弧数
  15. 	VertexType vexs[MAXV];		//存放顶点信息
  16. } MGraph;						//图的邻接矩阵类型
  17. void Ppath(int path[][MAXV],int i,int j)  //前向递归查找路径上的顶点
  18. {
  19. 	int k;
  20. 	k=path[i][j];
  21. 	if (k==-1) return;	//找到了起点则返回
  22. 	Ppath(path,i,k);	//找顶点i的前一个顶点k
  23. 	printf("%d,",k);
  24. 	Ppath(path,k,j);	//找顶点k的前一个顶点j
  25. }
  26. void Dispath(int A[][MAXV],int path[][MAXV],int n)
  27. {
  28. 	int i,j;
  29. 	for (i=0;i<n;i++)
  30. 		for (j=0;j<n;j++) 
  31. 		{
  32. 			if (A[i][j]==INF) 
  33. 			{
  34. 				if (i!=j) 
  35. 					printf("从%d到%d没有路径\n",i,j);
  36. 			}
  37. 			else 
  38. 			{
  39. 				printf("  从%d到%d=>路径长度:%d 路径:",i,j,A[i][j]);
  40. 				printf("%d,",i);	//输出路径上的起点
  41. 				Ppath(path,i,j);	//输出路径上的中间点
  42. 				printf("%d\n",j);	//输出路径上的终点
  43. 			}
  44. 		}
  45. } 
  46. void Floyd(MGraph g)
  47. {
  48. 	int A[MAXV][MAXV],path[MAXV][MAXV];
  49. 	int i,j,k;
  50. 	for (i=0;i<g.n;i++)
  51. 		for (j=0;j<g.n;j++) 
  52. 		{
  53. 			A[i][j]=g.edges[i][j];
  54. 			path[i][j]=-1;
  55. 		}
  56. 	for (k=0;k<g.n;k++)
  57. 	{
  58. 		for (i=0;i<g.n;i++)
  59. 			for (j=0;j<g.n;j++)
  60. 				if (A[i][j]>A[i][k]+A[k][j]) 
  61. 				{
  62. 					A[i][j]=A[i][k]+A[k][j];
  63. 					path[i][j]=k;
  64. 				}
  65. 	}
  66. 	Dispath(A,path,g.n);   //输出最短路径
  67. }
  68.  
  69. void main()
  70. {
  71. 	int i,j;
  72. 	MGraph g;
  73. 	g.n=4;g.e=8;
  74. 	int a[4][MAXV]={
  75. 		{0,  5,INF,7},
  76. 		{INF,0,  4,2},
  77. 		{3,  3,  0,2},
  78. 		{INF,INF,1,0}};
  79. 	for (i=0;i<g.n;i++)	
  80. 		for (j=0;j<g.n;j++)
  81. 			g.edges[i][j]=a[i][j];
  82. 	printf("各顶点的最短路径:\n");
  83. 	Floyd(g);
  84. 	printf("\n");
  85. }

时间复杂度： O(n^3）（n是顶点数）

 

 3、拓扑排序

1、引入概念--AOV网

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动间的优先关系

2、AOV网的性质

①弧表示活动间的某种制约关系

②不允许有回路（否则表示某项活动以自己为先决条件，不成立）

  • 拓扑序列

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,...，vn，满足从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列。

拓扑序列不唯一

  • 拓扑排序

对一个有向图构造拓扑序列的过程

如果：

①构造完毕后此网的全部顶点都被输出，则说明它是不存在环的AOV网

②如果输出顶点数少了，哪怕是少了一个，也说明该网存在环，不是AOV网

一个不存在回路的AOV网，我们可以将它应用在各种各样的工程项目流程图

  • 拓扑排序算法思想

从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或AOV网中不存在入度为0的顶点为止

  • 拓扑排序算法实现
  1. bool TopologicalSort(Graph G){
  2. 	InitStack(S);	//初始化栈，存储入度为0的顶点
  3. 	for(int i=0; i<G.vexnum; i++){
  4. 		if(indegree[i] == 0){
  5. 			Push(S, i);	//将所有入度为0的顶点进栈
  6. 		}
  7. 	}
  8. 	int count = 0;	//计数，记录当前已经输出的顶点数
  9. 	while(!IsEmpty(S)){	//栈不空，则存在入度为0的顶点
  10. 		Pop(S, i);	//顶点元素出栈
  11. 		printf("%d ", i);	//输出顶点i
  12. 		count++;
  13. 		for(p=G.vertices[i].finstarc; p; p=p->nextarc){
  14. 			//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
  15. 			v = p->adjvex;
  16. 			if(!--indegree[v]){
  17. 				Push(S, v);	//入度为0，则入栈
  18. 			}
  19. 		}
  20. 	}
  21. 	if(count < G.vexnum){
  22. 		return false;	//输出顶点少了，有向图中有回路，排序失败
  23. 	}else{
  24. 		return true;	//拓扑排序成功
  25. 	}
  26. }

4、关键路径

拓扑排序主要为了解决一个工程能否顺序进行的问题

关键路径主要为了解决工程完成需要的最短时间问题

 

引入概念--AOE网 

用顶点表示事件，有向边表示活动，边上的权值表示活动的持续时间

  •  关键路径

路径长度：路径上各种活动所持续的时间之和

从源点到汇点具有最大长度的路径叫关键路径

一个图可能不止一条关键路径

  • 关键活动

关键路径上的活动

  • 求解关键路径算法思想

Ve(j)：表示事件(顶点)的最早开始时间，在不推迟整个工期的前提下，表示从源点开始到该节点的需要的最长时间

Vl(j)：表示事件(顶点)的最晚开始时间，在不推迟整个工期的前提下，表示从结束顶点到该点最短需要多少时间

e(i)：表示活动(边)的最早开始时间，就是活动边的起点的最早发生时间, 表示该边起点的最早开始时间

l(i)：表示活动(边)的最晚开始时间，就是该活动边起点的最晚发生时间，表示该边起点的最晚开始事件

具体步骤如下：

1、求Ve(j),Vl(j)  Ve(j)=Max{Ve(i)+Wi,j} &&Vl(i)=Min{Vl(j)-Wi,j}

2、求e(i),l(i) e(i)=Ve(j)&&l(i)=Vl(k)-Wj,k

3、计算l(i)-e(i) if==0,则在关键路径上

如下图所示

时间复杂度：O（n+e）

  • 关键路径的讨论

①关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
②网中的关键路径并不唯一。
③对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

注意：并不是加快任何一个关键活动都可以缩短整个工程完成的时间，只有加快那些包括在所有的关键路径上的关键活动才能达到这个目的。只有在不改变AOE网的关键路径的前提下，加快包含在关键路径上的关键活动才可以缩短整个工程的完成时间。

五、总结

图是一种非常常用的一类数据结构，但同时它也是最为复杂的，几乎涉及到之前所有学过的数据结构，学习该数据结构不光需要对之前的知识都有所了解，还需要付出大量的时间和耐心。

参考资料：

1、数据结构：图(Graph)【详解】_图数据结构-CSDN博客

2、数据结构与算法----关键路径 - 掘金 (juejin.cn)

3、李春葆：《数据结构教程》

4、程杰：《大话数据结构》

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/873937
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号