结构体实现链式前向星

#include<bits/stdc++.h>
using namespace std;

const int N = 10010;
const int M = 2 * N;

int n,m;
struct edge //{终点,边权,下一条边}
{
    int v,w,ne;
}e[M]; //边集
int idx;
int h[N]; //存储u点的第一条出边的编号(头插法)

//插入一条由a到b的点
void add(int a,int b,int c)
{
    e[idx] = {b,c,h[a]};
    h[a] = idx++;
}

void dfs(int u,int father)
{
    for(int i = h[u]; i != -1; i = e[i].ne)
    {
        int v = e[i].v,w = e[i].w;
        if(v == father) continue;
        cout << u << " " << v << " " << w << endl;
        dfs(v,u);
    }
}

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i = 1; i <= m; i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0);
    return 0;
}

输入

6 5
4 3 90
1 4 30
5 6 60
1 5 20
5 2 70

输出

1 5 20
5 2 70
5 6 60
1 4 30
4 3 90

对edeg变化过程的分析

• add(4,3): e[0] = {3,h[4] = -1},h[4] = 0;
add(3,4): e[1] = {4,h[3] = -1},h[3] = 1;
add(1,4): e[2] = {4,h[1] = -1},h[1] = 2;
add(4,1): e[3] = {1,h[4] = 0}, h[4] = 3;
add(5,6): e[4] = {6,h[5] = -1},h[5] = 4;
add(6,5): e[5] = {5,h[6] = -1},h[6] = 5;
add(1,5): e[6] = {5,h[1] = 2} ,h[1] = 6;
add(5,1): e[7] = {1,h[5] = 4} ,h[5] = 7;

• 由于是用头插法,所以越后被插入的边越快遍历到,故将最后一个插入的边视为结点u的第一条出边,所以直接将h[u]赋值为idx

• 对于edge所存储的值的理解 :
  edge[i] = {第i条边的终点u,第i条边的权值w,第i条边的起点的另一条出边的编号}