链式前向星

本质：模拟链表的操作，链式存储图。

head[x]相当于一维代表了出发点，之后T[i].next一条链相当于二维代表了所有（与它）连接的点。（不连接的到-1就停止了）。

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void add(int u,int v,int w)
{
 edge[cnt].to = v; //终点
    edge[cnt].w = w; //权值
    edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号
    head[u] = cnt++;//更新以u为起点上一条边的编号
}
int main()
{
     memset(head,-1,sizeof(head));
     for(int i=1;i<=m;i++)
    {
    	cin>>ai>>bi>>ci;
         //起点，终点，还有权值
        add(ai,bi,ci);
        add(bi,ai,ci);
    }
}
//主要是这四步

如果是遍历

1
2
for(int i=head[u];i!=-1;i=e[i].next)
     //以他为起始，并不断找下一个

5 7 1 2 1 2 3 2 3 4 3 1 3 4 4 1 5 1 5 6 4 5 7

假设有这些边 1 5 6 1 3 4 1 2 1

2 3 2

3 4 3

4 5 7 4 1 5

对于1 2 1这条边：edge[0].to = 2; edge[0].next = -1; head[1] = 0;

对于2 3 2这条边：edge[1].to = 3; edge[1].next = -1; head[2] = 1;

对于3 4 3这条边：edge[2].to = 4; edge[2],next = -1; head[3] = 2;

对于1 3 4这条边：edge[3].to = 3; edge[3].next = 0; head[1] = 3;

对于4 1 5这条边：edge[4].to = 1; edge[4].next = -1; head[4] = 4;

对于1 5 6这条边：edge[5].to = 5; edge[5].next = 3; head[1] = 5;

对于4 5 7这条边：edge[6].to = 5; edge[6].next = 4; head[4] = 6;

最终我们从4节点开始遍历的话，会先是4 5 7，然后是4 1 5，然后结束

如果我们从节点1开始遍历，会先是 1 5 6，然后是 1 3 4，然后是1 2 1

这样在遍历时是倒着遍历的,也就是说与输入顺序是相反的,不过这样不影响结果的正确性.

大致是这样，想必看着样例也大概理解了