拓扑排序
节点的度
- 度：与节点相连的边的条数
- 入度：有向图中，指向当前节点的边的条数
- 出度：有向图中，从当前节点发出的边的条数
AOV网
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先级，这样的有向图为顶点表示活动的网，称为AOV(Activity
On Vertex Network)网
定义
将一个有向无环图G的所有顶点排成一个线性序列，使得有向无环图G的边集中的任意一条边<u,v>，始终满足u出现在v的前面
构造
- 在有向无环图中找到一个没有前驱（入度为0）的节点入栈
- 将栈顶节点出栈，然后从图中将此节点删除，并删除以该节点为尾的弧
- 重复操作
- 如果所有节点都已经输出，则结束，否则重复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
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1000;
const int mod = 1e9 + 7;
int g[N][N], indgr[N], res[N];
void topsort(int n){
int k =0;
for (int i =1;i<=n;i++){
for (int j = 1;j<=n;j++){
if(!indgr[j]){
res[i]=j;
indgr[j]--;
k=j;
break;
}
}
for (int j = 1;j<=n;j++){
if (g[k][j]==1){
g[k][j]=0;
indgr[j]--;
}
}
}
}
void solve() {
int n, m;
while(~scanf("%d %d", &n, &m)){
int x, y;
memset(indgr, 0, sizeof indgr);
memset(g, 0, sizeof g);
for (int i = 1;i<=m;i++){
scanf("%d %d",&x,&y);
if (!g[x][y]) {
g[x][y]=1;
indgr[y]++;
}
topsort(n);
for (int i = 1;i<=n;i++){
if (i<n) printf("%d ", res[i]);
else printf("%d\n", res[i]);
}
}
}
}
int main()
{
int tomorin=1;
while (tomorin--) solve();
return 0;
}
|
注意：
- 编号大的节点优先输出：寻找入度0的点时倒序遍历
- 如何判断有环：不存在入度为0的点
实现(邻接表)
对于稀疏图，使用邻接矩阵会浪费大量空间，我们可以使用邻接表
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
90
91
92
93
| #include <bits/stdc++.h>
using namespace std;
struct node{
int x;
int w;
node* next;
node(int x_, int w_){
this->x = x_;
this->w = w_;
next = nullptr;
}
};
vector<node*> head;
vector<int> in_degree;
void add_edge(int u, int v, int w){
node* a = head[u];
node* b = new node(v,w);
b->next = a->next;
a->next = b;
in_degree[v]++;
}
vector<int> topological_sort(int n) {
vector<int> result;
queue<int> q;
for(int i = 1; i <= n; i++) {
if(in_degree[i] == 0) {
q.push(i);
}
}
while(!q.empty()) {
int cur = q.front();
q.pop();
result.push_back(cur);
node* p = head[cur]->next;
while(p) {
in_degree[p->x]--;
if(in_degree[p->x] == 0) {
q.push(p->x);
}
p = p->next;
}
}
return result;
}
int main(){
int n, m;
cin >> n >> m;
head.resize(n+1);
in_degree.resize(n+1, 0);
for(int i = 0; i <= n; i++){
head[i] = new node(i,0);
}
for (int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
add_edge(u,v,w);
}
vector<int> topo = topological_sort(n);
if(topo.size() < n) {
cout << "图中存在环，无法进行拓扑排序" << endl;
} else {
for(int x : topo) {
cout << x << " ";
}
cout << endl;
}
return 0;
}
|
关键路径
AOE网
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动持续时间，这种有向图的边表示活动的网，称为AOE（Activity
On Edge Network）网
ETV与LTV
ETV：表示事件最早发生的时间(earliest time of vertex)
注意：考虑到多线程操作，事件最早发生时间应该是多个同步事件完成时间的最大值
LTV：表示事件最晚发生的时间(latest time of vertex)
注意：同理，事件最晚发生时间应该是减去多个同步事件完成时间后的最小值
