前置知识:

  1. 静态链表
  2. 邻接表(最好了解原理)

概述

与前向星不同,链式前向星无需排序操作,效率相对较高.

链式前向星实际就是静态建立的邻接表,或者说是用数组模拟(静态链表)实现的邻接表,因此代码实现非常简单.

链式前向星兼顾了前向星的简便和邻接表的高效,尽管应用不广泛,但是在OI竞赛中备受青睐.

原理

存储结构

需要2个数组,int head[];和struct Edge edge[];,分别存储表头和所有的边.

由于链式前向星本质是静态链表,因此需要一个edge[]数组来存储图中所有的边,根据输入顺序,edge[i]为输入的第i条边<ui,vi,wi>.

对每一条边而言,都存储4个数据u,v,w,next,分别为这条边的起点,终点,权值,下一条边的下标(edge中).其中下一条边的下标就类似于邻接表中的指向下一条边的指针,只不过这里使用静态链表实现.

然后,和邻接表一样,需要一个数组head[]作为表头,其中head[i]为一个下标,指向以i为起点的第1条出边.当没有这样的一条边时,即顶点i的出度为0,head[i]可以赋值为-1,代表没有下一条边了,类似NULL指针.

初始化

输入n,m为图的点数,边数.head[]长度为n,edge[]长度为m.根据实现可多出1个空间以忽略0下标.

head[]全部初始化为-1,代表当前所有的顶点都没有出边,即目前为空图.

插入边

采用头插法进行插入,每个head[i]就是一个(静态的)链表.

读入第i条边的信息<ui,vi,wi>,到edge[i].

根据ui找到head[ui],即以ui为起点的边集链表,将第一条边的下标head[ui]赋值给edge[i].next,即让第i条边的下一条边指向当前的edge[head[ui]]这条边.当指向的下标为-1时代表着到达链表尾部.

将i赋值给head[ui],即头插法,将新增的边i插入到链表头,即后输入的边在链表的头,先输入的边则在尾部,与输入相反.

依次插入m条边后,链式前向星即建立完成,就是这么简单.

代码示例

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
#include <iostream>

#define INF 0x7FFFFFFF
using namespace std;
struct EDGE {
	int to, w, next;
};
struct EDGE edge[500003];
int head[100003], n, m, cnt;
void addEdge() {
	int from;
    // 读入u,v,w
	cin >> from;
	cin >> edge[++cnt].to;
	cin >> edge[cnt].w;
	edge[cnt].next = head[from];
	head[from] = cnt;
}
void init() {
	cout<<"输入点数和边数:"<<endl;
	cin >> n >> m;//n为点数,m为边数
	cout<<"依次输入边(起始 终点 权值):"<<endl;
	for (int i = 1; i <= m; ++i)
		addEdge(); // 读入一条边
}
void print() {
	for (int i = 1; i <= n; ++i) {
		for (int j = head[i]; j; j = edge[j].next) {
			cout<<i<<"--("<<edge[j].w<<")-->"<<edge[j].to<<endl;
		}
	}
	return;
}
int main() {
	init();
	print();
	return 0;
}