複旦大學961-資料結構-第五章-圖（五）拓撲排序

961全部内容連結

文章目錄

• 拓撲排序
• AOV網
• AOE網
• • 基本概念
  • 求關鍵路徑的代碼實作

拓撲排序

拓撲排序：在一個有向無環圖中，把節點排成一個序列，當且僅當滿足以下兩個特性時，稱該序列為該圖的一個拓撲排序：

• 每個頂點在序列中隻出現一次
• 若頂點A在序列中排在頂點B的前面，則在圖中不存在從頂點B到頂點A的路徑

拓撲排序的實際應用：

比如該圖是一個有向無環圖。每個節點代表着一種活動。但是每個活動都需要一個前置的觸發條件，比如，如果你不買菜，就沒有雞蛋，就沒法打雞蛋。是以打雞蛋的前置條件是買菜。其他的也同理。 但是在這個是以，這些所有活動應該按照什麼樣的順序來進行，最後排一下序，這個排序後的序列就是這個有向無環圖的拓撲排序。比如，對于該圖，它的拓撲排序不止一個，可以舉例如下兩個：

1. 準備廚具 -> 買菜 -> 打雞蛋 -> 洗番茄 -> 切番茄 -> 下鍋炒 -> 吃
2. 買菜 -> 洗番茄 -> 準備廚具 -> 切番茄 -> 打雞蛋 -> 下鍋炒 -> 吃

除了上述兩種情況，還有很多種情況存在，是以拓撲排序是不唯一的。

AOV網

AOV網（Activity On Vertex Network）是用頂點表示活動的網絡。主要用于描述各個活動的優先級。是以它的邊沒有權值。如定義中舉的例子，我們并不關心哪一項活動到底花費多長時間，我們隻關心哪一步先做，哪一步後做。

拓撲排序的算法相對簡單，主要思路為：

1. 從有向無環圖中找到一個入度為0的點，并輸出
2. 從圖中删除該頂點的所有以它為起點的有向邊（此時也不會有以它為終點的有向邊，因為它的入度為0）。
3. 重複1,2，直到圖中不再有頂點。

算法僞代碼：

1. 申請一個棧（隊列也行，其他集合也可），用于存儲目前入度為0的點
2. 初始化棧，将目前入度為0的點入棧。

3. 開始while，如果棧不可為空，則

   3.1 出棧，然後輸出頂點

   3.2 将該頂點的鄰接節點的入度-1，如果-1後入度為0，則入棧

4. 當棧空時，周遊結束。

Java代碼如下：

// AOV網拓撲排序
    public static List topologicalSort(DirectedGraph graph) {
        List sortResult = new ArrayList();
        Map<Object, Integer> vertexInDegree = new HashMap<>();  // 存儲每個節點的入度
        Stack stack = new Stack(); // 存儲入度為0的節點

        for (Object vertex : graph.getVertexes()) {  // 周遊所有節點，初始化所有的入度
            int inDegree = graph.getInDegree(vertex);
            vertexInDegree.put(vertex, inDegree);  // 将節點的度存儲到map中
            if (inDegree == 0) stack.push(vertex); // 如果節點的入度為0，則入棧
        } // 初始化完成

        while (!stack.isEmpty()) { // 如果棧中還有入度為0的點，則繼續，當棧中沒有入度為0的點，說明拓撲排序已經完成
            Object vertex = stack.pop();
            sortResult.add(vertex);

            for (Object neighbor : graph.neighbors(vertex)) { // 周遊目前節點的所有鄰接節點（後繼節點）
                // 将該節點的所有後繼節點的入度減1，相當于删除了該節點以及該節點的邊。
                vertexInDegree.put(neighbor, vertexInDegree.get(neighbor) - 1);
                // 若該節點的後繼節點入度減1後為0，則将其入棧
                if (vertexInDegree.get(neighbor) == 0) stack.push(neighbor);
            }
        }
        return sortResult;
    }
           

這裡使用到了一個之前沒有用過的有向圖接口和鄰接矩陣有向圖的實作，代碼如下：

public interface DirectedGraph<VertexType> extends Graph<VertexType> {

    int getInDegree(VertexType vertex);  // 擷取節點入度

    int getOutDegree(VertexType vertex);  // 擷取節點出度

}
           

這個有向圖接口繼承自普通圖，多了兩個接口

// 鄰接矩陣實作有向圖
public class AdjacencyMatrixDirectedGraph<VertexType> extends AdjacencyMatrixUndirectedGraph<VertexType>
        implements DirectedGraph<VertexType> {

    public AdjacencyMatrixDirectedGraph(int maxVertexNum) {
        super(maxVertexNum);
    }

    @Override
    public void addEdge(VertexType x, VertexType y) {
        int xIndex = findIndex(x);
        int yIndex = findIndex(y);
        edges[xIndex][yIndex] = 1;  // 因為是有向圖，是以隻給<x,y>邊指派
    }


    @Override
    public int getInDegree(VertexType vertex) {
        int inDegree = 0;
        int xIndex = findIndex(vertex);
        for (int i = 0; i < edges.length; i++) {
            if (edges[i][xIndex] > 0) inDegree++;
        }
        return inDegree;
    }

    @Override
    public int getOutDegree(VertexType vertex) {
        int outDegree = 0;
        int[] edge = edges[findIndex(vertex)];
        for (int i : edge) {
            if (i > 0) outDegree++;
        }
        return outDegree;
    }
}
           

這個是鄰接矩陣有向圖的實作

AOE網

基本概念

AOE（Activity On Edge Network）網和AOV網很像，從名字中基本可以看出，AOV的V是vertex，是以AOV網是頂點代表活動。而AOE網的E是Edge，也就是邊代表活動。是以，用邊表示活動的網，簡稱AOE網。而AOE網中的頂點代表着事件。

比如如圖一張AOE網，事件就是頂點，比如V1(開始事件)，V2（可以切了事件），V3（可以抄了事件）。而邊代表活動，比如a1(打雞蛋活動)等等。

如圖所示，可以看出事件隻代表一種狀态，不消耗時間。而活動是需要消耗一定時間的，而這個時間一般用權值代表。

AOE網具有如下性質：

• 隻有在某頂點的所代表的的時間發生後，從該頂點出發的各個有向邊所代表的的活動才能開始。意思是，當你處于“可以炒了（V3）”這個事件後，你才可以進行下一項“炒菜（a4）”這個活動
• 隻有在進入某頂點的各個有向邊所得代表的活動都已經結束時，該頂點所代表的的事件才能發生。意思就是，你隻有打完雞蛋（a1）且切完番茄（a3），才可以開始炒了（V3）
• AOE網必須要有一個開始節點和一個結束節點。即一個入度為0的節點和一個出度為0的節點。

關鍵路徑的概念：

從源點到彙點的所有路徑中，具有最大路徑長度的路徑稱為關鍵路徑。而把關鍵路徑上的活動稱為關鍵活動。注意，多條路徑是可以并行執行的，比如打雞蛋可以和洗番茄并行執行。

解釋：彙點就是除開始之外的其他頂點。簡單點說關鍵路徑就是影響整個工期的路徑。比如在上圖中炒菜（a4）就是一個關鍵活動，因為在整個工期中，它快整個就快，它慢，整個就慢。而切番茄（a3）也是一個關鍵活動。因為切番茄的快慢也是可以直接影響整個進度的，因為打蛋隻需要兩分鐘，是以并不會影響整體進度。

下面這幾個概念很重要，這幾個概念涉及到算法實作，估計也會是出題重點。

1. 事件Vk的最早發生時間ve(k)

事件最早發生時間就是字面意思。比如：“開始（V1）”的最早發生時間是0。“可以切了（V2）”的最早發生時間是1（因為他前面需要花一分鐘的時間切番茄）。“可以炒了（V3）”的最早發生時間是4（因為他前面要經曆a2和a3，而打雞蛋的時間小于它們倆之和，是以不影響）。結束的最早發生時間是6。

2.事件Vk最遲發生時間vl(k)

最遲發生時間是指在不推遲整個工程完成的前提下，即保證它的後繼事件Vj在其最遲發生時間vl(j)能夠發生時，該事件最遲必須發生的時間。

上面這個圖不太能展現這個例子，我對其進行加工一下，如圖

假設對上述圖進行改造，在打雞蛋之前又加了拿雞蛋，增加了事件1.5。切番茄的時間也相應增加一些。此時關鍵路徑沒有變，還是a1,a3,a4。

對上述例子中，V1.5事件的最晚發生時間為4。因為在第6分鐘的時候，洗番茄和切番茄已經幹完了，雖然打雞蛋這件事不是關鍵路徑，但是你不能影響别人的進度，是以你在第4分鐘的時候，就必須開始打雞蛋，要不然你就來不及了。

3.活動ai的最早開始時間e(i)

了解了上面兩個時間，那麼這個也就不難了解了。字面意思。還用上面的老圖。

“洗番茄（a2）”的最早發生時間是0，“打雞蛋（a1）”的最早發生時間也是0。“炒菜(a4)”的最早發生時間是4。也就是說，活動的最早發生時間等于該邊對應起點的最早發生時間。即 e(i)=ve(k)。

4.活動ai的最遲開始時間l(i)

這個概念與時間的最遲發生時間差不多。比如，“打雞蛋(a1)”這個活動的最晚發生時間為2。因為打雞蛋需要2分鐘，而洗番茄+切番茄需要4分鐘。如果在2分鐘的時候還不開始打雞蛋，就會耽誤整體進度。注意區分事件最遲發生時間和活動最遲發生時間的差別。事件是頂點，活動是邊

5.時間餘量

一個活動的“最遲開始時間 - 最早開始時間”就是時間餘量。簡單點說，就是這個活動可以拖多長時間再開始。比如上圖中，打雞蛋這個活動可以在開始之後拖兩分鐘再去做，它的活動餘量就是2。你決定考研到來不及必須學政治的時候，相差了100天，那學政治這個活動的時間餘量就是100天。

求關鍵路徑的代碼實作

核心思想：那些時間餘量為0的活動，就是關鍵活動，他們構成的路徑就是關鍵路徑。簡單點說就是那些不能夠推遲的活動組成的路徑就是關鍵路徑。

算法步驟：

1. 根據拓撲排序的順序，依次求出各個頂點的最早開始時間
2. 根據逆拓撲排序（可以了解為将拓撲排序逆序）依次求出各個頂點的最遲開始時間
3. 如果兩個頂點是鄰居，且他們的最早開始時間和最晚開始時間相等，則他們之間的活動（路徑）就是關鍵活動。

算法步驟解釋：

• 關于第一步，因為是按照拓撲排序，是以當你求第n個頂點的最早發生時間時，那麼前驅節點一定已經求過了，是以隻需要用它前驅節點的最早發生時間加上這兩個節點之間的活動消耗時間即可。如果一個節點有多個前驅節點，那麼它的最早發生時間取合最大的那個。
• 關于第二步，因為是求最遲發生時間，是以要考慮該事件（頂點）的後繼節點的最晚發生時間。即一個事件的最晚發生時間是它後繼事件的最晚發生時間減去他們之間活動的所消耗的時間。比如 <u,v>=3，如果v的最晚發生時間是5，那麼u的最晚發生時間是5-3=2。之是以采用逆拓撲排序，是為了從後往前求，這樣當你求一個節點時，它的後繼節點的最晚發生時間一定已經求過了。如果一個節點有多個後繼節點，那麼可以求出來多個最晚發生時間，去最小的那個。

關于王道書上的步驟的個人了解：王道書上是五步，王道書在求完節點後，又求了每條邊（活動）的最早發生時間和最遲發生時間，然後使用的是邊的兩個時間之差判斷是否為0。它這樣的好處個人認為有兩個：1. 可以直接求出關鍵活動，而不用根據兩個節點夾出關鍵活動。 2. 可以适用于複雜圖，如圖所示

比如對于該圖，很明顯，該圖是一個複雜圖，假設用兩個節點之間有多條活動，那麼用第一種方法就會認為a1和a2都是關鍵路徑，但實際上隻有a2是關鍵路徑。

Java代碼如下：

// 求關鍵路徑
    public static List<WeightedGraph.Edge> criticalPath(DirectedWeightedGraph graph) {
        List topoVertexes = topologicalSort(graph); // 求出節點的拓撲排序
        List reverseTopoVertexes = new ArrayList(); // 求出逆拓撲排序
        for (int i = topoVertexes.size() - 1; i >= 0; i--) {
            reverseTopoVertexes.add(topoVertexes.get(i));
        }

        Map<Object, Integer> ve = new HashMap<>(); // 存儲節點的最早發生時間
        Map<Object, Integer> vl = new HashMap<>(); // 存儲節點的最遲發生時間

        for (Object vertex : topoVertexes) { // 根據拓撲排序順序，求出各個節點的最早發生時間
            List predecessors = graph.predecessors(vertex); // 擷取該節點的所有前驅節點
            int maxWeight = 0;  // vertex節點中，“前驅頂點最早發生時間+<vertex,predecessor>邊活動的消耗時間”的最大值
            for (Object predecessor : predecessors) {
                // weight = 前驅頂點最早發生時間+<vertex,predecessor>邊活動的消耗時間
                int weight = ve.get(predecessor) + graph.getEdgeWeight(predecessor, vertex);
                if (weight > maxWeight) maxWeight = weight;  // 從它所有的前驅節點中找出消耗時間最長的那個作為最早發生時間
            }
            ve.put(vertex, maxWeight);
        }


        vl.put(reverseTopoVertexes.get(0), ve.get(reverseTopoVertexes.get(0)));  // 初始化結束頂點的最晚開始時間(等于它的最早開始時間)
        for (int i = 1; i < reverseTopoVertexes.size(); i++) {  // 按逆拓撲排序，周遊各個頂點
            Object vertex = reverseTopoVertexes.get(i);
            Object[] neighbors = graph.neighbors(vertex);  // 求出目前節點的所有後繼節點
            int latestStartTime = Integer.MAX_VALUE;  // 用于存儲目前節點的最小最晚開始時間
            for (Object neighbor : neighbors) {  // 周遊目前節點的所有後繼節點，找出最小的最晚開始時間
                int delay = vl.get(neighbor) - graph.getEdgeWeight(vertex, neighbor); // 求出<vertex, neighbor>這條路徑的最晚開始時間
                if (delay < latestStartTime) latestStartTime = delay;  // 如果它比最晚開始時間小，則更新最晚開始時間
            }
            vl.put(vertex, latestStartTime);
        }

        List<WeightedGraph.Edge> result = new ArrayList<>();
        List<WeightedGraph.Edge> edges = graph.getEdges();
        for (WeightedGraph.Edge edge : edges) {  // 周遊所有邊，若該邊的兩個節點都滿足“最晚開始時間=最早開始時間”，那麼該邊就是關鍵搞活動
            if (vl.get(edge.vertex1) == ve.get(edge.vertex1)
                    && vl.get(edge.vertex2) == ve.get(edge.vertex2
            )) {
                result.add(edge);
            }
        }
        return result;
    }