链式前向星

图有三种常见的存储方式。分别为：邻接矩阵、邻接表、链式前向星。

从逻辑上理解链式前向星可以认为是邻接表的一种变体，只不过这回存的不是节点，而是边的信息。

原理解释：

• 用一个结构体数组来存储边集，每条边有三个信息：
  1. 这条边的终点(e)
  2. 这条边的权值(v)
  3. 和这条边同起点的下一条边的编号(next)。 本质是用一个指针域模拟一个链表。
• 还需要一个head数组：用来保存某一个点为起点的所有边当中最后一条边的编号。

代码实现：

#include<iostream>
#include<cstring>
using namespace std;

struct edge {
    int e, v, next;
};

edge edg[1005];
int n, m, head[1005];

int main() {
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edg[i].e = b;
        edg[i].v = c;
        // 头插法
        edg[i].next = head[a];
        head[a] = i;
    }
    for (int i = 1; i <= n; i++) {
        cout << i << " : ";
        for (int j = head[i]; j != -1; j = edg[j].next) {
            cout << "{" << i << "-->" << edg[j].e << ", " << edg[j].v << "} ";
        }
        cout << endl;
    }
    return 0;
}

输入样例：

5 6
1 3 7
3 5 9
5 2 10
1 4 3
5 4 1
1 2 5

输出结果：

1 : {1-->2, 5} {1-->4, 3} {1-->3, 7} 
2 : 
3 : {3-->5, 9} 
4 : 
5 : {5-->4, 1} {5-->2, 10}