细说链式前向星存图法
首先要明白,链式前向星的原理是利用存边来进行模拟图。
推荐左神的视频–建图、链式前向星、拓扑排序
比方说有这样一张图,我们用链式前向星来进行模拟时,可以将每一条边都进行编号,其中,红色的数字就是对每一条边的编号,蓝色的数字表示每一个结点编号。
准备三个数组
head[]
,next[]
,to[]
数组名称 下标含义 值的含义 head
结点值 结点指向的边 next
边的编号 该边指向下一条边 to
边的编号 边指向的结点值
idx
:表示当前还没有分配的边编号
添加边
所以添加边的函数add()
可以这样去设计:
//建立一个a->b的结点->结点,->表示边
inline void add(int a, int b) {
to[idx] = b, next[idx] = head[a], head[a] = idx++;
}
//新建一条边,编号为idx,指向结点b,然后在a结点的邻居边中增加idx边,思想类似与头插法,让这个新的边指向头边,并修改头边为新的边。
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10001; //最多生成N个结点,N-1个单边
int head[N], to[N], next[N], idx;
// head[]头边号
// 点号
// next[] 下一条边号
// 边号
// to[] 去往的点
// 边号
// idx
inline void add(int a, int b) {
to[idx] = b, next[idx] = head[a], head[a] = idx++;
}
inline void dfs(int u) {
cout << u << ' ';
int i = head[u]; //i为u结点第一条边
for (; i != -1; i = next[i]) {
//每次更新为下一条边
dfs(to[i]); //去到 i 边指向的结点
}
}
int main() {
memset(head, -1, sizeof head);//head[i]为-1表示这个结点没有后继边
add(1, 2);
add(1, 5);
add(1, 6);
add(2, 6);
add(5, 6);
dfs(1);
}