图的三种存储方式

大家好，欢迎来到IT知识分享网。

图论开坑–图存储的三种方式

图是一种常见的抽象模型，在计算机专业中的应用尤其广泛。数据结构和算法是计算机专业的必修课程，而图则是数据结构和算法课上的必修内容，图论问题是算法竞赛的常客，图的重要性可见一斑。其它算法学的再好，不会图论的话，那永远也称不上是算法高手。那么问题就来了，怎么学习图算法呢。

要学习图算法，首先咱得有个图不是，所以学习图算法的第一关就这么来了–怎样能创建/存储图呢？

一.基本概念

再讲具体的存储之前，先讲一下图的基本概念
图可以描述现实世界的许多状态，由结点和结点之间的连线组成，图的相同与否仅与结点和边的数量有关和连线的具体长度和结点的位置无关。比如：

上面的两个图就表示了同一个图形。当然，这里说的相同与否是在同一类型下的图的比较。图可以分成很多种类。

1.可以通过边有无方向把图分成有向图和无向图和混合图
(1)每一条边都是无向边的图称为无向图，上面图中的两个图都是无向图。
(2)每一条边都是有向边的图称为有向图，下面图中的图就是有向图。

(3)如果图中的一些边是有向边，一些边是无向边，则称这个图是混合图。

2.除了看边的方向，还可以通过看边是否有权把边分成无权图和加权图。

(1)无权图：顾名思义，边上没有权值的图就叫无权图，上述所有的图都属于无权图。
(2)加权图：在无权图的基础上给每条边加上权值，就称为加权图。如下图所示，边上的数值就是权值。

3.将以上两点结合可得多种图
(1)无向无权图，边没有权值，没有方向
(2)有向无权图，边有方向，无权值
(3)加权无向图，边有权值，但没有方向
(4)加权有向图，边有权值，有方向
这些图就是1. 2. 示例图的结合，这里就不在特意放图描述了

4.度的概念和相关定理
在一个图中，和一个结点相关联的边数就称为该结点的度数。据此有以下定理。
(1)每个图中，结点的度数总和等于边数的两倍。

(2)在任何图中，度数为奇数的结点必定是偶数个。

5.子图和补图
子图：设图G=<V,E>，如果有图G’=<V’,E’>，且E’⊆E，V’⊆V，则称G’为G的子图。如果G的子图包含G的所有结点，则称该子图为G的生成子图。

补图：设图G’=<V’,E’>是图G=<V,E>的子图，若给定另外一个图G’’=<V’’,E’’>，使得E’’=E-E’，且V’‘中仅包含E’‘的边所关联的结点，则称G’‘是子图G’相对于图G的补图。

简单的梳理了一下图的基本知识，关于图存储方式的学习就正式开始了。

二.邻接矩阵

用二维数组表示，定义全局变量G [row] [col],其中row是矩阵行数，col是矩阵列数。而G [i] [j]表示结点i和结点j之间存在路径的情况，无权图中，0表示不存在路径，1表示存在路径。有权图中，G [i] [j]中的值是边的权值，当路径不存在时用无穷大表示。无向图中G [i] [j]==G [j] [i] ；而有向图中G [i] [j] !=G [j] [i].

无向图(无权)

#include<stdio.h> #include<iostream> using namespace std; const int row = 10; const int col = 10; int G[row][col]; int main() { int n, m, u, v; cin >> n >> m; while (m--) { cin >> u >> v; G[u][v] = 1; G[v][u] = 1; } for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { cout << G[i][j] << ' '; } cout << endl; } return 0; } 

无向图(有权)

#include<stdio.h> #include<iostream> using namespace std; const int row = 10; const int col = 10; const int INF = 99999; int G[row][col]; void init() { for (int i = 0;i < row;i++) { for (int j = 0;j < col;j++) { G[i][j] = INF; } } } int main() { init(); int n, m, u, v, w; cin >> n>> m; while (m--) { cin >> u >> v >> w; G[u][v] = w; G[v][u] = w; } for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { cout << G[i][j] << ' '; } cout << endl; } return 0; } 

有向图(无权)

#include<stdio.h> #include<iostream> using namespace std; const int row = 10; const int col = 10; int G[row][col]; int main() { int n, m, u, v; cin >> n >> m; while (m--) { cin >> u >> v; G[u][v] = 1; } for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { cout << G[i][j] << ' '; } cout << endl; } return 0; } 

有向图(有权)

#include<stdio.h> #include<iostream> using namespace std; const int row = 10; const int col = 10; const int INF = 99999; int G[row][col]; void init() { for (int i = 0;i < row;i++) { for (int j = 0;j < col;j++) { G[i][j] = INF; } } } int main() { init(); int n, m, u, v, w; cin >> n >> m; while (m--) { cin >> u >> v >> w; G[u][v] = w; } for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { cout << G[i][j] << ' '; } cout << endl; } return 0; } 

邻接矩阵适合于稠密图，且代码的实现也很简单，在此基础上对图进行的操作也比较简单方便。

但要是在像ACM这样的算法竞赛中遇到了有关图的问题，直接采用邻接矩阵的方式存储的话，十有八九会死的相当凄惨，因为这种方法有一个非常大的缺点，它的空间复杂度非常之大，达到了O(V^2)。在现实生活中也无法满足所有的情况，以城市之间的交通为例，两个城市之间经常会出现有多条道路相通的情况，用图的方式表示城市交通图非常合适，但是用邻接矩阵存储的话是没有办法存储两个结点之间的多条边的，即无法存储重边。

因为有上述问题，也就引出了下面的存储方式。

三.邻接表

邻接表的原理就是对每个在图上的顶点都创建了一个单链表，把该顶点上的边都存储在链表上。头节点存储图上的顶点信息，由顶点号和指向下一个结点的指针组成。其它结点由三部分组成，和头节点表示的顶点有边相关联的顶点号，边的权值和指向下一个结点的指针。如下图所示。


这就是图和邻接表的对应关系，用链表来存储，极大的优化了存储效率，但是链表并不好实现，也不好操作，所以很多人到这里就会感到头疼。的确，直接的利用链表去实现图的存储会比较麻烦，但C++的STL库是一个非常有用的工具，其中的vector就可以很好的替代表。

代码

#include<stdio.h> #include<iostream> #include<vector> using namespace std; const int N = 100; struct edge//定义边的结构体 { int from;//边的起点 int to;//边的终点 int w;//权值 edge(int a, int b, int c) { from = a; to = b; w = c; } }; vector<edge> e[N];//vector的数组实现邻接表，它的每一个存储单元都可以作为链表去使用 int main() { int n, m; cin >> n >> m;//输入n个结点,m条边 for (int i = 1;i <= n;i++) { e[i].clear(); } while (m--) { int from, to, w; cin >> from >> to >> w;//输入每条边的起点，终点，权值 e[from].push_back(edge(from, to, w));//将边送入作为起点的结点对应的“链表”中 } for (int i = 1;i <= n;i++)//输出每个结点所关联的边的情况 { if (e[i].size() > 0) { cout << "结点" + i << ' '; cout << "的边有" + e[i].size() << "个，分别为："; for (int j = 0;j < e[i].size();j++) { printf("%d %d %d; ", e[i][j].from,e[i][j].to,e[i][j].w); } cout << endl; } } } 

像上面所说，邻接表把邻接矩阵最被人诟病的空间复杂度的问题解决了，空间复杂度只有O(V+E)了，按理来说人们这时候就可以用这种方式把图存储好，一起开心的去研究图论问题了。但是人的贪欲是无止境的，有了邻接表，人们还想得到空间效率更高的存储方式。于是，欲望驱动大脑，思维的火花一闪，前向星出现了。

四.链式前向星

链式前向星和邻接表的思想非常相似，首先要先建一个结构体数组struct edge表示边,包含有int to,int next,int w三个数据域，分别表示边的终点，下一条边和边的权值。

struct edge { int to; int next; int w; }; 

除此之外还要定义一个静态数组head[]，head的下标是结点号，对应的内容是该结点的第一条边。当head[i]=j时，表示i结点的第一个边是j，即edge[j]。因为在结构体中定义了三个数据域，其中next便是指下一条边，所以可以一步步找到其它所有边；通过to可以找到其它有边相连的结点。

此外存储边的时候，要设置addedge()函数，每新增一条边，to,next,head等信息都可能更新。

void addedge(int u, int v, int w) { e[cnt].to = v; e[cnt].w = w; e[cnt].next = head[u]; head[u] = cnt++; } 

代码

#include<stdio.h> #include<iostream> #include<vector> using namespace std; const int N = 100; struct edge { int to; int next; int w; }; edge e[N]; int head[N]; int cnt=0; void addedge(int u, int v, int w) { e[cnt].to = v; e[cnt].w = w; e[cnt].next = head[u];//指向结点u上一次存边的位置 head[u] = cnt++;//更新最新的存放位置 } int main() { for (int i = 0;i < N;i++) { e[i].next = -1;//刚开始每个边都没有下一个边 head[i] = -1;//刚开始不存在从结点i出发的边 } int u, v, w, n, m,t; cin >> n >> m; while (m--) { cin >> u >> v >> w; addedge(u, v, w); } for (int i = 0;i < N;i++) { if (head[i] != -1) { for (int j = head[i];j != -1;j = e[j].next) { printf("边为%d %d %d\n", i, e[j].to, e[j].w); } } } return 0; } 

前向星比邻接表更节省空间，是空间效率最高的方法。

如果您觉得这篇文章对您有所帮助，欢迎关注我的微信公众号–【悬浮流星】，阅读更多的类似文章。如果您发现该文章有错误或不足之处，也欢迎批评指正。