首页 > 代码库 > 图的存储方式
图的存储方式
图(Graph)是由点(Point)和边(Edge)组成的集合，要存储图就要存储他的点和边。显然点很容易存储，所以我们只要存储边，就可以存储整张图，所以现在我们只关注边。
»边的分类(Edge classification)
1.按是否有权值分类，可以把边分为有权边和无权边。多数时候，无权边可以看成是权值为1的边。
2.按是否有方向分类，可以把边分为有向边和无向边(双向边)。多数时候，无向边可以简单地分成两条有向边。
»边的存储方式(The ways of storaging edge)
1.邻接矩阵
优点：实现方便，运用矩阵算法或是位运算优化时更方便。
缺点：时空复杂度较大。
对于一张给定的图G，其中有n个点m条边，那么邻接矩阵为一个n*n的矩阵。在实现时，我们通常用一个二维数组a来表示这个矩阵，其中a[i][j]=w即表示i点与j点有一条权值为w的边，w=0表示不连通。
在无向图中，满足a[i][j]=a[j][i]，而有向图中并不一定满足。
如果是带权图，二维数组a中的元素表示边权，否则a为bool型，表示每条边是否存在。
在枚举每个节点的后继节点时，我们只要枚举所有n个节点，再通过邻接矩阵判断两点之间是否有边相连。
这样存储和遍历的复杂度都是O(n2),适合稠密图。
喜闻乐见的Code
1 #include<cstdio> 2 using namespace std; 3 #define maxn 1010 4 bool vis[maxn]; 5 int n,m,a[maxn][maxn]; 6 void dfs(int now) { 7 vis[now]=true; 8 for(int i=1;i<=n;i++) 9 if(!vis[i]&&a[now][i])10 dfs(i);11 }12 int main() {13 scanf("%d%d",&n,&m); //假设带权有向图有n个点m条边： 14 for(int i=1;i<=m;i++) {15 int u,v,w;16 scanf("%d%d%d",&u,&v,&w);17 a[u][v]=w; 18 }19 dfs(1);20 return 0;21 }
2.邻接表
优点：时空复杂度较小。
缺点：实现相对复杂。
邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。
每个结点包含两个元素，第一个元素代表该结点的数据，第二个元素为指针，指向下一个结点所在的位置。
这样我们可以将一个结点x的所有出边都建立一个表结点，按照顺序挂在x的表头结点后。
其中指针部分可以用数组模拟。
时间复杂度为O(n+m)，空间复杂度为O(n+m);
喜闻乐见的Code
1 /* 2 利用结构体实现邻接表; 3 */ 4 #include<cstdio> 5 using namespace std; 6 #define maxn 1010 7 #define maxm 1010 8 struct Graph { 9 int u,v,w,next; 10 Graph(int u=0,int v=0,int w=0,int next=0): 11 u(u),v(v),w(w),next(next) {} 12 }edge[maxm]; //注意无向图开edge要开两倍空间; 13 int head[maxn],cnt=0; 14 bool vis[maxn]; 15 void Add_edge(int u,int v,int w) { 16 edge[++cnt]=Graph(u,v,w,head[u]); 17 head[u]=cnt; 18 } 19 void dfs(int now) { 20 vis[now]=true; 21 for(int i=head[now];i;i=edge[i].next){ 22 int v=edge[i].v; 23 if(!vis[v]) 24 dfs(v); 25 } 26 } 27 int main() { 28 int n,m; 29 scanf("%d%d",&n,&m); 30 for(int i=1;i<=m;i++) { 31 int u,v,w; 32 scanf("%d%d%d",&u,&v,&w); 33 Add_edge(u,v,w); 34 // Add_edge(v,u,w); //无向图还需要建一条相反的边; 35 } 36 for(int i=1;i<=n;i++) 37 if(!vis[i])dfs(i); 38 return 0; 39 } 40 41 42 43 44 45 /* 46 利用数组实现邻接表; 47 */ 48 #include<cstdio> 49 using namespace std; 50 #define maxn 1010 51 #define maxm 1010 52 int to[maxm],w[maxm],next[maxn],head[maxn],cnt=0; 53 bool vis[maxn]; 54 void Add_edge(int u,int v,int w) { 55 to[++cnt]=v; 56 w[cnt]=w; 57 next[cnt]=head[u]; 58 head[u]=cnt; 59 } 60 void dfs(int now){ 61 vis[now]=true; 62 for(int i=head[now];i;i=next[i]); 63 if(!vis[to[i]])dfs(to[i]); 64 } 65 int main() { 66 int n,m; 67 scanf("%d%d",&n,&m); 68 for(int i=1;i<=m;i++) { 69 int u,v,w; 70 scanf("%d%d%d",&u,&v,&w); 71 Add_edge(u,v,w); 72 //Add_edge(v,u,w); 73 } 74 for(int i=1;i<=n;i++) 75 if(!vis[i])dfs(i); 76 return 0; 77 } 78 79 80 81 82 83 84 /* 85 利用stl中的vector和pair实现邻接表 86 */ 87 #include<cstdio> 88 #include<vector> 89 #include<utility> //包含pair 90 using namespace std; 91 #define maxn 1010 92 vector<pair<int,int> >g[maxn]; 93 //> > 中间的空格不能省去，否则会ce 94 bool vis[maxn]; 95 void dfs(int now) { 96 vis[now]=true; 97 for(int i=0;i<g[now].size();i++) 98 if(!vis[g[now][i].first]) 99 dfs(g[now][i].first);100 }101 int main() {102 int n,m;103 scanf("%d%d",&n,&m);104 for(int i=1;i<=m;i++) {105 int u,v,w;106 scanf("%d%d%d",&u,&v,&w);107 g[u].push_back(make_pair(v,w));108 // g[v].push_back(make_pair(u,w));109 }110 for(int i=1;i<=n;i++)111 if(!vis[i])dfs(i);112 return 0;113 }
3.边集数组
优点：方便对边进行排序以及整体处理。
缺点：难以对图进行遍历，难以求出每个节点的相邻节点。
边集数组是直接将读入的边用一个数组保存下来，而不将其和所连接的点挂起来。
一般在不需要遍历图，只需要这些边的信息时会使用这种方法，such as并查集。
当然也存在一种方法可以在直接保存所有边的情况下快速求出每个节点的出边达到遍历的目的。
这种做法叫做前向星。我们可以在读入所有边的信息后将所有边按照出点排序，这样同一个点连出的所有点就是连续的。
扫一遍后我们就可以知道每个节点的出边在哪一段区间。对于无向图，两个方向的边我们都要保存。由于要给所有边进行排序，所以时间复杂度相对较高。
时间复杂度O(mlog(m))，空间复杂度O(n+m)
喜闻乐见的Code
1 #include<algorithm> 2 #include<cstdio> 3 using namespace std; 4 #define maxn 1010 5 struct qxx { //QianXiangXing->qxx 6 int u,v,w; 7 qxx(int u=0,int v=0,int w=0): 8 u(u),v(v),w(w) {} 9 }a[maxn];10 int cnt,L[maxn],R[maxn];11 bool vis[maxn];12 bool cmp(qxx a,qxx b) {return a.u<b.u;}13 void Add_edge(int u,int v,int w) {14 a[++cnt]=qxx(u,v,w);15 }16 void dfs(int now) {17 vis[now]=true;18 for(int i=L[now];i<R[now];i++)19 if(!vis[a[i].v])20 dfs(a[i].v);21 }22 int main() {23 int n,m;24 scanf("%d%d",&n,&m);25 for(int i=1;i<=m;i++) {26 int u,v,w;27 scanf("%d%d%d",&u,&v,&w);28 Add_edge(u,v,w);29 // Add_edge(v,u,w);30 }31 sort(a+1,a+cnt+1,cmp);32 for(int i=1;i<=m;i++)33 if(a[i].u!=a[i-1].u)34 L[a[i].u]=R[a[i-1].u]=i;35 dfs(1);36 return 0;37 }
»summary
图的存储方式