前向星
前向星是以存储边的方式来存储图，先将边读入并存储在连续的数组中，然后按照边的起点进行排序，这样数组中起点相同的边就能够在数组中进行连续访问了。
其有点在于实现简单，易于理解。缺点是在读入边后需要对所有边进行一次排序，带来了时间开销，实用性也较差。因此只适合离线算法。
链式前向星（实质为数组模拟链表）
链式前向星和邻接表类似，也是链式结构的结合，每个节点i均有一个链表，此链表内的数据均为以节点i为起点的所有边的集合（对比邻接表存的是顶点的集合），边的表示为一个四元组(to,w,next)，其中to代表该条边的有向点对(w,v)，w代表边上的权值，next指向下一条边。
调用的时候只要通过head[i]就能访问到由节点i出发的第一条边的编号，通过编号到edge数组进行索引可以得到边的具体信息，然后根据这条边的next域可以得到第二条边的编号，以此类推，直到next域为INF（这里的INF即head数组初始化的值，一般取-1即可）
链式前向星基本原理
链式前向星是以边为主的存图方式，因此我们需要利用结构体来规划边，这会使图变得更加清晰。
结构
这里注意下面两个必要的数组：
Edge edge[edgenumber]; //结构体数组edge存边，edge[i]表示编号为i的边
int head[vexnumber]; //head[i]存以节点i为起点的第一条边（在edge中的编号）
这里实现的是
1
2
3
4
5
6
| struct Edge{
int next;
int to;
int w;
};
Edge edge[500010];
|
Edge结构体不用记录顶点u
如上所述，前向星存储的是每个顶点的邻接边。可以知道，在每个顶点后面连接一个链表，不过链表的节点表示的是邻接边而非邻接点。而用数组实现这个链表，就是前向星。
无论采用哪种结构存图，都应该是每读入一条边的信息，就更新一次图的结构。读入一条边u—>v，那么我们在存储图的时候，对于顶点u,该边就是u的一条邻接边，我们就把这条边“挂”在u后面即可。等读入所有的边，建图完成。
顶点u后“挂”的边就全是顶点u的邻接边，因此只需要记录这些邻接边的另一个顶点，而不需要存储顶点u。
由于边是按顺序一条一条读入，我们就很自然的想到对边进行编号，然后将这些边读入edge数组。对于Edge结构体中的next，其实就相当于链表中的next指针。不过此处的next是int型变量，存储的是下一条邻接边的编号。
head数组的用处
head数组相当于邻接链表中的表头数据，head[u]就表示顶点u的某一条邻接边（其编号）。根据这条边的next，就能找出顶点u所有的邻接边。
增边
若以点i为起点的边新增了一条，在edge中的下标为j。那么edge[j].next = head[i]，此后head[i] = j
即每次新加的边作为第一条边，最后倒序遍历
1
2
3
4
5
6
7
| void Add(int u, int v, int w) {
edge[++cnt].next = head[u];
edge[cnt].w = w;
edge[cnt].to = v;
head[u] = cnt;
}
|
遍历
遍历以st为起点的边
for(int i = head[st]; i != -1; i = edge[i].next)
i为开始的第一条边，每次指向下一条，以初始化的-1为结束标志
简单案例
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
42
43
44
45
| #include <iostream>
using namespace std;
#define MAXM 500000 + 10
#define MAXN 10000 + 10
struct Edge{
int next;
int to;
int w;
};
Edge edge[MAXM];
int n, m, cnt;
int head[MAXN];
void add(int u, int v, int w) {
edge[++cnt].next = head[u];
edge[cnt].w = w;
edge[cnt].to = v;
head[u] = cnt;
}
void print() {
int st;
cout << "Begin with[Please Input]: \n";
cin >> st;
for(int i = head[st]; i != 0; i = edge[i].next) {
cout << "Start: " << st << endl;
cout << "End: " << edge[i].to << endl;
cout << "W: " << edge[i].w << endl << endl;
}
}
int main() {
int s, t, w;
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> s >> t >> w;
add(s, t, w);
}
print();
return 0;
}
|
链式前向星实现SPFA
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define MAXM 50000 + 10
#define MAXN 10000 + 10
#define INF 0x3f3f3f3f3f
struct Edge {
int next;
int to;
int w;
};
Edge edge[MAXM];
int n, m, st, cnt;
int head[MAXN];
int d[MAXN];
bool inq[MAXN];
inline int Read() {
char c;
int ans = 0;
bool sign = false;
while (!isdigit(c = getchar()) && c != '-');
if (c == '-') {
sign = true;
c = getchar();
}
do {
ans = (ans << 3) + (ans << 1) + (c ^ '0');
} while (isdigit(c = getchar()));
return sign ? -ans : ans;
}
void add(int u, int v, int w) {
edge[++cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt;
}
void read() {
int x, y, w;
n = Read();
m = Read();
st = Read();
for (int i = 1; i < m; i++) {
x = Read();
y = Read();
w = Read();
add(x, y, w);
}
}
void SPFA(int x) {
d[x] = 0;
for (int i = 1; i < n; i++)
d[i] = INF;
queue<int> q;
q.push(x);
inq[x] = true;
while (!q.empty()) {
int k = q.front;
q.pop();
inq[k] = false;
for (int i = head[k]; i != 0; i = edge[i].next) {
int j = edge[i].to;
if (d[j] > d[k] + edge[i].w) {
d[j] = d[k] + edge[i].w;
if (!inq[j]) {
q.push(j);
inq[j] = true
}
}
}
}
for (int i = 1; i <= n; i++)
printf("%d ", d[i]);
printf("\n");
}
int main() {
read();
SPFA(st);
return 0;
}
|
关于SPFA算法的详解可见SPFA算法详解
