介于邻接矩阵与邻接表之间的存图方式————链式前向星

链式前向星

图的存储一般有三种:邻接矩阵、邻接表、前向星。

若图是稀疏图,边很少,开二维数组很浪费;

若点很多(如10000个点)a[10000][10000]又会爆.只能用前向星做.

前向星的效率不是很高,优化后为链式前向星,直接介绍链式前向星。

(一)链式前向星

1. 结构

这里用两个东西:

1 结构体数组edge存边,edge[i]表示第i条边,

2 head[i]存以i为起点的第一条边(在edge中的下标)

1
2
3
4
5
6
struct EDGE{
int next; //下一条边的存储下标(默认0)
int to; //这条边的终点
int w; //权值
};
EDGE edge[500010];

2.增边

若以点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) {  //起点u, 终点v, 权值w 
//cnt为边的计数,从1开始计
edge[++cnt].next = head[u];
edge[cnt].w = w;
edge[cnt].to = v;
head[u] = cnt; //第一条边为当前边
}

3. 遍历

遍历以st为起点的边

1
for(int i=head[st]; i!=0; i=edge[i].next)

i开始为第一条边,每次指向下一条(以0为结束标志) (若下标从0开始,next应初始化-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
#include <iostream>
using namespace std;
#define MAXM 500010
#define MAXN 10010
struct EDGE{
int next; //下一条边的存储下标
int to; //这条边的终点
int w; //权值
};
EDGE edge[MAXM];
int n, m, cnt;
int head[MAXN]; //head[i]表示以i为起点的第一条边
void Add(int u, int v, int w) { //起点u, 终点v, 权值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) {//i开始为第一条边,每次指向下一条(以0为结束标志)若下标从0开始,next应初始化-1
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
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define MAXM 500010
#define MAXN 10010
#define ANS_MAX 2147483647
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] = ANS_MAX;
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;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!