图是一个好东西,能够使用图来模拟或解决很多生活问题,同时在各大比赛上都少不了有关于图的问题.图是关系与顶点与边的,那么我们该如何来存入图的信息呢?
(1)直接存边
我们开一个数组,数组里每个元素是图的一条边。其中存的每一条边都包含这些信息:顶点 v 与 u , 边的权值。
这就用到结构体数组,对于无向图,只需要存两个顶点 , 有向图的话需要区分起点、终点。
// 直接存边 struct edge{ int start; // 起点 int to; // 终点 int cost; // 花费(权值) }G[MAXN];
这样做有个缺点 , 每次想要知道两个点之间是否有连边(或者说一条边是否存在),都需要遍历整个数组进行查找.而且如果没有进行排序的话 , 还不能使用二分查找( O(log n) ) , 只能顺序查找 ( O(n) ) , 对于需要多次查找的情况 , 显然是不合适的 . 但在使用 Kruskal 算法求最小生成树的时候能用到这种方法。
应用:
1. 由于直接存边的遍历效率低下,一般不用于遍历图。
2. 在 Kruskal 算法 中,由于需要将边按边权排序,需要直接存边。
3. 在有的题目中,需要多次建图(如建一遍原图,建一遍反图),此时既可以使用多个其它数据结构来同时存储多张图,也可以将边直接存下来,需要重新建图时利用直接存下的边来建图。
(2)邻接矩阵
邻接矩阵的英文名是 adjacency matrix。它的形式是 bool adj[n][n] , 这里需要存 n 个节点,adj[x][y] 表示节点x与节点y 之间是否有边,如果边有权值的话 , 用 int adj[n][n] 直接把边权存进去。
无向图需要 x 与 y 有边则需要存 adj[x][y] 与 adj[y][x] 表示有双向导通 , 有向图则 x -> y 则存 adj[x][y] 就行了 .
#include<bits/stdc++.h> using namespace std; int adj[MAXN][MAXN],n,m; // n 为节点数 , m 为边数 int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { int x,y,v; scanf("%d %d %d",&x,&y,&v); adj[x][y]=adj[y][x]=v;//向x,y间添加一个权值为v的边(无向) //有向图为adj[x][y]=v; } return 0; }
它的优点是 , 在查询两点间是否有边时 , 时间复杂度为 O(1) , 但是缺点是它存边却是极占内存,它的空间(内存)复杂度是 O(n^2) . 对于一个稀疏的图(边相对于点数的平方比较少)来说,用邻接矩阵来存的话,成本偏高。
如果n*m超过3×1e7,内存就超过128MB了,所以当看到类似的 n,m=<1e4时就不要用邻接矩阵 , 需要考虑其他的存储方式。
(3)邻接表
邻接表英文名是 adjacency list . 邻接表是链状的,它实际上是一个离散化的邻接矩阵。edge[i] 代表第 i 号节点 , .to[] 表示到与别的节点联通的路径 ,.v[ ]是 i 到 edge[i].to[j] 号节点的权值, .len 用来标记一共有几个联通 i 号节点的边 (也称节点i的出度)
#include<bits/stdc++.h> using namespace std; struct node { int to[1010]; //存储与当前节点相接的节点 int v[1010]; //两节点间的边的权值 int olen; //出度 //int ilen; //入度 }edge[1010]; int n,m; int main() { scanf("%d %d",&n,&m); for(int i=1;i<=m;i++) { int x,y,v1; scanf("%d %d %d",&x,&y,&v1); edge[x].len++;edge[y].len++; edge[x].to[edge[x].len]=y;edge[y].to[edge[x].len]=x; edge[x].v[edge[x].len]=edge[y].to[edge[x].len]=v1;//向x,y间添加一个权值为v的边(无向) /*有向图为 edge[x].len++; edge[x].to[edge[x].len]=y; edge[x].v[edge[x].len]=v1; */ } return 0; }
应用:
1. 存各种图都很适合,除非有特殊需求(如需要快速查询一条边是否存在,且点数较少,可以使用邻接矩阵)。
2. 尤其适用于需要对一个点的所有出边进行排序的场合。
(4)链式前向星
本质上是用链表实现的邻接表,核心代码如下:
// C++ Version // head[u] 和 cnt 的初始值都为 -1 void add(int u, int v) { nxt[++cnt] = head[u]; // 当前边的后继 head[u] = cnt; // 起点 u 的第一条边 to[cnt] = v; // 当前边的终点 } // 遍历 u 的出边 for (int i = head[u]; ~i; i = nxt[i]) { // ~i 表示 i != -1 int v = to[i]; }
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程