链式前向星

链式前向星

链式前向星对于图的存储十分方便，我们可以对一个节点进行访问，遍历所有与他相连的边，从而访问与它临近的所有节点，比如说在bfs版本的spfa实现最短路时，就有很好的应用。

与邻接矩阵、邻接表不同的是，存的是“边”

Code of 链式前向星存图与遍历

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100;

struct node
{
    int from, to, w, pre;///pre存：与该边同一起点的下一条边的位置（排号，cnt计）
}a[N];
int head[N];///head[i]存：以i为起点的最新边的位置（排号，cnt计）
int cnt = 1;

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    a[cnt].pre = head[from];
    head[from] = cnt;
    cout << "边的排号 :" << cnt << '\n';
    cout << "边的起点 :" << a[cnt].from << '\n';
    cout << "边的终点 ：" << a[cnt].to << '\n';
    cout << "边的权重 ：" << a[cnt].w << '\n';
    cout << "共起点前一条边排号 : " << a[cnt].pre << '\n';
    cout << "共起点最新边排号 ：" << head[from] << '\n';
    cnt++;
}

int main()
{
    int n;
    int b, c, d;///起点、终点、权重
    cin >> n;///存n条边
    memset(head, -1, sizeof(head));
    for(int i = 1; i <= n; ++i)
    {
        cin >> b >> c >> d;
        add(b, c, d);
    }
    for(int i = 1; i <= 4; ++i)///对“点”
        for(int k = head[i]; k != -1; k= a[k].pre)
            cout << i << "的相邻的点 ：" << a[k].to << '\n';
    return 0;
}