数据结构-图的创建与遍历

# 有向图的拓扑排序

图的创建与遍历

给定节点数和边数,以及构成每条边的两个节点。

构造图

image-20240603193735331

要存储上面的图,需要h[N], e[N], ne[N]来表示

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

using namespace std;

const int N = 100010;
int h[N];//存放节点a第一个邻接节点的索引idx
int e[N];//存放索引为idx的边的指向的节点值a
int ne[N];//存放索引idx的与其共享同一个起始点的边的索引idx
int idx;

void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;

}

int main(){
memset(h, -1, sizeof(h));
int n,m;
cin>>n>>m;
int a,b;
for(int i=0; i<m; i++){
cin>>a>>b;
add(a,b);
}

for(int i=1; i<=n; i++){
//对点i求其所连接的边
cout<<"以节点"<<i<<"为起始点,与其相邻的边有:";
for(int j = h[i]; j!=-1; j = ne[j]){
int eb = e[j];
cout<<eb<<" ";

}
cout<<endl;

}


}

image-20240603193821500

拓扑排序

拓扑排序

若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (𝑥,𝑦),𝑥 在 𝐴 中都出现在 𝑦 之前,则称 𝐴 是该图的一个拓扑序列。

如:下面的图,能找到序列:1 —— 2 —— 4 —— 3 ——5构成一条拓扑序列

image-20240603194203015

判断方法

  1. 删除一个入度为0的节点,加入结果集合
  2. 将上述节点对应的有向边都删除,重复第一步
  3. 直到最后没有节点,则该图可找出拓扑序列

代码实现重点

  1. 现把入度为0的节点加到集合的,后面删除该节点对应的边时要先删除:可以使用队列存储
  2. 删除节点a对应的有向边:可以遍历a为起始的连接边,将这些对应的点的入度-1即可
  3. 直到最后没有节点:队列为空时,结果集为整个图的节点个数

实现

用一个d[N]数组来存储每个点的入度数

队列q存储所有入度为0的节点

数组v存储答案

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
# include <iostream>
# include <queue>
# include <vector>
# include<cstring>
# include <algorithm>


using namespace std;

const int N = 100010;
queue<int> q;
vector<int> v;

int e[N], ne[N],h[N];
int d[N];//计算每个点的入度数
int idx;
int n,m;
int sum;


void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}

void topsort(){
//找度为0的点
for(int i =1; i<=n; i++){
if(d[i]==0){
q.push(i);
}
}

while(!q.empty()){
int u = q.front();
v.push_back(u);
sum++;
q.pop();
for(int j = h[u]; j!=-1; j=ne[j]){
int c = e[j];
d[c]--;
if(d[c]==0){
q.push(c);
}
}
}

if(sum == n){
for(auto i : v){
cout<<i<<" ";
}
}
else{
cout<<-1;
}



}

int main(){
memset(h, -1, sizeof(h));
cin>>n>>m;
int a,b;
for(int i =0 ;i<m ;i++){
cin>>a>>b;
add(a,b);
d[b]++;
}
topsort();

}

数据结构-图的创建与遍历
https://wendyflv.github.io/2024/06/03/数据结构-图的创建与遍历/
作者
Wendyflv
发布于
2024年6月3日
许可协议