数据：

输入:

第 1 行，两个整数 n,m，N 表示顶点个数，顶点编号为 1~n，m 表示边的个数。接下来 m 行表示每行有三个数，xyz 表示顶点 x 到顶点 y 的边的权值为 z。

按照读入的顺序为每一条边进行编号，1~m。比如第 1 条边 149 的编号就是 1， 137 这条边的编号是 5。

用 uvw 三个数组来记录每条边的具体信息。U[i]v[i] 和 w[i] 表示第 i 边是从第 u[i] 号顶点到 v[i] 号顶点，权值为 w[i]。

再用一个 first 数组来存储每个顶点其中(任意)一条边的编号。以便将来我们枚举每个顶点所有的边。比如 1 号顶点有一条边是 149，那么就将 first1 的值设为 1。如果某个顶点没有以该顶点为起始点的边，则将 first[i] 的值设为-1。

读入第 1 条边 149，将这条边的信息存储到 u[1],v[1],w[1] 中。同时为这条边赋予一个编号，因为这条边是最先读入的，存储在 u,v 和 w 数组下标为 1 的单元格中，因此编号就是 1。这条边的起始点是 1 号顶点，因此将 first[1] 的值设为 1。

这条编号为 1 的边是以 1 号顶点为起始点的第 1 条边，所以要将 next[1] 的值设为-1。也就是说如果当前这条编号为 i 的边，是我们发现的以 u[i] 为起点的第 1 条边就将 next [i] 的值设为-1。

读入第 2 条边 438，将这条边的信息存储到 u[2],v[2] 和 w[2]中，这条边的编号为 2，这条边的起始顶点是 4 号顶点，因此将 first[4] 的值设为 2，另外这条编号为 2 的边是我们发现以 4 号起点为起始点的第 1 条边，所以将 next[2] 的值设为-1。

读入第 3 条边 125，将这条边的信息存储到 u[3]v[3] 和 w[3]中，这条边的编号为 3，起始顶点是 1 号顶点，我们发现 1 号顶点已经有一条编号为一的边了，如果此时将 first[1] 的值设为 3 那编号唯一的边岂不是丢失了，此时只需将 next[3] 的值设为 1。

Next 数组存储的是编号为 i 的边的前一条边的编号\

读入第 4 条边 246，将这条边的信息存储到 u[4]v[4] 和 w[4]中，这条边的编号为 4，起始顶点是 2 号顶点，因此将 first[2] 的值设为 4，另外这条编号为 4 的边是我们发现以 2 号顶点为起始点的第 1 条边，所以将 next[4] 的值设为-1。

读入第 5 条边 137，将这条边的信息存储到 u[5]v[5] 和 w[5]中，这条边的编号为 5，起始顶点又是 1 号顶点，此时需要将 first[1] 的值设为 5，并将 next[5] 的值改为 3。

1 号顶点的其中一条边的编号存储在 first 一中，其余的边可以通过 next 数组找到。

此时遍历某个顶点边的时候的遍历顺序，正好与读入时候的顺序相反。因为在为每个顶点插入边的时候，都是直接插入链表的手部，而不是尾部。\

创建连接表的代码：

int n,m,i;
//u、v和w的数组大小要根据实际情况来设置，要比m的最大值要大1
int u[6],v[6],w[6];
//first和next的数组大小要根据实际情况来设置，要比n的最大值要大1
int first[5],next[5];
scanf("%d %d",&n,&m);
//初始化first数组下标1~n的值为-1，表示1~n顶点暂时都没有边
for(i=1;i<=n;i++)
    first[i]=-1;
for(i=1;i<=m;i++)
{
    scanf("%d %d %d",&u[i],&v[i],&w[i]);//读入每一条边
    //下面两句是关键啦
    next[i]=first[u[i]];
    first[u[i]]=i;
}

遍历 1 号顶点所有边的代码:

k=first[1];// 1号顶点其中的一条边的编号（其实也是最后读入的边）
while(k!=-1) //其余的边都可以在next数组中依次找到
{
    printf("%d %d %d\n",u[k],v[k],w[k]);
    k=next[k];
}

遍历每个顶点的所有边的代码:

for(i=1;i<=n;i++)
{
    k=first[i];
    while(k!=-1)
    {
        printf("%d %d %d\n",u[k],v[k],w[k]);
        k=next[k];
    }
}

参考原文[http://developer.51cto.com/art/201404/435072.htm]

汇源果汁吖！

数组实现邻接表

数据：