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

图论算法入门基础---图的储存---链式前向星详讲_链式前向星存图法

作者：我家小花儿 | 2024-04-14 03:21:57

赞

踩

链式前向星存图法

先给出离散数学上的概念：

有序对：

有两个元素x,y（允许x=y)按照一定的顺序排序成的二元组称作一个有序对或称序偶记作<x,y>，其中x是它的第一个元素，y是它的第二个元素;其性质：

1，当x!=y时，<x,y>！=<y,x>;

2, <x,y>=<u,v>的充分必要条件:x=u,y=v;这些性质是二元集所不具备的   比如{x,y}={y,x}无论x，y是否相等都成立;

无序积概念：

设A,B为任意的两个集合，称{{a,b} | a∈A&&b∈B }为A与B的无序积记作A与B的无序积，记作:A&B;方便起见A&B中的无序对{a,b}记作（a,b)，且允许a=b;无论a,b是否相等都有(a,b)=(b,a);因而有A&B=B&A；

V: vertex 顶点；

E: edge 边线；

笛卡尔积概念：

设A,B为集合，用A中的元素作为第一元素，B中元素作为第二元素构成的有序对，所有有序对构成的集合称作A和B的笛卡尔积，并记作AxB；符号表示为AxB={ <x,y> | x∈A&&y∈B }；

例如A={a,b},B={0,1,2}；

AxB={<a,0>,<a,1>,<a,2>,<b,0>,<b,1>,<b,2>}；

BxA={<0,a>,<0,b>,<1,a>,<1,b>,<2,a>,<2,b>};

图的定义：

无向图：无向图G是一个有序的二元组<V,E>；其中：

（1）V是一个非空有穷集，称作顶点集，其元素称作顶点或结点。

   (2) E是无序积V&V的有穷多重子集，称作边集，其元素称作无线边，简称边；

有向图：有向图D是一个有序的二元组<V,E>；其中;

(1)V定义同上；

   (2)E是笛卡尔积VxV的有穷多重子集，称作编辑，其元素称作有有向边，简称边； 

图片源于网络

该图为一个有向图；去掉箭头，将集合E改为无序对即为无向图；

接下来介绍三种图的储存方式：

1：邻接矩阵：优点：容易理解，实现简答，适用于稠密图（边多的图）；缺点不适合与稀疏图会造成巨大的空间浪费，是最暴力的方法了；

2：邻接表：优点与缺点都不突出，是算法竞赛中比较常用的做法；缺点是不易判定重边

3：链式前向星：缺点也是判重麻烦，还有就是难以理解，代码实现麻烦。要是理解后把代码模版背下来呢？     优点的话，据前人经验，几乎所有图论题都能用它做。这也是本文重点讲的。

邻接矩阵

对于矩阵而言，其表示意义为，第i行第j列的值为顶点i到顶点j的权值；记作m(i,j)

因此开一个二维数组就可以了；

  1. #include<iostream>
  2. const int N = 1007;
  3. int  m[N][N];
  4. /*
  5. 数据源于离散数学教材；
  6.   输入 n=4;
  7.   map:
  8. 	0,2,1,0
  9. 	0,0,1,0
  10. 	0,0,0,1
  11. 	0,0,1,1
  13. */
  14. int main() {
  15. 	int n;
  16. 	std::cin >> n;
  17. 	for (int i = 1; i <= n; i++) {
  18. 		for (int j = 1; j <= n; j++) {
  19. 			std::cin >> m[i][j];
  20. 		}//读入图
  21. 	}
  22. 	for (int i = 1; i <= n; i++) {
  23. 		for (int j = 1; j <= n; j++) {
  24. 			if (m[i][j]) {//如果两点可达
  25. 				std::cout << "The distance from " << i << " to " << j << " is " << m[i][j] << " units\n";
  26. 			}
  27. 		}
  28. 	}
  29. 	return 0;
  30. }

 

邻接表

邻接表的话用的是一个链表的思想，我们可以通过一个不定长的向量来表示它

k==v[i][j]表示的是  顶点i的第j条边到达顶点k;(这里的第几条边j只是为了方便遍历而表示的，i和k才是顶点）；

      v1,v2,v3,v4,v5

v1 :  0,0,0,0,1;

v2:   1,0,1,0,0;

v3:   0,0,0,0,1

v4:   1,0,1,0,0;

v5:   0,1,0,1,0;

这是一个可达矩阵

现在表示成向量形式：

vec1:  5       顶点1的第一条边到达5

vec2:  1,3    顶点2的第一条边到达1，第二条边到达3

vec3:   5,     顶点3的第一条边到达5

vec4:  1,3    顶点4的第一条边到达1，第二条边到达3

vec5:   2,4  顶点5的第一条边到达2，第二条边到达4

该表示方法不能表示边的权值；如果想要表示权值的话一般定义一个结构体：u为顶点，w为权值；

不考虑边权值：

  1. #include<iostream>
  2. #include<vector>
  3. using std::vector;
  4. const int N = 1007;
  5. vector<int> vec[N];
  6. /*
  7. 测试数据：
  8.  n,m   n个点m条边
  9.  v u  点v到点u；
  10.  输入：
  12.  5 8
  14.  1 5
  15.  4 1
  16.  4 3
  17.  2 3
  18.  2 1
  19.  3 5
  20.  5 2
  21.  5 4
  22. */
  23. int main() {
  24.     int n, m;
  25.     std::cin >> n >> m;
  26.     for (int i = 0; i < m; i++) {
  27.         int v, u;
  28.         std::cin >> v >> u;
  29.         vec[v].push_back(u);
  30.         //从边的角度读入
  31.     }
  32.     for (int i = 1; i <= n; i++) {
  33.         for (int j = 0; j < vec[i].size(); j++) {
  34.             std::cout << i << " to " << vec[i][j] << "    ";
  35.         }
  36.         std::cout << '\n';
  37.     }
  38.     return 0;
  39. }

 考虑边权值：

  1. #include<iostream>
  2. #include<vector>
  3. using std::vector;
  4. const int N = 1007;
  5. struct edge {
  6.     int u, w;
  7. };
  8. vector<edge> vec[N];
  9. /*
  10. 数据：
  11.  n,m   n个点m条边
  12.  v u  点v到点u；
  13.  输入：
  15.  5 8
  17.  1 5  2
  18.  4 1  2 
  19.  4 3  3
  20.  2 3  1
  21.  2 1  4
  22.  3 5  2
  23.  5 2  5
  24.  5 4  7
  25. */
  26. int main() {
  27.     int n, m;
  28.     std::cin >> n >> m;
  29.     for (int i = 0; i < m; i++) {
  30.         int v, u, w;
  31.         std::cin >> v >> u >> w;
  32.         vec[v].push_back({u,w});
  33.         //从边的角度读入
  34.     }
  35.     for (int i = 1; i <= n; i++) {
  36.         for (int j = 0; j < vec[i].size(); j++) {
  37.             std::cout<<" The distance of "<< i << " to " << vec[i][j].u << " is "<<vec[i][j].w<<"\t";
  38.         }
  39.         std::cout << '\n';
  40.     }
  41.     return 0;
  42. }

接下来介绍较难理解的链式前向星；其实还有一种叫前向星的，不过我们可以跳过，直接学习

链式前向星；

链式前向星

接下来以书上的有向图（如果是无向图的话，可以化为两个点通过两条有向箭头连接的有向图）的数据为例：

前面的方式都是通过点来找点，而这里通过点找边，边找边的方式遍历；

 我们可以设置几个数组来表示：

下列表示方法为网络上习惯的数组表示法：

to[cnt]   表示第cnt条边指向的终点，因此to[cnt]是一个顶点  cnt是第几条边；

w[cnt]  表示第cnt条边的权值；

ne[cnt] 表示的是第cnt条边指向的边  因此ne[cnt]是一条边；

h[u]      表示的是编号为u的点引出的最新的一条边  h[u]是一条边；

我们可以通过ne[cnt]来储存h[u]，h[u]=一条新边，来更新；

那么遍历的思路就是：从第x的顶点出发  找到它的一条边  即为h[x]，通过h[x]找出上一条边

即为 ne[h[x]]; 每次找到一条边那么就可以找到他的终点 即为 to[cnt]，也可以找出它的权值w[cnt];

这也就是一开始说的，点找边，边找边   边找边。。。。。

再来看下数组含义，h[u] :head 头部  头引出边

                                to[cnt]  : 没啥好说的，边指出点

                                w[cnt]  : worth        边指出权值；

                                 ne[cnt]:  next 给出边 找到下一个边；

这里面有一个非常强的映射关系，如果理解通了，学习到的就不只是这么一个存图了； 

下面给出具体实例加以理解：

这里特别注意 ne[1]=-1这个初始化，因为通过第一条边找不到下一条边了，因此初始化为-1；

那么：流程如下：为了偷懒    实例把权值都设为ww

cnt==1;

v1到v2 这条边 的终点v2  保留在to[1]中 to[1]=2 权值保留在w[1]中 w[1]=ww；

ne[1]=h[1];对此我们一开始可以对h全部赋值为-1；

h[1]=1;     h[1]中的1  指的是点 v1 而非cnt 

那么这条边录完了，cnt++；

cnt==2:

v1到v3 的终点为v2  to[2]=3  w[2]=ww;

ne[2]=h[1];

h[1]=2;  cnt++；

cnt==3:

v1到v4     to[3]=4 w[3]=ww;

ne[3]=h[1];

h[1]=3; cnt++;

cnt==4;

v1到v5     to[4]=4 w[4]=ww;

ne[4]=h[1];

h[1]=4; cnt++；

cnt==5；

注意：这里换起点了哦；

v2到v3 to[5]=3 w[5]=ww;

ne[5]=h[2];  (h[2]==-1)

h[2]=5;cnt++;

cnt==6

v2到v4 to[6]=3 w[6]=ww;

ne[6]=h[2];  

h[2]=6;cnt++;

cnt==7

v2到v5 to[7]=3 w[7]=ww;

ne[7]=h[2];  

h[2]=cnt;cnt++;

于是就把这张图储存下来了

给出几种代码，一种就是按上面的几个数组实现的，另一种就是用head+结构体封装了一下；以普通枚举实现

最后再给出遍历方式为bfs||dfs的代码;

 纯数组：

  1. #include<iostream>
  2. #include<algorithm>
  3. /*
  4. 测试数据：
  5.  5 7
  6. 1 2 1
  7. 1 3 2
  8. 1 4 3
  9. 1 5 2
  10. 2 3 1
  11. 2 4 2
  12. 2 5 4
  14. */
  15. const int N = 1e6;
  16. int h[N], to[N], ne[N], w[N];
  17. int cnt;
  18. void add(int u, int v, int ww) {
  19.     to[cnt] = v;
  20.     w[cnt] = ww;
  21.     ne[cnt] = h[u];
  22.     h[u] = cnt;
  23.     cnt++;
  24. }
  25. int main() {
  26.     int n, m;
  27.     std::cin >> n >> m;
  28.     //输入顶点数和边数
  29.     for (int i = 1; i <= n; i++) {
  30.         h[i] = -1;//将所有顶点的最新编号为-1；
  31.     }
  32.     for (int i = 1; i <= m; i++) {
  33.         int u, v, ww;
  34.         std::cin >> u >> v >>ww;
  35.         add(u, v, ww);//加入这条边；
  36.     }
  37.     //枚举所有的点：
  38.     for (int i = 1; i <= n; i++) {
  39.           //根据head 枚举所有边
  40.         for (int j = h[i]; j != -1; j=ne[j]) {
  41.             std::cout << "The distance of " << i << " to " << to[j] << " is " << w[j]<<'\n';
  42.         }
  43.  
  44.     }
  45.     return 0;
  46. }

结构体封装：h+edge;

  1. #include<iostream>
  2. const int N = 1e6;
  3. struct E {
  4.     int to , w, ne;
  5. };
  6. E edge[N];
  7. int h[N], cnt;
  8. void add(int u, int v, int ww) {
  9.     edge[cnt].to = v;
  10.     edge[cnt].w = ww;
  11.     edge[cnt].ne = h[u];
  12.     h[u] = cnt;
  13.     cnt++;
  14. }
  15.  
  16. int main() {
  17.     int n, m;
  18.     std::cin >> n >> m;
  19.     for (int i = 1; i <= n; i++)h[i] = -1;
  20.     for (int i = 1; i <= m; i++) {
  21.         int u, v, w;
  22.         std::cin >> u >> v >> w;
  23.         add(u, v, w);
  24.     }
  25.     for (int i = 1; i <= n; i++) {
  26.         for (int j = h[i]; j != -1; j = edge[j].ne) {
  27.             std::cout << "The distance of " << i << " to " << edge[j].to<< " is " << edge[j].w << '\n';
  28.         }
  29.     }
  30.     return 0;
  31. }

用bfs||dfs进行遍历：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<queue>
  4. using std::queue;
  5. const int N = 1e6;
  6. struct E {
  7.     int to, w, ne;
  8. };
  9. E edge[N];
  10. int h[N], cnt;
  11. bool vis[N];
  12. void add(int u, int v, int ww) {
  13.     edge[cnt].to = v;
  14.     edge[cnt].w = ww;
  15.     edge[cnt].ne = h[u];
  16.     h[u] = cnt;
  17.     cnt++;
  18. }
  19. void bfs(int n) {
  20.     queue<int>p;
  21.     //寻找所有起点；
  22.     for (int i = 1; i <= n; i++) {
  23.         if (vis[i] == true)continue;
  24.         p.push(i);
  25.         while (!p.empty()) {
  26.          int t = p.front();
  27.                  p.pop();
  28.                  if (vis[t] == true)continue;
  29.                  vis[t] = true;
  30.          for (int j = h[t]; j != -1; j = edge[j].ne) {
  31.              int v = edge[j].to;
  32.              p.push(v);
  33.              std::cout << "The distance of " << t << " to " << edge[j].to << " is " << edge[j].w << "\n";
  34.          }
  35.         }
  36.     }
  37.  
  38. }
  39.  
  40. // dfs:
  41. void dfs(int u) { 
  42.     if (h[u]==-1||vis[u]==true) return;
  43.         vis[u] = true;
  44.     for(int i=h[u];i!=-1;i=edge[i].ne){
  45.         dfs(edge[i].to);
  46.     std::cout << "The distance of" << u << " to " << edge[i].to << " is " << edge[i].w << '\n';
  47.     }
  48. }
  49. void reseach_dfs(int n) {
  50.  
  51. //一样的枚举所有起点，因为有了vis的剪枝，所以不必担心效率太低；
  52.     for (int i = 1; i <= n; i++) {
  53.         if (vis[i] == true)continue;
  54.         dfs(i);
  55.     }
  56. }
  57. int main() {
  58.     int n, m;
  59.     std::cin >> n >> m;
  60.     for (int i = 1; i <= n; i++)h[i] = -1;
  61.     for (int i = 1; i <= m; i++) {
  62.         int u, v, w;
  63.         std::cin >> u >> v >> w;
  64.         add(u, v, w);
  65.     }
  66.     std::cout << "bfs:\n";
  67.     bfs(n);
  68.     std::cout << "dfs:\n";
  69.     memset(vis, false, sizeof vis);
  70.     reseach_dfs(n);
  71.     return 0;
  72. }

推荐一个记忆化搜的题：

最大食物链计数 - 洛谷

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

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

  

闽ICP备14008679号