链式前向星存图.MD

日期 2022 / 03 / 23

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。 前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界 上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优 秀的数据结构。

链式前向星其实就是静态建立的邻接表，时间效率为O(m)，空间效率也为O(m)。遍历效率也为O(m)。

Next，表示与这个边起点相同的上一条边的编号。

head[i]数组，表示以 i 为起点的最后一条边的编号。

#include <bits/stdc++.h>

#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 0, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e6 + 10;
using namespace std;
int cnt;
int head[maxn];

struct Edge {
  int to, w, next; // 终点,边权，同起点的上一条边的编号
} edge[maxn]; //边集

void Add_Edge(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(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i <= n; i++) {
    head[i] = -1; // 初始化	
  }
  for (int i = 1; i <= m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    Add_Edge(x, y, z);	
  }
  for (int i = 1; i <= n; i++) {
    cout << i << endl;
    for (int j = head[i]; j != -1; j = edge[j].next) {
      cout << i << ' ' << edge[j].to << ' ' << edge[j].w << endl;
    }
    cout << endl;	
  }
  return 0;
}


/*
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
*/