首页data structure

# 拓扑排序 Topological Sort

# 拓扑序列 Topological Order

拓扑序列是一个有向无环图（Directed Acyclic Graph，简称 DAG）的所有顶点的线性序列。

设 G=(V，E) 是一个具有 n 个顶点的有向图，V 中顶点序列v1、v2、…、vnv_1、v_2、…、v_n 称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若<vi，vj><v_i，v_j> 是图中的有向边或者从顶点viv_i 到顶点vjv_j 有一条路径，则在序列中顶点viv_i 必须排在顶点vjv_j 之前。

# 过程

  1. 从有向图中选择一个没有前驱（即入度为 0）的顶点并且输出它。
  2. 从图中删去该顶点，并且删去从该顶点发出的全部有向边。
  3. 重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。

# 结果

  • 图中全部顶点都被输出，即得到包含全部顶点的拓扑序列，称为成功的拓扑排序。
  • 图中顶点未被全部输出，即只能得到部分顶点的拓扑序列，称为失败的拓扑排序，说明有向图中存在回路。

# 代码

# 基于 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 进栈
            }
        }
    }
}
# 分析


使用邻接表进行拓扑排序的时间复杂度为O(V+E)O(V + E)。这是一种相对高效的算法，特别适用于稀疏图（边的数量较少）的拓扑排序问题。


# AOE 网


# 定义


若用一个带权有向图（DAG）描述工程的预计进度，以顶点表示事件，有向边表示活动，边 e 的权 c (e) 表示完成活动 e 所需的时间（比如天数），或者说活动 e 持续时间→\toAOE 网。


通常 AOE 网中只有一个入度为 0 的顶点，称为源点，和一个出度为 0 的顶点，称为汇点。


在 AOE 网中，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径。完成整个工程的最短时间就是网中关键路径的长度。


关键路径上的活动称为关键活动，或者说关键路径是由关键活动构成的。


# 事件的最早开始和最迟开始时间


    

  • 事件 v 的最早开始时间：规定源点事件的最早开始时间为 0。定义图中任一事件 v 的最早开始时间 ee(v)  等于 x、y、z 到 v 所有路径长度的最大值
    • 



ee(v)={0v为源点max{ee(x)+a, ee(y)+b, ee(z)+c}否则ee(v) = \begin{cases} 0 &v为源点 \\ max\{ee(x)+a,\ ee(y) + b,\ ee(z)+c\} &否则 \end{cases}



    

  • 事件 v 的最迟开始时间：定义在不影响整个工程进度的前提下，事件 v 必须发生的时间称为 v 的最迟开始时间 le(v)  应等于 ee(y)  与 v 到汇点的最长路径长度之差
    • 



le(v)={ee(v)v为汇点min{le(x)−a, le(y)−b, le(z)−c}否则le(v) = \begin{cases} ee(v) &v为汇点 \\ min\{le(x)-a,\ le(y) - b,\ le(z)-c\} &否则 \end{cases}



# 活动的最早开始时间和最迟开始时间


    

  • 活动 a 的最早开始时间 e(a)  指该活动起点 x 事件的最早开始时间，即： e(a)=ee(x)e(a)=ee(x)
    • 

  • 活动 a 的最迟开始时间 l(a)  指终点 y 事件的最迟开始时间与该活动所需时间之差，即：l(a)=le(y)−cl(a)=le(y)-c
    • 



# 关键活动


对于每个活动 a，求出d(a)=l(a)−e(a)d(a)=l(a)-e(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";
        }
    }
}
# 分析


因为使用了拓扑排序，时间复杂度为O(V+E)O(V+E)


此文章已被阅读次数:正在加载...更新于