【数据结构与算法】【算法思想】拓扑排序

缺乏、安全感 2022-12-04 07:37 184阅读 0赞

#### 一、拓扑排序 ####

拓扑排序是基于依赖关系的节点，根据依赖关系而生成的序列。节点和依赖关系往往要生成有向无环图。类似的问题有：穿衣服裤子的先后关系，生成穿衣序列/专业课程与前置课程形成的课程学习序列/代码编译依赖关系形成的编译顺序序列。

public class Graph { 
      private int v; // 顶点的个数
      private LinkedList<Integer> adj[]; // 邻接表
    
      public Graph(int v) { 
        this.v = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i) { 
          adj[i] = new LinkedList<>();
        }
      }
    
      public void addEdge(int s, int t) {  // s先于t，边s->t
        adj[s].add(t);
      }
    }

#### 二、实现 ####

##### 0x00Kahn 算法 #####

根据邻接表，很容易计算出每个节点的入度。  
遍历每个入度，将入度为0的节点，放入队列。  
队列不空，循环：  
取出队首元素，输出他，然后遍历他的邻接节点，将邻接节点入度-1，如果邻接节点恰好为0，将节点放入队列。  
**时间复杂度：求入度：O(v+e),循环输出O(v+e)合起来O(v+e)  
空间复杂度：入度数组O(v),队列<O(v)**

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);
        }
      }
    }

##### 0x01 DFS 深度优先搜索算法 #####

1.  深度优先搜索是要一通到底的，所以需要将邻接表返过来，改成逆邻接表。方法：遍历邻接表，对i的每个邻接节点j，都将i加到j的逆邻接表中。
2.  图的深度优先搜索不跟树一样：没有根节点，所以要尝试从每个节点都开始一次，自然需要visited数组防止重复。对某个节点深度遍历完之后，再输出。
3.  **时间复杂度：求入度：O(v+e),顶点两次 边一次  
    空间复杂度：入度数组O(v),队列<O(v)**

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);
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

**显然用于拓扑排序的图是不可以成环的。自然拓扑排序算法可以用于检测图中的环。对于kahn算法，极端化思维：如果所有的节点形成大环，那么没有入度为0的节点，也就不会有任何输出。普通思维：如果存在环，总会到一个位置，没有任何节点入度为0。就会少输出节点。如果输出的节点<总结点，意味着存在环。**

#### 三、思考题 ####

**\[1\]在今天的讲解中，我们用图表示依赖关系的时候，如果 a 先于 b 执行，我们就画一条从 a 到 b 的有向边；反过来，如果 a 先于 b，我们画一条从 b 到 a 的有向边，表示 b 依赖 a，那今天讲的 Kahn 算法和 DFS 算法还能否正确工作呢？如果不能，应该如何改造一下呢？**

1.如果有向边反向，代表依赖关系，则Kahn算法无法工作，改造方法是：1.1把对入度的计算改为对出度的计算，即首先输出出度为0的节点，然后依次把与该节点相邻的节点的出度都减1，重复此过程直到输出所有节点；1.2 改成逆连接表，计算入度；而DFS算法中，则会输出相反的结果，由于邻接表和逆邻接表正好是相反的，因此改造方法是：在DFS中，把对逆邻接表的的访问改为对邻接表的访问即可。

**\[2\]我们今天讲了两种拓扑排序算法的实现思路，Kahn 算法和 DFS 深度优先搜索算法，如果换做 BFS 广度优先搜索算法，还可以实现吗？**  
2.采用BFS算法，无法保证在某个结点输出之前，先输出其所有依赖的节点，因为有可能该节点和其所依赖的某个节点，可能在BFS算法中处于同一个层次，因为这两个节点可能都和某个节点相邻，因此，采用BFS算法，有可能会输出不正确的拓扑次序。

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/2e3764f79d7b40b8b6a9252b40e5e508.png
[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png