1. 概述

拓扑排序是将一个有向无环图的所有顶点进行线性序列。且该序列必须满足下面两个条件：

  • 每个顶点出现且只出现一次

  • 若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面

拓扑排序并不会改变图的结构，它只是在图结构中找到一条有先后顺序的路径。当图结构为有向无环图时，才有拓扑排序一说

所谓先后顺序的路径，例如：当我们学习一套视觉班的课程时
image.png

  • 首先要具备OpenGL基础和3D数学的基础，才能学习OpenGL ES的学科

  • 在掌握OpenGL ES之后，才能进一步完成GPUImage的学习

  • 当前面的学科掌握后，最终才能完成Metal的学习

示例中，想要完成整体课程学习，我们就要按照各个学科的先后顺序，层层递进，依次学习。而这个学习路径，就是一个具有先后顺序的路径

在⼀个表示⼯程的有向图中，⽤顶点表示活动，⽤弧表示活动之间的优先关系。这样有向图为顶点表示活动的⽹，我们称之为AOV⽹（Activity On Vertex Network）
image.png

  • 在有向图中，边被称之为“弧”

  • 图结构不一定是线性的，但我们按照任务执行过程中的先后关系，最终要输出一个线性排序

  • 拓扑排序只是在任务执行过程中，选择的策略不同，它并不是唯一的答案。例如：以下两种路径：

    • C1 → C2 → C3 → C4 → C5

    • C2 → C1 → C3 → C4 → C5

2. 拓扑序列

设G = (V, E)是⼀个具有n个顶点的有向图，V中的顶点序列V1、V2…Vn。若满⾜从顶点Vi到Vj有⼀条路径，则在顶点序列Vi必须在Vj之前，则我们称这样的顶点序列为拓扑序列

所谓拓扑排序，其实就是对⼀个有向图构造拓扑序列的过程

拓扑序列构造过程会产⽣两个结果：

  • 如果此⽹中的全部顶点被输出，则说明它不存在环（回路）的AOV⽹

  • 如果输出的顶点数少了，哪怕仅少了⼀个，也说明这个⽹存在环（回路），不是AOV⽹

3. 算法解析

对一张图进行拓扑排序时，我们无法预知该图是否可以完整拓扑排序。我们会根据执行结构，判断该图是否具备拓扑排序的条件

判断逻辑：当所有顶点都能按照先后顺序输出，该图为无环的AOV网，它符合拓扑排序的条件

由于拓扑排序选择的策略不同，它的答案并不是唯一的

3.1 存储方式

在开始拓扑排序的算法之前，我们还要确定AOV网图的存储方式。因为在算法的设计过程中，我们会进行一些删除操作，所以采用邻接表存储更具优势

3.2 数据结构

当一个顶点没有前驱结点，也就是入度为0时，就可以将它作为起始顶点

  • 入度：指有向图中某点作为图中边的终点的次数之和

所以，我们根据上述逻辑，可以设计出邻接表顶点的数据结构：
image.png

  • in：存储顶点的入度

  • data：顶点域，存储顶点信息

  • firstedge：指向边表头结点

3.3 算法思路

从AOV⽹中选择⼀个⼊度为0的顶点输出，然后从顶点表中删去此顶点，并删除以此顶点为尾的弧。继续重复此步骤，直到输出全部顶点或AOV⽹中不存在⼊度为0的顶点为⽌

这个算法实现过程中，我们需要借助另⼀个数据结构：栈，帮助我们规避在每次查找时，都要遍历AOV图中的顶点表，查找是否存在⼊度为0的顶点

  • 创建⼀个栈，⽤来存储⼊度为0的顶点序号

  • 遍历AOV图中顶点表，判断⼊度为0的顶点全部⼊栈

4. 算法分析

以此图为例：
image.png

将案例中的AOV网图，采用邻接表存储后的结果：
image.png

【初始化】将入度为0的顶点对应的索引值入栈。将count值初始为0，用于统计输出的顶点个数
image.png

【第一次执行】遍历stack栈，栈顶gettop = 3出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V3连接的顶点V2、V13，并将其⼊度-1，则V2、V13的⼊度值都为1。 它的⽬的是为了将V3顶点的弧删除
image.png

【第二次执行】 遍历stack栈，栈顶gettop = 1出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V1连接的顶点V2、V4、V8，并将其⼊度-1，则V2的⼊度为0，V4、V8的⼊度值都为1。它的⽬的是为了将V1顶点的弧删除。因为V2的⼊度为0，则V2⼊栈
image.png

【第三次执行】 遍历stack栈，栈顶gettop = 2出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V2连接的顶点V5、V6、V9，并将其⼊度-1，则V6的⼊度为0，V5的⼊度值为2，V9的⼊度值为1。它的⽬的是为了将V2顶点的弧删除。因为V6的⼊度为0，则V6⼊栈
image.png

【第四次执行】 遍历stack栈，栈顶gettop = 6出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V6连接的顶点V5，并将其⼊度-1，则V5的⼊度为1。它的⽬的是为了将V6顶点的弧删除
image.png

【第五次执行】 遍历stack栈，栈顶gettop = 0出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V0连接的顶点V4、V5、V11，并将其⼊度-1，则V4、V5的⼊度都为0，V11的⼊度为1。它的⽬的是为了将V0顶点的弧删除。因为V4、V5的⼊度为0，则V4、V5⼊栈
image.png

【第六次执行】 遍历stack栈，栈顶gettop = 4出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V4连接的顶点V7，并将其⼊度-1，则V7的⼊度为1。它的⽬的是为了将V4顶点的弧删除
image.png

【第七次执行】 遍历stack栈，栈顶gettop = 5出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V5连接的顶点V8、V12，并将其⼊度-1，则V8、V12的⼊度都为1。它的⽬的是为了将V5顶点的弧删除。因为V8、V12的⼊度为0，则V8、V12⼊栈
image.png

【第八次执行】 遍历stack栈，栈顶gettop = 8出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V8连接的顶点V7，并将其⼊度-1，则V7的⼊度为0。它的⽬的是为了将V8顶点的弧删除。因为V7的⼊度为0，则V7⼊栈
image.png

【第九次执行】 遍历stack栈，栈顶gettop = 7出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，由于V7没有连接的顶点，继续下一轮循环
image.png

【第十次执行】 遍历stack栈，栈顶gettop = 12出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V12连接的顶点V9，并将其⼊度-1，则V9的⼊度为0。它的⽬的是为了将V12顶点的弧删除。因为V9的⼊度为0，则V9⼊栈
image.png

【第十一次执行】 遍历stack栈，栈顶gettop = 9出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V9连接的顶点V10、V11，并将其⼊度-1，则V10、V11的⼊度都为0。它的⽬的是为了将V9顶点的弧删除。因为V10、V11的⼊度为0，则V10、V11⼊栈
image.png

【第十二次执行】 遍历stack栈，栈顶gettop = 10出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，找到对应的V10连接的顶点V13，并将其⼊度-1，则V13的⼊度为0。它的⽬的是为了将V10顶点的弧删除。因为V13的⼊度为0，则V13⼊栈
image.png

【第十三次执行】 遍历stack栈，栈顶gettop = 13出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，由于V13没有连接的顶点，继续下一轮循环
image.png

【第十四次执行】 遍历stack栈，栈顶gettop = 11出栈，并count++

循环针对栈顶gettop顶点对应的弧链表进⾏遍历，由于V11没有连接的顶点，继续下一轮循环
image.png

【停止遍历】此时stack栈为空栈，停止遍历，程序执行结束

5. 代码实现

创建AovGraphLinked类，定义边表中的顶点结构，顶点表中的顶点结构，以及AOV网图的数据结构

  1. class AovGraphLinked {
  3.     fileprivate class Node {
  4.         var adj_vex_index : Int?;
  5.         var data : String?;
  6.         var next : Node?;
  7.     }
  9.     fileprivate class VNode {
  10.         var inDegree : Int;
  11.         var data : String?;
  12.         var firstEdge : Node?;
  14.         init(){
  15.             self.inDegree = 0;
  16.         }
  17.     }
  19.     fileprivate class Graph {
  20.         var adjList : [VNode]?;
  21.         var arc_num : Int;
  22.         var node_num : Int;
  24.         init(){
  25.             self.arc_num = 0;
  26.             self.node_num = 0;
  27.         }
  28.     }
  30.     fileprivate var graph : Graph;
  32.     init(){
  33.         self.graph = Graph();
  34.     }
  35. }

实现创建方法：

class AovGraphLinked {

    func create(nodes : [String], arcs : [[Int]]) {

        self.graph.arc_num = arcs.count;
        self.graph.node_num = nodes.count;
        self.graph.adjList = [VNode]();

        for data in nodes {
            let vNode = VNode();
            vNode.data = data;
            self.graph.adjList?.append(vNode);
        }

        for arc in arcs {

            let i = arc[0];
            let j = arc[1];

            let node = Node();
            node.adj_vex_index = j;
            node.data = self.graph.adjList![j].data;
            self.graph.adjList![j].inDegree += 1;

            let vNode = self.graph.adjList![i];
            node.next = vNode.firstEdge;
            vNode.firstEdge = node;
        }
    }
}

实现打印方法：

class AovGraphLinked {

    func traverse() -> String {

        var str : String = "";

        for vNode in self.graph.adjList! {

            var node = vNode.firstEdge;

            str += "入度：\(vNode.inDegree)，\(vNode.data!)"

            while(node != nil){
                str += " -> \(node!.data!)";
                node = node?.next;
            }

            str += "\n";
        }

        return str;
    }
}

实现拓扑排序方法：

class AovGraphLinked {

    fileprivate var stack : LinearStack<Int>?;

    func topologicalSort() -> String {

        var str : String = "";

        self.stack = LinearStack<Int>.init(capacity: self.aovGraph.adjList!.count);

        // 1、将入度为0的顶点对应的索引值入栈
        for i in 0 ..< self.aovGraph.adjList!.count {

            let aovNode = self.aovGraph.adjList![i];

            if(aovNode.inDegree > 0){
                continue;
            }

            self.stack!.push(element: i);
        }

        var count = 0;

        // 2、遍历stack
        while(!self.stack!.isEmpty()) {

            // 将数据依次出栈，并且count++
            let i = self.stack!.pop()!;
            count += 1;

            // 通过索引在顶点表中获取顶点
            let aovNode = self.aovGraph.adjList![i];
            str += "\(aovNode.data!) -> ";

            // 获取顶点指向边表中的头结点
            var node = aovNode.firstEdge;

            // 遍历边表中的顶点
            while(node != nil){

                // 将顶点的入度-1
                let aovNode = self.aovGraph.adjList![node!.adj_vex_index!];
                aovNode.inDegree -= 1;

                // 如果-1后顶点的入度为0，将其索引值入栈
                if(aovNode.inDegree == 0){
                    self.stack!.push(element: node!.adj_vex_index!);
                }

                node = node?.next;
            }
        }

        // 3、判断输出的顶点是否为正确的拓扑排序
        if(count < self.aovGraph.node_num){
            str = "执行失败，图结构非AOV网图";
        }

        return str;
    }
}

按照示例中的AOV网图逻辑，使用代码创建邻接表，并打印拓扑排序的结果：

let nodes = ["V0", "V1", "V2", "V3", "V4", "V5", "V6", "V7", "V8", "V9", "V10", "V11", "V12", "V13"];
let arcs = [[0, 4], [0, 5], [0, 11],
            [1, 2], [1, 4], [1, 8],
            [2, 5], [2, 6], [2, 9],
            [3, 2], [3, 13],
            [4, 7],
            [5, 8], [5, 12],
            [6, 5],
            [8, 7],
            [9, 10], [9, 11],
            [10, 13],
            [12, 9]];

let aovGraphLinked = AovGraphLinked();
aovGraphLinked.create(nodes: nodes, arcs: arcs);
print(aovGraphLinked.traverse());
print("拓扑排序：\(aovGraphLinked.topologicalSort())");

-------------------------
//输出以下内容：
入度：0，V0 -> V11 -> V5 -> V4
入度：0，V1 -> V8 -> V4 -> V2
入度：2，V2 -> V9 -> V6 -> V5
入度：0，V3 -> V13 -> V2
入度：2，V4 -> V7
入度：3，V5 -> V12 -> V8
入度：1，V6 -> V5
入度：2，V7
入度：2，V8 -> V7
入度：2，V9 -> V11 -> V10
入度：1，V10 -> V13
入度：2，V11
入度：1，V12 -> V9
入度：2，V13

拓扑排序：V3 -> V1 -> V2 -> V6 -> V0 -> V4 -> V5 -> V8 -> V7 -> V12 -> V9 -> V10 -> V13 -> V11 ->

总结

概述：

  • 拓扑排序是将一个有向无环图的所有顶点进行线性序列。且该序列必须满足下面两个条件：

    • 每个顶点出现且只出现一次

    • 若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面

  • 拓扑排序并不会改变图的结构，它只是在图结构中找到一条有先后顺序的路径。当图结构为有向无环图时，才有拓扑排序一说

拓扑序列：

  • 设G = (V, E)是⼀个具有n个顶点的有向图，V中的顶点序列V1、V2…Vn。若满⾜从顶点Vi到Vj有⼀条路径，则在顶点序列Vi必须在Vj之前，则我们称这样的顶点序列为拓扑序列

  • 拓扑序列构造过程会产⽣两个结果：

    • 如果此⽹中的全部顶点被输出，则说明它不存在环（回路）的AOV⽹

    • 如果输出的顶点数少了，哪怕仅少了⼀个，也说明这个⽹存在环（回路），不是AOV⽹

算法解析：

  • 当所有顶点都能按照先后顺序输出，该图为无环的AOV网，它符合拓扑排序的条件

  • 由于拓扑排序选择的策略不同，它的答案并不是唯一的

  • 在算法的设计过程中，我们会进行一些删除操作，所以采用邻接表存储更具优势

  • 当一个顶点没有前驱结点，也就是入度为0时，就可以将它作为起始顶点

    • 入度：指有向图中某点作为图中边的终点的次数之和

算法思路：

  • 从AOV⽹中选择⼀个⼊度为0的顶点输出，然后从顶点表中删去此顶点，并删除以此顶点为尾的弧。继续重复此步骤，直到输出全部顶点或AOV⽹中不存在⼊度为0的顶点为⽌

  • 这个算法实现过程中，我们需要借助另⼀个数据结构：栈，帮助我们规避在每次查找时，都要遍历AOV图中的顶点表，查找是否存在⼊度为0的顶点

    • 创建⼀个栈，⽤来存储⼊度为0的顶点序号

    • 遍历AOV图中顶点表，判断⼊度为0的顶点全部⼊栈