链式向前星，是图的一种存储结构，采用数组模拟链表实现前向星的功能，简单来讲，它按照边来存图，而邻接矩阵是按照点来存图。

可以结合图的邻接表存储（链表实现）图的存储和数组实现链表数组实现链表的知识，自己实现链式向前星。

链式向前星

无边权图

存储结构

1
const int N = 1000, M = N * 2;
1
int h[N], e[M], ne[M], idx;

h[i] 表示第 i 个结点的头节点

e[i] 表示第 i 个节点在图中对应的编号

ne[i] 表示第 i 个节点的下一个节点所在的下标，也就是边

idx 表示下一个新添节点的下标

注意头节点需要N个的话，那么，最多需要 N*(N-1) 个ne节点和e节点（完全图的性质）。但是一般都没有那么满，满图用邻接矩阵来存，所以一般M = N * 2就够了。

初始化

1
2
3
4
void init() {
    idx = 0;
    memset(h, -1, sizeof(h));
}

在一般适合，直接全局写就行了，不用写成函数再调用。

加边操作

1
2
3
4
void add(int a, int b) { // 添加边 ： a -> b 
	// 就是对 h[a] 的链表添加一个节点，新节点值为 b 
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

链表头插法添加节点：

1
2
3
4
5
void add(int x) {
	e[idx] = x;
	ne[idx] = head;
	head = idx++;
}

==注意调用一次是有向图，可以调用两次变成双向图或无向图==

即： 

1
2
add(a, b);
add(b, a);

遍历操作

普通遍历

1
2
3
4
5
6
7
8
9
10
11
// 遍历
void disp() {
	for (int i = 0; i < N; ++i) {
		if (h[i] != -1){
			cout <<  i << "：";
			for(int j = h[i]; j != -1; j = ne[j])	//遍历顶点指向的边 
				cout << e[j] << " idx(" << j << ") -> ";
			cout << endl;
		}
	}
}

dfs遍历

+ dfs遍历

bfs遍历

+ bfs遍历

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>

using namespace std;

const int N = 1000, M = N * 2;

int h[N], e[M], ne[M], idx;

void init() {
	idx = 0;
	memset(h, -1, sizeof(h));
}

void add(int a, int b) { // 添加边 ： a -> b 
	// 就是对 h[a] 的链表添加一个节点，新节点值为 b 
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// 遍历
void disp() {
	for (int i = 0; i < N; ++i) {
		if (h[i] != -1){
			cout <<  i << "：";
			for(int j = h[i]; j != -1; j = ne[j])	//遍历顶点指向的边 
				cout << e[j] << " idx(" << j << ") -> ";
			cout << endl;
		}
	}
}

int main () {
	init();
	add(1,2);
	add(3,4);
	add(2,3);
	add(2,1);
	add(4,5);
	add(5,1);
	add(5,2);
	disp(); 
}

有边权图

存储结构

1
const int N = 1000, M = N * 2;
1
int h[N], e[M], w[M], ne[M], idx;

h[i] 表示第 i 个结点的头节点

e[i] 表示第 i 个节点在图中对应的编号

w[i] 表示第 i 条边的边权

ne[i] 表示第 i 个节点的下一个节点所在的下标，也就是边

idx 表示下一个新添节点的下标

初始化

1
2
3
4
void init() {
    memset(h, -1, sizeof(h));
    idx = 0;
}

加边操作

1
2
3
4
// 添加边， a->b ， 边权为 c
void add(int a, int b, int c) {
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

遍历操作

有边权图的遍历其实就只是比无边权的多输出w[j]的值而已。

普通遍历

1
2
3
4
5
6
7
8
9
10
11
12
// 普通遍历 
void disp() {
	for (int i = 0; i < N; ++i) {
		if (h[i] != -1) {
			cout << i << ": ";
			for (int j = h[i]; j != -1; j = ne[j]) {
				cout << e[j] << " " << w[j] << "(" << j << ") -> "; 
			}
			cout << endl;
		}
	}
}

dfs遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
bool st[N];

// dfs遍历 
void dfs(int i) {
	st[i] = true;
	cout << i;
	for (int j = h[i]; j != -1; j = ne[j]) {
		if (!st[e[j]]) {
			cout << " -(" << i << ")" << w[j] << "> ";
			dfs(e[j]);
		}
	}
}

bfs遍历

bfs遍历带权图很麻烦，带权图还是用dfs遍历算了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void bfs(int i) {
	qu[++rear] = i;
	st[i] = true;
	n[i] = 0;
	int father = i;
	while (front != rear) {
		int t = qu[++front];
		if (n[father] == 0) {
			father = t;	
		}
		for (int j = h[t]; j != -1; j = ne[j]) {
			if (!st[e[j]]) {
				qu[++rear] = e[j];
				quw[++rearw] = w[j];
				st[e[j]] = true;
				n[t]++;
			}
		}
		if (frontw == rearw) {
			cout << t;
			break;
		}
		cout << t << " -(" << father << ")" << quw[++frontw] << "> ";
		n[father]--;
	}
}