具体算法1 - 局部依赖和拓扑排序

写在前面：之前我们已经介绍了所有常见的数据结构和算法思想。下面的一段时间会给出一些具体的算法，来解决实际编程中会遇到的问题。

本章关键词

局部依赖、执行顺序

问题阐述

我们知道，一个完整的项目会包含很多代码源文件，编译器在编译代码的时候会根据代码间的依赖关系按照一定的顺序编译源文件。比如，A.cpp 依赖 B.cpp，在编译的时候，就要先编译 B.cpp，然后编译 A.cpp： 编译的依赖关系.jpg
在生活中我们也常常有这样的问题，例如穿衣服的顺序： 穿衣服的依赖关系.jpg
你会发现，对一同一组局部依赖关系，整体的全局有序序列可能有多种解，这没问题。

算法解析

要解决这种问题，我们选择使用 图 这种表达性很强的数据结构。解决这种问题的算法有很多，这里介绍两种：Kahn算法 和 DFS深度优先搜索算法。

1.Kahn算法

我们先从图中，找出一个入度为 0 的顶点，将其输出到拓扑排序的结果序列中（对应代码中就是把它打印出来），并且把这个顶点从图中删除（也就是把这个顶点可达的顶点的入度都减 1）。我们循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。

代码如下：

public void topoSortByKahn() {
  int[] inDegree = new int[v]; // 统计每个顶点的入度
  for (int i = 0; i < v; ++i) {
    for (int j = 0; j < adj[i].size(); ++j) {
      int w = adj[i].get(j); // i->w
      inDegree[w]++;
    }
  }
  LinkedList<Integer> queue = new LinkedList<>();
  for (int i = 0; i < v; ++i) {
    if (inDegree[i] == 0) queue.add(i);
  }
  while (!queue.isEmpty()) {
    int i = queue.remove();
    System.out.print("->" + i);
    for (int j = 0; j < adj[i].size(); ++j) {
      int k = adj[i].get(j);
      inDegree[k]--;
      if (inDegree[k] == 0) queue.add(k);
    }
  }
}

2.DFS算法
我们可以使用深度优先遍历的思路实现拓扑排序：

public void topoSortByDFS() {
  // 先构建逆邻接表，边s->t表示，s依赖于t，t先于s
  LinkedList<Integer> inverseAdj[] = new LinkedList[v];
  for (int i = 0; i < v; ++i) { // 申请空间
    inverseAdj[i] = new LinkedList<>();
  }
  for (int i = 0; i < v; ++i) { // 通过邻接表生成逆邻接表
    for (int j = 0; j < adj[i].size(); ++j) {
      int w = adj[i].get(j); // i->w
      inverseAdj[w].add(i); // w->i
    }
  }
  boolean[] visited = new boolean[v];
  for (int i = 0; i < v; ++i) { // 深度优先遍历图
    if (visited[i] == false) {
      visited[i] = true;
      dfs(i, inverseAdj, visited);
    }
  }
}

private void dfs(
    int vertex, LinkedList<Integer> inverseAdj[], boolean[] visited) {
  for (int i = 0; i < inverseAdj[vertex].size(); ++i) {
    int w = inverseAdj[vertex].get(i);
    if (visited[w] == true) continue;
    visited[w] = true;
    dfs(w, inverseAdj, visited);
  } // 先把vertex这个顶点可达的所有顶点都打印出来之后，再打印它自己
  System.out.print("->" + vertex);
}

有几个地方需要解释：

• 这个算法需要构建逆邻接表
• 算法的核心：递归处理每个顶点。在输出这个顶点前，先处理完这个顶点依赖的所有顶点，然后输出这个顶点。不要问依赖顶点所依赖的顶点怎么办，递归就是这么神奇。你要记得在递归时我们强调的：递归只需要考虑当前递归层和下一递归层的关系，而不关心下一层和下下一层的关系。

3.复杂度分析
两个算法都有常数次地访问了所有的顶点和边，所以他们的时间复杂度都是O(V+E)，其中 V 表示顶点的个数，E 表示边的个数。

---

在这里，我自己用代码实现了这个算法，一并发出来供你参考：

import queue


class Graph:
    def __init__(self, n):
        '''
        构造一个邻接表
        :param n: 顶点的个数
        '''
        self.v = [[] for i in range(n)]

    def addEdge(self, x, y):
        '''
        建立一个有向边
        :param x: 起始顶点（被依赖的点）
        :param y: 终止顶点
        :return: None
        '''
        self.v[x].append(y)

    def __repr__(self):
        return str(self.v)

    def topoSortByKahn(self):
        '''
        使用Kahn算法进行拓扑排序，并输出排序内容
        :return: None
        '''
        inDegree = [0 for i in self.v]  # 保存入度的表
        que = queue.Queue(len(self.v))  # 一个队列，用于保存入度为 0 的点

        for i_index, i_list in enumerate(self.v):  # 初始化 inDegree
            for j in i_list:  # i_index 为起始顶点，j 为终止顶点，这里要为 inDegree[i_index] ++
                inDegree[j] += 1

        for vertex, inD in enumerate(inDegree):  # 初始化 que
            if inD == 0:
                que.put(vertex)

        while not que.empty():  # 对入度为 0 的点输出，并将以该点为起始的边删掉，逐渐所有的点都会输出
            l = que.get()
            print('->', l)
            for i in self.v[l]:  # i 为从 l 出发的所有 终止顶点
                inDegree[i] -= 1
                if inDegree[i] == 0:
                    que.put(i)

    def topoSortByDFS(self):
        '''
        使用深度优先遍历的方法完成拓扑排序
        :return:None
        '''

        # 首先，构建逆邻接表 和 浏览记录数组
        invers = [[] for i in self.v]
        visted = [False for i in self.v]

        for i_index, i_list in enumerate(self.v):  # 构建邻接表
            for j in i_list:  # i_index 为起始顶点，j 为终止顶点，这里要为 invers[j] 添加 i_index
                invers[j].append(i_index)

        for vertex, v_list in enumerate(invers):  # 对所有点进行遍历输出
            self.dg(vertex, invers, visted)

    def dg(self, cur_vertex, invers, visted):
        '''
        将访问所有的以 cur_vertex 为终点的边的起点，也就是访问所有 cur_vertex 的依赖项，并递归下去，最终会遍历所有点
        :param cur_vertex:当前要处理的点
        :param invers:逆邻接表
        :param visted:访问表
        :return:
        '''
        if visted[cur_vertex] == True:
            return
        else:
            visted[cur_vertex] = True

        invers_copy = invers[cur_vertex].copy()
        for i in invers_copy:  # 处理当前点的所有依赖点

            self.dg(i, invers, visted)
            invers[cur_vertex].remove(i)

        if invers[cur_vertex] == []:  # 处理完依赖项后，逆邻接表的相关存储内容会被清空，所以其实不用这个 if 判断程序也是正确的
            print('->', cur_vertex)


if __name__ == '__main__':
    g = Graph(6)
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(0, 3)
    g.addEdge(0, 4)
    g.addEdge(0, 5)
    g.addEdge(1, 3)
    g.addEdge(2, 3)
    g.addEdge(4, 3)
    g.addEdge(5, 3)
    g.topoSortByKahn()
    print('-----------------------')
    g.topoSortByDFS()

---

以上就是关于拓扑排序的全部内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间