邻接表是图的一种链式存储方式。对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。又称链接表。
邻接表的表示方法：1）表节点结构邻接表中每个表结点均有两个域:（还可加上与弧或者叫边相关的信息如：权值）
① 邻接点域adjvex 存放与vi相邻接的顶点vj的序号j。 ② 链域next 将邻接表的所有表结点链在一起。
2）头结点结构：
顶点vi邻接表的头结点包含两个域： ① 顶点域vertex 存放顶点vi的信息（也可不加） ② 指针域firstedge vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。
用邻接表实现的Dijkstra算法（接上篇邻接表描述）：
#include <cstring>
#include <cstdio>
const int MAX = 0xfffffff;
const int N = 101;
struct edge {
int v1,v2, e, next;
} edge[10000];
int n, m, edge_num = 0, Head[N], dis[N];
bool mark[N];
void insert_edge(int v1, int v2, int w)
{
edge[edge_num].v1 = v1 - 1;
edge[edge_num].v2 = v2 - 1;
edge[edge_num].e = w;
edge[edge_num].next = Head[v1 - 1];
Head[v1 - 1] = edge_num++;
edge[edge_num].v1 = v2 - 1;
edge[edge_num].v2 = v1 - 1;
edge[edge_num].e = w;
edge[edge_num].next = Head[v2 - 1];
Head[v2 - 1] = edge_num++;//head[] 总是指向第一个弧，即最后添加进来的弧
return;
}
void get_map()
{
int s, e, w;
memset(Head, -1, sizeof(Head));
for(int i = 0; i < N; dis[i++] = MAX);
while(m--)
{
scanf("%d %d %d", &s,&e, &w);
insert_edge(s,e, w);
}
return;
}
void dijkstra(int src)
{
int i, j, k, minf;
memset(mark, 0, sizeof(mark));
mark[src] = true;
dis[src] = 0;
k = src;
for(j = 1; j < n; ++j)
{
for(i = Head[k]; i != -1; i = edge[i].next)
{
int u1 = edge[i].v2;
if(!mark[u1] && dis[k] + edge[i].e < dis[u1])
dis[u1] = dis[k] + edge[i].e ;
}
minf = MAX;
for(i = 0; i < n; ++i)
{
if(!mark[i] && dis[i] < minf)
{
k = i;
minf = dis[i];
}
}
mark[k] = true;
}
printf("%d\n",dis[n - 1]);
}
int main()
{
while(~scanf("%d %d", &n,&m), n||m) {
get_map();
dijkstra(0);
}
return 0;
}
邻接表存储图的实质，就是一个 Edge存储一条边。那一条边需要存什么信息呢？边的两点，与边权。
那，怎么把这些边关联在一起呢~
邻接表，实际上就是把“与同一顶点相连的边”关联在一起，通过一个链表进行关联。
也就是说，与同一个点相连的所有边，将会组织成一个链表。
所以，Edge就是链表的一员，需要一个next。而这个next，并不一定是指针，而可能是下一条边的Edge的下标。
现在轮到head了。要访问一个链表，肯定只能从链表头开始访问啦~那这个head数组，就分别记录每个点所形成的边的“链表”的头。说是链表头，实际上也只是和next一样，记录的是下标。
-1干嘛的？-1是作为链表尾的一个判定。每次访问链表的next，实际上就是下标的变换，那每一次的变换，判一下是不是-1，-1的话，就代表链表到尾了。。。