数组模拟邻接表的基础应用

内容总结自紫书(第二版)P360,Dijkstra算法的优化

巧妙的借助编号将邻接信息保存在first与next两个数组中，下面简单的介绍基本的应用方式：

测试数据讲解：

10 7//表示结点n个和以下m个路径
3 9 8//u,v,w分别表示路径起点、路径终点、路径长度
3 7 6
3 6 8
2 5 4
5 3 4
6 8 7
1 0 5

组织邻接表的代码：

 1 const int maxn = 300;
 2 int n,m;
 3 int first[maxn];
 4 int u[maxn],v[maxn],w[maxn],next[maxn];
 5 
 6 int main()
 7 {
 8     //freopen("input.txt","r",stdin);
 9     cin>>n>>m;
10     for(int i=0;i<n;i++)first[i]=-1;//表示不再有下一条边
11     for(int e=0;e<m;e++)
12     {
13         cin>>u[e]>>v[e]>>w[e];
14         ::next[e]=first[u[e]];
15         first[u[e]]=e;
16     }
17     return 0;
18 }

first[u]保存了结点u的“第一条边”的编号e。由于模拟链表采用的是向首部插入的方式，插入到模拟链表的最后一个与u结点相连的边的编号e就保存在first[u]里。

next[e]表示编号为e的“下一条边”的编号。由于某些原因，在每一次使用next数组时都需要声明，因为next可能因为内置关键字而重复。

first[i]与next[i]之间是没有关系的。

我们将上面的数据经过上述的程序读取并打印出来得到如下结果：

     e 0 1 2 3 4 5 6 7 8 9
first:-1 6 3 2-1 4 5-1-1-1
next: -1 0 1-1-1-1-1 0 0 0
   u[] 3 3 3 2 5 6 1 0 0 0
   v[] 9 7 6 5 3 8 0 0 0 0
   w[] 8 6 8 4 4 7 5 0 0 0

在读取上述列表时，应当使用如下的循环：

1 for(int c=first[3];c!=-1;c=::next[c])
2 {
3     printf("lenth->%d
",w[c]);//这样能够输出与结点3相连的每一条路径的长度
4 }

上述代码的意义是：对于结点u，从first数组中取出其第一条边的编号e1，则利用u,v,w数组就能够查询出该路径的相关信息；然后将通过next[e1]中得到下一条边的编号e2，直到next的最终值是结束标志值(这里是-1)，即可完成所有与结点u相连的路径的信息查询。