邻接表

邻接表

一,对于邻接表的简单介绍:

       1,使用条件:

       当图的边数小于节点数的平方(把边数远小于节点数平方的图称为稀疏图,把边数远大于节点数平方的图称为稠密图)时,就使用邻接表的储存方法来代替临界矩阵储存法。能够使得时间复杂度优化。

        2,如何储存(代码实现):

        这个方法定义了3个数组暂定为u[6],v[6],w[6](三个数组大小根据具体情况来定,大小要比m大一),u用来储存起始节点,v就是到达节点,w用来储存两个节点之间的权值。

 1 //邻接表
 2 int n, m, i;
 3 int u[6], v[6], w[6];
 4 int first[5], next[6];
 5 scanf("%d %d", &n, &m);
 6 //初始化first下标为-1表示暂时没有边
 7 for (i = 1; i <= n; i++) {
 8     first[i] = 1;
 9 }
10 for (i = 1; i <= m; i++) {
11     scanf("%d %d %d", &u[i], &v[i], &w[i]);
12     //下面两句时关键
13     next[i] = first[u[i]];
14     first[u[i]] = i;
15 }

 

下面来解释一下:这里是用数组来储存而不是用指针链表但是能达到链表的效果(我讨厌指针),first储存的是这个起始节点第一条边的编号,next就是储存编号为i的下一条边的编号

 

邻接表邻接表邻接表

现在假设我要遍历一号顶点的所有边,剩下的边都可以在next数组中找到比如这图:

 

 

邻接表从first[1]出发,这个是编号为5的边,将1通向3号边,3号边再通向1号边(这里两个数组储存的是编号不是节点,我之前一直理解错)。然后这个边的编号和数组一起结合起来看,记住这里是边的编号的遍历,从5号边到3号边,再从3号边到1号边。后面这个代码就是实现上面这个图的。

 

 

1 k = first[1];
2 while (k != -1) {
3     printf("%d %d %d\n", u[k], v[k], w[k]);
4     k = next[k];
5 }

 

但是从上面这个图可以看出来,这个明显是倒着printf的也就是说先打印出来的是1  3  7而不是1  4   9.。这个是因为每个顶点插入的都是“这个链表”的头。

二,最后的代码实现:

 1 int n, m, i;
 2 int u[6], v[6], w[6];
 3 int first[5], next[6];
 4 scanf("%d %d", &n, &m);
 5 //初始化first下标为-1表示暂时没有边
 6 for (i = 1; i <= n; i++) {
 7     first[i] = 1;
 8 }
 9 for (i = 1; i <= m; i++) {
10     scanf("%d %d %d", &u[i], &v[i], &w[i]);
11     //下面两句时关键
12     next[i] = first[u[i]];
13     first[u[i]] = i;
14 }
15 for (i = 1; i <= n; i++) {
16     k = first[i];
17     while (k != -1) {
18         printf("%d %d %d\n", u[k], v[k], w[k]);
19         k = next[k];
20     }
21 }
//这个是包含了建立和遍历邻接表的两个过程

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

上一篇:学习记录11.23


下一篇:【Python数据分析-2】:Pandas常用操作-生成Series/DataFrame对象的方法