来自我的博客：拓扑排序 Topological Sort – Snow’s Blog (ivansnow02.github.io)
拓扑排序 Topological Sort
拓扑序列 Topological Order
拓扑序列是一个有向无环图（Directed Acyclic Graph，简称DAG）的所有顶点的线性序列。
设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若是图中的有向边或者从顶点到顶点有一条路径，则在序列中顶点必须排在顶点之前。
过程
- 从有向图中选择一个没有前驱（即入度为0）的顶点并且输出它。
- 从图中删去该顶点，并且删去从该顶点发出的全部有向边。
- 重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。
结果
- 图中全部顶点都被输出，即得到包含全部顶点的拓扑序列，称为成功的拓扑排序。
- 图中顶点未被全部输出，即只能得到部分顶点的拓扑序列，称为失败的拓扑排序，说明有向图中存在回路。
代码
基于BFS的拓扑排序
struct Edge {
int from, to, cost;
Edge(int u, int v, int w): from(u), to(v), cost(w) {}
};
vector<Edge> edges; // 存储所有边
vector<int> G[MAXN]; // G[i] 存储顶点i发出的所有边
int inDegree[MAXN]; // 存储每个顶点的入度
vector<int> result;
void TopologicalSort(int V) {
queue<int> q;
// 统计每个顶点的入度
for (int i = 0; i < edges.size(); ++i) {
int to = edges[i].to;
inDegree[to]++;
}
// 将入度为0的顶点入队
for (int i = 0; i < V; ++i) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
// 遍历顶点u发出的所有边
for (int i = 0; i < G[u].size(); ++i) {
Edge& e = edges[G[u][i]];
int v = e.to;
// 删除边(u, v)，更新顶点v的入度
if (--inDegree[v] == 0) {
q.push(v);
}
}
}
}
基于DFS的拓扑排序
void TopSort(vector<Edge>& edges, vector<vector<int>>& G) {
stack<int> st; // 定义一个栈
int ind[MAXV]; // 记录每个顶点的入度
memset(ind, 0, sizeof(ind));
for (const Edge& edge : edges) {
int to = edge.to;
ind[to]++; // 顶点to的入度增1
}
for (int i = 0; i < G.size(); i++) {
if (ind[i] == 0) {
st.push(i); // 将所有入度为0的顶点进栈
}
}
while (!st.empty()) {
int i = st.top();
st.pop(); // 出栈一个顶点i
printf("%d ", i); // 输出拓扑序列中的一个顶点i
for (int j : G[i]) { // 遍历顶点i的所有邻接点
int w = edges[j].to;
ind[w]--; // 顶点w的入度减1
if (ind[w] == 0) {
st.push(w); // 入度为0的邻接点w进栈
}
}
}
}
分析
使用邻接表进行拓扑排序的时间复杂度为。这是一种相对高效的算法，特别适用于稀疏图（边的数量较少）的拓扑排序问题。
AOE网
定义
若用一个带权有向图（DAG）描述工程的预计进度，以顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的时间（比如天数），或者说活动e持续时间AOE网。
通常AOE网中只有一个入度为0的顶点，称为源点，和一个出度为0的顶点，称为汇点。
在AOE网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。完成整个工程的最短时间就是网中关键路径的长度。
关键路径上的活动称为关键活动，或者说关键路径是由关键活动构成的。
事件的最早开始和最迟开始时间
- 事件v的最早开始时间：规定源点事件的最早开始时间为0。定义图中任一事件v的最早开始时间
ee(v)等于x、y、z到v所有路径长度的最大值
- 事件v的最迟开始时间：定义在不影响整个工程进度的前提下，事件v必须发生的时间称为v的最迟开始时间
le(v)应等于ee(y)与v到汇点的最长路径长度之差
活动的最早开始时间和最迟开始时间
- 活动a的最早开始时间
e(a)指该活动起点x事件的最早开始时间，即： - 活动a的最迟开始时间
l(a)指终点y事件的最迟开始时间与该活动所需时间之差，即：
关键活动
对于每个活动a，求出，若d(a)为0，则称活动a为关键活动。 对关键活动来说，不存在富余时间。
使用拓扑排序求关键路径
struct Edge {
int from, to, cost;
Edge(int u, int v, int w): from(u), to(v), cost(w) {}
};
vector<Edge> edges; // 存储所有边
vector<int> G[MAXN]; // G[i] 存储顶点i发出的所有边
int inDegree[MAXN]; // 存储每个顶点的入度
int earliest[MAXN]; // 存储每个顶点的最早开始时间
int latest[MAXN]; // 存储每个顶点的最晚开始时间
void addEdge(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
int m = edges.size();
G[u].push_back(m - 1);
inDegree[v]++;
}
void calcEarliestTime(int n) {
memset(earliest, 0, sizeof(earliest));
queue<int> q;
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
int v = e.to;
int w = e.cost;
earliest[v] = max(earliest[v], earliest[u] + w);
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
}
void calcLatestTime(int n) {
memset(latest, INF, sizeof(latest));
latest[n - 1] = earliest[n - 1];
queue<int> q;
q.push(n - 1);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < G[u].size(); i++) {
Edge& e = edges[G[u][i]];
int v = e.to;
int w = e.cost;
latest[u] = min(latest[u], latest[v] - w);
if (--inDegree[v] == 0) {
q.push(v);
}
}
}
}
void findCriticalPath(int n) {
for (int i = 0; i < edges.size(); i++) {
Edge& e = edges[i];
int u = e.from;
int v = e.to;
int w = e.cost;
int earliestU = earliest[u];
int latestV = latest[v] - w;
if (earliestU == latestV) {
cout << u << " -> " << v << " : " << w << "\n";
}
}
}
分析
因为使用了拓扑排序，时间复杂度为
© 版权声明
文章版权归作者所有，未经允许请勿转载，侵权请联系 admin@trc20.tw 删除。
THE END
