首页 > 代码库 > 图的存储方式

图的存储方式

图的存储方式

1.邻接矩阵

邻接矩阵的二维数组表示第i个点到第j个点的权值为dis[i][j]。

实现容易,但时空复杂度都比较大,时间复杂度为O(n*n),空间复杂度为O(n*n)。

适合稠密图。

下为代码:

技术分享矩阵
 1 #include<cstdio>
 2 #define N 4200
 3 int vis[N],dis[N][N],n,m,a,b,c;
 4 int dfs(int x){
 5     vis[x]=1;
 6     for(int i=1;i<=n;++i)
 7         if(dis[x][i]==1&&!vis[i])
 8             dfs(i);
 9 }
10 int main(){
11     scanf("%d%d",&n,&m);
12     for(int i=1;i<=m;++i){
13         scanf("%d%d%d",&a,&b,&c);
14         dis[a][b]=c;
15         dis[b][a]=c;
16     }
17     dfs(1);
18     return 0;
19 }

2.链表

链表通过三个数组实现。一个是next,表示指向的连接该边的另一条边的序号;一个是to,表示该边连接的点;一个是dis,表示权值。

时空复杂度较小,但实现困难,时间复杂度为O(m+n),空间复杂度为O(m+n)。

适合稀疏图。

附上两个代码,第一个为结构体模拟的链表,第二个为数组模拟的链表(其实都差不多)。

技术分享链表 结构体
 1 #include<cstdio>
 2 #define N 420000
 3 struct hehe{
 4     int next;
 5     int to;
 6     int dis;
 7 }edge[N];
 8 int n,m,a,b,c,num_edge,head[N],vis[N];
 9 int add_edge(int from,int to,int dis){
10     edge[++num_edge].next=head[from];
11     edge[num_edge].to=to;
12     edge[num_edge].dis=dis;
13     head[from]=num_edge;
14 }
15 int dfs(int x){
16     vis[x]=1;
17     for(int i=head[x];i;i=edge[i].next)
18         if(!vis[edge[i].to])
19             dfs(edge[i].to);
20 }
21 int main(){
22     scanf("%d%d",&n,&m);
23     for(int i=1;i<=m;i++){
24         scanf("%d%d",&a,&b,&c);
25         add_edge(a,b,c);
26         add_edge(b,a,c);
27     }
28     dfs(1);
29     return 0;
30 }

技术分享链表 数组
 1 #include<cstdio>
 2 #define N 420000
 3 int n,m,a,b,c,num,head[N],vis[N],next[N],to[N],dis[N];
 4 int add(int false_from,int false_to,int false_dis){
 5     next[++num]=head[false_from];
 6     to[num]=false_to;
 7     dis[num]=false_dis;
 8     head[false_from]=num;
 9 }
10 int dfs(int x){
11     vis[x]=1;
12     for(int i=head[x];i;i=next[i])
13         if(!vis[to[i]])
14             dfs(to[i]);
15 }
16 int main(){
17     scanf("%d%d",&n,&m);
18     for(int i=1;i<=m;i++){
19         scanf("%d%d",&a,&b,&c);
20         add(a,b,c);
21         add(b,a,c);
22     }
23     dfs(1);
24     return 0;
25 }

3.vector

用vector(动态数组)实现,其中pair的first存储的是点,second存储的是权值。

时间复杂度和空间复杂度都是O(m+n)。

代码:

技术分享vector

其实还有一个边集数组的算法,就是把边所连接的两个点和权值直接存储在结构体里,就不上代码了。

 

图的存储方式