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

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

非本人允许请勿转载。

趁热打铁,学会了邻接表把这个总结一下,以及感谢大佬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天复赛。

 

 

 

 

 

 

 

 

 

 

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

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