devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

图的基础总结_图由顶点和边组成,顶点表示图中的数据元素,边表示数据元素之间的

作者：知新_RL | 2024-08-15 18:36:59

赞

踩

图由顶点和边组成,顶点表示图中的数据元素,边表示数据元素之间的

图的定义：

首先，需要定义什么是图。图是由顶点（或节点）和边（或弧）组成的数据结构。顶点表示数据元素，而边表示数据元素之间的关系。图可以是无向的，也可以是有向的，这取决于边的方向性。

表示： 

图（Graph）是由顶点（Vertex）的有穷非空集合和顶点之间边的集合组成，通常表示为：G = (V, E)，其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

关系：

在图论中，顶点（Vertex）是图中的数据元素，通常用来表示实际对象（如人、地点、事件等），而边（Edge）则表示顶点之间的关系。

有向图和无向图：

根据边的有无方向性，图可以分为无向图和有向图。

  • 在无向图中，任意两个顶点之间的边没有方向性，表示两个顶点之间的双向关系。
  • 而在有向图中，边有方向性，表示一个顶点指向另一个顶点的单向关系。

稀疏图和稠密图：

此外，图还可以根据边或弧的多少分为稀疏图和稠密图。

如果任意两个顶点之间都存在边，则称为完全图。若无重复的边或顶点到自身的边，则称为简单图。

图的表示：

图的表示方式主要有两种：邻接矩阵和邻接表。

 邻接矩阵：

邻接矩阵是一个二维数组，用于表示图中顶点之间的关系。

对于无向图，邻接矩阵是对称的，即如果顶点i和顶点j之间存在一条边，那么邻接矩阵中第i行第j列的元素和第j行第i列的元素都为1，否则为0。

对于有向图，邻接矩阵不一定对称，因为边的方向性会导致邻接矩阵中的元素不同。

优点是直观、简单，可以快速判断任意两个顶点之间是否存在边。

缺点是对于稀疏图（即边数相对较少的图），邻接矩阵会浪费大量的存储空间。

邻接表：

邻接表是一种链式存储结构，用于表示图中顶点之间的关系。

对于每个顶点，邻接表中存储了与其相邻的顶点的信息（如顶点编号、边的权重等）。邻接表可以使用数组或链表来实现。

优点是存储效率高，尤其是对于稀疏图，可以避免浪费大量的存储空间。此外，邻接表还可以方便地添加、删除顶点和边，因此在动态图中得到了广泛应用。

  1. //邻接表的实现
  2. #include<iostream>  // 引入输入输出流库  
  3. using namespace std;  // 使用标准命名空间  
  4. // 定义全局变量  
  5. int head[100000], cnt;  // head数组用于存储每个节点的第一条边的编号，cnt用于记录边的数量  
  6. long long ans[1000000];  // 存储从源点到每个节点的最短距离  
  7. bool vis[1000000];  // 标记节点是否已被访问过  
  8. int m, n, s;  // m是节点的数量，n是边的数量，s是源点的编号  
  9. // 定义边的结构体  
  10. struct edge{
  11. 	int to;  // 边的终点节点编号  
  12. 	int nextt;  // 下一条边的编号  
  13. 	int wei;  // 边的权值（权重）  
  14. } edge[1000000];  // 存储所有边的数组  
  15. // 添加边的函数  
  16. void addedge(int x, int y, int z){
  17. 	edge[++cnt].to = y;  // 设置新边的终点  
  18. 	edge[cnt].wei = z;   // 设置新边的权值  
  19. 	edge[cnt].nextt = head[x];  // 设置新边的下一条边为节点x的当前第一条边  
  20. 	head[x] = cnt;  // 更新节点x的第一条边为新添加的边  
  21. }
  22. int main(){
  23. 	cin >> m >> n >> s;  // 输入节点的数量m，边的数量n，以及源点的编号s  
  24. 	// 初始化ans数组为一个大数（表示无穷大）  
  25. 	for (int i = 1; i <= n; i++){
  26. 		ans[i] = 2147483647;  // 2147483647是int类型的最大值  
  27. 	}
  28. 	ans[s] = 0;  // 源点到自身的距离是0  
  29. 	// 输入每条边的信息并添加到图中  
  30. 	for (int i = 1; i <= n; i++){
  31. 		int a, b, c;
  32. 		cin >> a >> b >> c;  // 输入边的起点、终点和权值  
  33. 		addedge(a, b, c);  // 添加边到图中  
  34. 	}
  35. 	
  36.  
  37.  
  38.    return 0;
  39. }

小总结：

邻接矩阵是一个二维数组，其中每个元素表示相应顶点对之间的边的权重。对于无向图，邻接矩阵是对称的；对于有向图，邻接矩阵不一定对称。邻接表则是一种链式存储结构，对于每个顶点，都有一个与之相邻的顶点的链表。

除了邻接矩阵和邻接表之外，还有一些其他的图的表示方式，如边集数组、邻接多重表等。 

图的基本操作：

图的基本操作包括创建图、添加顶点、添加边、删除顶点、删除边、查找顶点、查找边等。这些操作是图的基本功能，对于实现图的算法和应用具有重要意义。

创建图：

根据给定的顶点集合和边集合创建一个图。这通常涉及到为顶点分配内存空间，并设置相应的属性。

插入顶点：

向图中添加新的顶点。这可能需要重新分配内存空间以容纳新的顶点，并更新相关的数据结构。

删除顶点：

从图中移除指定的顶点。这可能需要释放该顶点所占用的内存空间，并更新与该顶点相关的边和邻接表等信息。

插入边：

向图中添加新的边。这可能需要更新邻接表或邻接矩阵，以反映新的边的存在。

删除边：

从图中移除指定的边。这可能需要更新邻接表或邻接矩阵，以反映边的删除。

查找顶点：

根据给定的顶点标识查找图中的顶点。这通常涉及到遍历顶点集合或使用哈希表等数据结构进行快速查找。

查找边：

根据给定的起点和终点查找图中的边。这可能需要遍历邻接表或邻接矩阵，以找到与给定起点和终点相关的边。

图的遍历：

图的遍历是图论中的重要概念，主要包括深度优先遍历（DFS）和广度优先遍历（BFS）。深度优先遍历从某个顶点出发，尽可能深地访问图的分支，直到达到某个终点。广度优先遍历则从某个顶点出发，逐层访问与当前顶点相邻的顶点。

常见的图算法：

最短路径算法：

  • Dijkstra算法：用于计算图中单个源点到其他所有顶点的最短路径。它采用贪心策略，逐步找到从源点到其他顶点的最短路径。迪杰斯特拉算法-CSDN博客
  • Floyd算法：也称为Warshall算法，用于计算图中所有顶点对之间的最短路径。它使用一个二维数组来存储顶点对之间的最短距离，并通过动态规划的思想逐步更新这个数组。
  • Bellman-Ford算法：适用于带有负权边的图，用于计算单源最短路径。它通过对所有边进行|V|-1次松弛操作（V为顶点数），找到从源点到其他顶点的最短路径。此外，该算法还可以检测是否存在负权环。

最小生成树算法：最小生成树-CSDN博客

  • Prim算法：从某个顶点开始，逐步添加边以构建最小生成树，直到所有顶点都被包含在内。每次添加边时，选择连接已选顶点和未选顶点的最小权边。
  • Kruskal算法：将所有边按照权值从小到大排序，然后依次选择边，如果添加该边不会形成环，则将其加入最小生成树中。该算法基于边的选择，直到选择了n-1条边（n为顶点数）。

拓扑排序：

  • Kahn算法：用于有向无环图（DAG）的拓扑排序。它通过不断删除入度为0的顶点并更新其邻接顶点的入度，直到所有顶点都被删除或存在环为止。
  • DFS（深度优先搜索）：也可以用于拓扑排序。通过深度优先遍历图，并在访问每个顶点时将其加入结果列表，可以得到一种拓扑排序。

图的遍历：

  • DFS（深度优先搜索）：从某个顶点开始，沿着图的边深入搜索，直到达到目标顶点或无法再深入为止，然后回溯并继续搜索其他路径。
  • BFS（广度优先搜索）：从某个顶点开始，逐层访问邻接顶点，直到访问完所有顶点。它使用一个队列来保存待访问的顶点。

匹配算法：

  • 匈牙利算法：用于求解二分图的最大匹配问题。它通过不断寻找增广路径并更新匹配，直到无法再找到增广路径为止。

网络流算法：

  • Edmonds-Karp算法：用于求解最大流问题。它基于增广路径的思想，不断寻找从源点到汇点的路径并更新流量，直到无法再找到增广路径为止。

相关题目：

题目：查找文献

题目描述

小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个（也有可能没有）参考文献的链接指向别的博客文章。小 K 求知欲旺盛，如果他看了某篇文章，那么他一定会去看这篇文章的参考文献（如果他之前已经看过这篇参考文献的话就不用再看它了）。

假设洛谷博客里面一共有 n(n≤10^5) 篇文章（编号为 1 到 n）以及 m(m≤10^6) 条参考文献引用关系。目前小 K 已经打开了编号为 1 的一篇文章，请帮助小 K 设计一种方法，使小 K 可以不重复、不遗漏的看完所有他能看到的文章。

这边是已经整理好的参考文献关系图，其中，文献 X → Y 表示文章 X 有参考文献 Y。不保证编号为 1 的文章没有被其他文章引用。

请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。

输入格式

共 1m+1 行，第 1 行为 2 个数，n 和 m，分别表示一共有 n(n≤10^5) 篇文章（编号为 1 到 n）以及m(m≤10^6) 条参考文献引用关系。

接下来 m 行，每行有两个整数 X,Y 表示文章 X 有参考文献 Y。

输出格式

共 2 行。 第一行为 DFS 遍历结果，第二行为 BFS 遍历结果。

输入输出样例

输入 #1复制

  1. 8 9
  2. 1 2
  3. 1 3
  4. 1 4
  5. 2 5
  6. 2 6
  7. 3 7
  8. 4 7
  9. 4 8
  10. 7 8

输出 #1复制

  1. 1 2 5 6 3 7 8 4 
  2. 1 2 3 4 5 6 7 8

代码：
  1. #include<iostream>  
  2. #include<algorithm>  
  3. #include<vector>  
  4. #include<queue>  
  5. using namespace std;
  6.  
  7. // 记录边的结构体  
  8. struct fun {
  9. 	int u; // 起点  
  10. 	int v; // 终点  
  11. };
  12.  
  13. // 存具体信息的二维数组，每个元素是一个向量，用于存储与这个顶点相连的所有边的索引  
  14. vector<int> arr[1000200];
  15.  
  16. // 存边的结构体vector数组  
  17. vector<fun> brr;
  18.  
  19. // 排序规则，如果v相同则按u排序  
  20. bool cmp(fun x, fun y) {
  21. 	if (x.v == y.v) // 这里应该使用双等号进行比较  
  22. 		return x.u < y.u;
  23. 	else
  24. 		return x.v < y.v;
  25. }
  26.  
  27. // 标记是否访问过的数组  
  28. bool vis1[1000200] = { 0 }, vis2[1000200] = { 0 };
  29.  
  30. // DFS函数  
  31. void dfs(int x) {
  32. 	vis1[x] = 1; // 标记为已访问  
  33. 	cout << x << " "; // 输出当前访问的顶点  
  34. 	for (int i = 0; i < arr[x].size(); i++) {// 遍历与x相连的所有边   
  35. 		int p = brr[arr[x][i]].v; // 获取边的终点  
  36. 		if (!vis1[p]) dfs(p); // 如果终点未被访问，则继续DFS  
  37. 	}
  38. }
  39.  
  40. // BFS函数  
  41. void bfs(int x) {
  42. 	queue<int> q; // 创建一个队列用于BFS  
  43. 	q.push(x); // 将起始点加入队列  
  44. 	cout << x << " "; // 输出起始点  
  45. 	vis2[x] = 1; // 标记为已访问  
  46. 	while (!q.empty()) { // 当队列不为空时继续循环    
  47. 		int f = q.front(); // 获取队列的第一个元素  
  48. 		for (int i = 0; i < arr[f].size(); i++) {// 遍历与f相连的所有边    
  49. 			int p = brr[arr[f][i]].v; // 获取边的终点  
  50. 			if (!vis2[p]) {// 如果终点未被访问  
  51. 				q.push(p); // 将终点加入队列  
  52. 				cout << p << " "; // 输出终点  
  53. 				vis2[p] = 1; // 标记为已访问  
  54. 			}
  55. 		}
  56. 		q.pop(); // 弹出队列的第一个元素  
  57. 	}
  58. }
  59.  
  60. int main() {
  61. 	int n, m;
  62. 	cin >> n >> m; // 输入顶点数和边数  
  63. 	for (int i = 0; i < m; i++) {
  64. 		int uu, vv;
  65. 		cin >> uu >> vv; // 输入每条边的起点和终点  
  66. 		brr.push_back({ uu, vv }); // 将边加入brr向量  
  67. 	}
  68. 	sort(brr.begin(), brr.end(), cmp); // 对边按照排序规则进行排序  
  69. 	for (int i = 0; i < m; i++) {
  70. 		arr[brr[i].u].push_back(i); // 根据边的起点，将边的索引添加到对应顶点的向量中
  71.          /*综合起来，arr[brr[i].u].push_back(i); 这行代码的意思是：
  72.          1.  获取 brr 向量中第 i 个元素的 u 成员的值。
  73.          2.  使用这个值作为索引，访问 arr 向量中的对应子向量。
  74.          3.  向这个子向量的末尾添加整数 i。*/  
  75. 	}
  76. 	dfs(1); // 从顶点1开始进行DFS遍历  
  77. 	printf("\n"); // 输出换行  
  78. 	bfs(1); // 从顶点1开始进行BFS遍历  
  79. 	return 0;
  80. }

 题目：最小生成树

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 N,M，表示该图共有 N 个结点和 M 条无向边。

接下来 M 行每行包含三个整数 Xi​,Yi​,Zi​，表示有一条长度为 Zi​ 的无向边连接结点 Xi​,Yi​。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

输入输出样例

输入 #1复制

  1. 4 5
  2. 1 2 2
  3. 1 3 2
  4. 1 4 3
  5. 2 3 4
  6. 3 4 3

输出 #1复制

7
说明/提示

数据规模：

对于 20% 的数据，N≤5，M≤20。

对于 40% 的数据，N≤50，M≤2500。

对于 70% 的数据，N≤500，M≤10^4。

对于 100% 的数据：1≤N≤5000，1≤M≤2×10^5，1≤Zi​≤10^4。

样例解释：

所以最小生成树的总边权为 2+2+3=7。

代码：
  1. #include<iostream> // 包含输入输出流库  
  2. #include<cstdio>   // 包含标准输入输出库  
  3. #include<algorithm> // 包含算法库，用于 sort 函数  
  4. #include<cstring>  // 包含字符串处理库，虽然在这段代码中并未使用  
  5. #include<queue>    // 包含队列库，虽然在这段代码中并未使用  
  6.   
  7. using namespace std; // 使用标准命名空间  
  8.   
  9. // 定义一个结构体来存储边的信息  
  10. struct Edge{  
  11. 	int u, v, w; // u 和 v 是边的两个端点，w 是边的权重  
  12. }edge[2000000]; // 存储边的数组，最多可以存储 2000000 条边  
  13.   
  14. int fa[6000], n, m, ans, eu, ev; // fa 是并查集数组，n 是顶点数，m 是边数，ans 是最小生成树的权重和，eu 和 ev 用于存储查找得到的集合代表元素  
  15. int cnt; // 用于计数已选择的边的数量  
  16.   
  17. // 比较函数，用于边的排序  
  18. bool cmp(Edge a, Edge b)  
  19. {  
  20. 	return a.w < b.w; // 按边的权重升序排序  
  21. }  
  22.   
  23. // 查找函数，用于并查集  
  24. int find(int x)   
  25. {  
  26. 	while (x != fa[x]) // 如果 x 不是自己集合的代表元素  
  27. 		x = fa[x] = fa[fa[x]]; // 路径压缩，将 x 直接连接到它的根节点，并返回根节点  
  28. 	return x;  
  29. }  
  30.   
  31. // Kruskal 算法实现函数  
  32. void kruskal()  
  33. {  
  34. 	int b = n - 1; // 最小生成树需要 n - 1 条边  
  35. 	sort(edge, edge + m, cmp); // 对边按权重进行排序  
  36. 	for (int i = 0; i < m; i++) { // 遍历每条边  
  37. 		eu = find(edge[i].u), ev = find(edge[i].v); // 查找边的两个端点所在集合的代表元素  
  38. 		if (eu == ev) continue; // 如果两个端点已经在同一个集合中（即已经连通），则跳过这条边  
  39. 		ans += edge[i].w; // 累加这条边的权重到最小生成树的权重和中  
  40. 		fa[ev] = eu; // 合并两个集合  
  41. 		cnt++; // 已选择的边数加1  
  42. 		if (cnt == b) break; // 如果已选择的边数达到 n - 1，则最小生成树构建完成，退出循环  
  43. 	}  
  44. 	if (cnt < b) { // 如果选择的边数少于 n - 1  
  45. 		cout << "orz" << endl; // 输出"orz"表示图不连通  
  46. 		ans = 0; // 重置最小生成树权重和为0  
  47. 		return; // 返回，不再执行后续代码  
  48. 	}  
  49. }  
  50.   
  51. int main()  
  52. {  
  53. 	cin >> n >> m; // 读入顶点数和边数  
  54. 	for (int i = 1; i <= n; i++) fa[i] = i; // 初始化并查集，每个顶点自成一个集合  
  55. 	for (int i = 0; i < m; i++) { // 读入每条边的信息  
  56. 		cin >> edge[i].u >> edge[i].v >> edge[i].w;  
  57. 	}  
  58. 	kruskal(); // 调用 Kruskal 算法函数构建最小生成树  
  59. 	if(ans != 0) // 如果最小生成树权重和不为0（即图连通）  
  60. 		printf("%d", ans); // 输出最小生成树权重和  
  61. 	return 0; // 程序结束  
  62. }

同类型题目会逐渐增加（未完待续）

图的应用：

图在许多领域都有广泛的应用，如社交网络、计算机网络、电路设计、机器学习等。通过应用图的算法，可以解决许多实际问题，如最短路径问题、最小生成树问题、网络流问题等。

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号