首页 > 代码库 > <图论入门>邻接矩阵+邻接表

<图论入门>邻接矩阵+邻接表

2024-09-20 14:25:32   217人阅读

非本人允许请勿转载。

趁热打铁，学会了邻接表把这个总结一下，以及感谢大佬uncle-lu！！！（奶一波）祝早日进队！

首先，图论入门就得是非常基础的东西，先考虑怎么把这个图读进去。

给定一个无向图，如下

技术分享

怎么把这个图的数据读入进去呢？

把这个图剖析开来看，1连着的是2和3，2连着4和5，3连着6和7，4连着5，5连着8和6，6连着9。

所以这个图可以用一种神奇的东西————邻接矩阵来存。如下，能联通的制为1，不能联通的制为0。

技术分享

那么可以看出来，这个邻接矩阵光读入的时间复杂度就是O(N2)的了，在有些情况下就会非常的浪费时间和空间，不利于这个身心健康发展啊。

所以就有了邻接表这个东西，邻接表邻接表，也就是边表，他存的是边而非其他gaygay的东西。这个邻接表是有两种存边的方法，一种是用链表来维护，把要存的边存在链表里，第二种是用数组模拟链表来维护，比链表要更加好理解一些？？？

技术分享

 

 纯手制链表，与该图相符，如果是带权值的可以再加一行。但是这里就看出来了这个链表的弊端，对于无向图也会出现一些奇奇怪怪的事情，像多次重复出现某个值。

那么这是链表版的邻接表，那么这个数组版的就如下。

技术分享

U数组就是起点，V就是终点，这个图是无向图，就人为省略了那些重复的东西。

所以邻接矩阵和邻接表的代码如下：

临接矩阵：

 1 #include<bits/stdc++.h>
 2 int edge[10010][10010];
 3 int main()
 4 {
 5      int n , m , x , y;
 6      scanf("%d%d",&m,&n);
 7      for(i=1;i<=n;++i)
 8        {
 9             for(j=1;j<=n;++j)
10              {
11                    cin >> x >> y ;
12                    edge[x][y]=w;
13              }
14         }
15 //  printf("linjiejuzhenduwanle happly"); 
16     return 0 ;
17 }

 临接表：

 1 #include<bits/stdc++.h>
 2 struct node
 3 {
 4     int v , next ;
 5 }edge[10010];
 6 int head[10010],cnt;
 7 void add_edge(int x , int y )
 8 {
 9     edge[++cnt].v  = x ;
10     edge[cnt].next = head[x];
11     head[x] = cnt ;
12     return ;    
13 }
14 int main()
15 {
16     int n , m;
17     scanf("%d%d",&n,&m);
18     int x , y ;
19     for(int i = 1 ; i < m ; i ++)
20         {
21             scanf("%d%d",&x,&y);
22             add_edge(x,y);    
23         }
24 //    printf("linjiebiaowanleduwanle happly");
25     return 0 ;
26  }

 那么就开始令（丧）人（心）愉（病）快（狂）的图论题吧，啊哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈。

//你哈个辣子啊你。

 

 

还有158天初赛， 还有186天复赛。

 

 

 

 

 

 

 

 

 

 

那是我愿意付诸一生的人，现在却没法拥有。

<图论入门>邻接矩阵+邻接表


联系
我们