邻接表

一，对于邻接表的简单介绍：

       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 }
//这个是包含了建立和遍历邻接表的两个过程