图的几种存储方法

作为我们学习图论的基点，我们有必要了解几种常用的图存储方法，并比较他们的优劣与适用范围。

本文参考了https://oi-wiki.org/graph/save/

直接存边：

由于直接存边的遍历效率低下，一般不用于遍历图。

在 Kruskal算法中，由于需要将边按边权排序，需要直接存边。

在有的题目中，需要多次建图（如建一遍原图，建一遍反图），此时既可以使用多个其它数据结构来同时存储多张图，也可以将边直接存下来，需要重新建图时利用直接存下的边来建图。

 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 int pos1=0;//绝对位置 
 5 int tire[100][30];
 6 int end[100];//储存是否为末尾 
 7 void insert (string s){
 8     int start=0;
 9     for (int i=0;i<s.length();i++){
10         int pos2=s[i]-'a';
11         if (!tire[start][pos2]){
12             tire[start][pos2]=++pos1;
13         }
14         start=pos1;
15     }
16     end[start]=1;//给末尾标记上 
17 }
18 bool find(string s){
19     int start=0;
20     for (int i=0;i<s.length();i++){
21         int pos2=s[i]-'a';
22         if (!tire[start][pos2])
23             return false;
24         start=tire[start][pos2];
25     }
26     return end[start];//查找末尾是否有标记 
27 }
28 int main(){
29     insert("ans");
30     cout<<find("ansser")<<find("ans")<<find("an");
31     return 0;
32 }

 邻接矩阵存储：

邻接矩阵只适用于没有重边（或重边可以忽略）的情况。

其最显著的优点是可以 O（1）查询一条边是否存在。

由于邻接矩阵在稀疏图上效率很低（尤其是在点数较多的图上，空间无法承受），所以一般只会在稠密图上使用邻接矩阵。

代码如下：

 1 #include <iostream>
 2 using namespace std;
 3 int adj[200][200];
 4 int vis[200];
 5 int k;//顶点数
 6 int n;//边数 
 7 void insert (int u,int v,int w){
 8     adj[u][v]=w;
 9     adj[v][u]=w;//无向图需要存两条，有向图存一条即可 
10 }
11 bool find_root(int u,int v){
12     return adj[u][v];
13 }
14 void dfs(int u){
15     if (vis[u]) return ;
16     vis[u]=true;
17     cout<<u<<" ";
18     for (int i=1;i<=k;i++){
19         if (adj[u][i])
20             dfs(i);
21     }
22 }
23 int main(){
24     cin>>k>>n;
25     for (int i=1;i<=n;i++){
26         int u,v;
27         cin>>u>>v;
28         insert(u,v,1);
29     }
30     dfs(1);
31     return 0;
32 }

邻接表存储：

存各种图都很适合，除非有特殊需求（如需要快速查询一条边是否存在，且点数较少，可以使用邻接矩阵）。

尤其适用于需要对一个点的所有出边进行排序的场合。

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 vector<vector<int> >adj;
 5 int k;//点数 
 6 int n;//边数 
 7 int vis[200];
 8 bool find_root(int u,int v){
 9     for (int i=0;i<adj[u].size();i++){
10         if (adj[u][i]==v)
11             return true;
12     }
13     return false;
14 }
15 void dfs(int u){
16     if (vis[u]) return ;
17     vis[u]=true;
18     cout<<u<<" ";
19     for (int i=0;i<adj[u].size();i++){
20         dfs(adj[u][i]);
21     }
22 }
23 int main(){
24     cin>>k>>n;
25     adj.resize(k+1);//初始化
26     for (int i=1;i<=n;i++){
27         int u,v;
28         cin>>u>>v;
29         adj[u].push_back(v);
30     }
31     dfs(1);
32     return 0;
33 }

链式前向星：

存各种图都很适合，但不能快速查询一条边是否存在，也不能方便地对一个点的出边进行排序。

优点是边是带编号的，有时会非常有用，而且如果 cnt 的初始值为奇数，存双向边时 i ^ 1 即是 i 的反边（常用于网络流）。

 1 #include <iostream>
 2 using namespace std;
 3 int cnt=0;//边的标号
 4 int nxt[200];//储存和本条边同出发点的上一条边
 5 int head[200];//储存开始节点标号为i的最新边
 6 int to[200];//储存标号为i的边的终止点
 7 int w[200];//储存标号为i的边的权重 
 8 int k;//点数 
 9 int n;//边数 
10 int vis[200];
11 void insert(int u,int v,int w1){
12     nxt[++cnt]=head[u];
13     head[u]=cnt;
14     to[cnt]=v;
15     w[cnt]=w1;
16 }
17 bool find_root(int u,int v){
18     for (int i=head[u];i;i=nxt[i]){
19         if (to[i]==v)
20             return true;
21     }
22     return false;
23 }
24 void dfs(int u){
25     if (vis[u]) return ;
26     vis[u]=true;
27     cout<<u<<" ";
28     for (int i=head[u];i;i=nxt[i]){
29         dfs(to[i]);
30     }
31 }
32 int main(){
33     cin>>k>>n;
34     for (int i=1;i<=n;i++){
35         int u,v;
36         cin>>u>>v;
37         insert(u,v,1);
38         insert(v,u,1);//无向图存两次 
39     }
40     dfs(1);
41     return 0;
42 }