必会算法总结(3) - 拓扑排序

​ 可能很多人第一次看到拓扑排序这个名字还以为它是种数值排序算法，它其实是对有向无环图AOV的一种特殊的遍历算法。拓扑排序是图论中比较重要的算法，在笔试中也是很常见的，需要知道的是只有无环图才有拓扑排序，所以使用我们可以使用拓扑排序判断一个图中是否存在环。那么下面我们就一起学习拓扑排序。

邻接表

在本示例中我们选用邻接表存储图，代码如下：

• Node

  public class Node {
      int value;
      List<Node> neighbors;
      
      public Node () {}
      
      public Node (int value) {
          this.value = value;
      }
      
      public Node (int value, List<Node> neighbors) {
          this.value = value;
          this.neighbors = neighbors;
      }
  }
  

• Graph

  public class Graph {
      List<Node> nodes;
      
      public Graph() {}
      
      public Graph(List<Node> nodes) {
          this.nodes = nodes;
      }
  }
  

节点入度

在拓扑排序中，我们要计算每一个节点的入度inDegree，在这里我选取图的广度优先遍历算法计算节点的入度，代码如下：

public Map<Node, Integer> findInDegree(Graph graph) {
    Map<Node, Integer> map = new HashMap<>();
    Deque<Node> deque = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    // 初始化map
    for (Node node : graph.nodes) {
        map.put(node, 0);
    }
    // 图的BFS遍历算法
    for (Node node : graph.nodes) {
        if (!visited.contains(node)) {
            deque.add(node);
            visited.add(node);
            while (!deque.isEmpty()) {
                int size = deque.size();
                for (int i = 0; i < size; i++) {
                    // 遍历节点的每个相邻节点
                    for (Node node1 : deque.remove().neighbors) {
                        map.put(node1, map.get(node1) + 1); // 更新节点的入度
                        if (!visited.contains(node1)) {
                            deque.add(node1);
                            visited.add(node1);
                        }
                    }
                }
            }
        }
    }
    return map;
}

核心算法

现在我们已经知道了每一个节点的入度，就可以进行拓扑排序了，代码如下：

public List<Node> topologicalSort(Graph graph) {
    // 计算每一个节点的入度
    Map<Node, Integer> map = findInDegree(graph);
    // 将所有入度为0的节点加入队列中
    Deque<Node> deque = new LinkedList<>();
    for (Map.Entry<Node, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 0) {
            deque.add(entry.getKey());
        }
    }
    // 重复拆边直到队列为空
    List<Node> list = new LinkedList<>();
    while (!deque.isEmpty()) {
        Node node = deque.remove();
        list.add(node);
        for (Node node1 : node.neighbors) {
            map.put(node1, map.get(node1) - 1);
            if (map.get(node1) == 0) {
                deque.add(node1);
            }
        }
    }
    // 如果图中存在环，则不存在拓扑排序，即不能遍历所有的节点
    if (list.size() != graph.nodes.size()) {
        throw new IllegalArgumentException("图中存在环");
    }
    return list;
}

最终总结

下面的代码是将上面所有代码的汇总，如下：

public class Main {
    
    static class Node {
        int value;
        List<Node> neighbors;
        
        public Node() {}
        
        public Node(int value) {
            this.value = value;
        }
        
        public Node(int value, List<Node> neighbors) {
            this.value = value;
            this.neighbors = neighbors;
        }
    }
    
    static class Graph {
        List<Node> nodes;
        
        public Graph() {}
        
        public Graph(List<Node> nodes) {
            this.nodes = nodes;
        }
    }
    
    public static Map<Node, Integer> findInDegree(Graph graph) {
        Map<Node, Integer> map = new HashMap<>();
        Deque<Node> deque = new LinkedList<>();
        Set<Node> visited = new HashSet<>();
        for (Node node : graph.nodes) {
            map.put(node, 0);
        }
        for (Node node : graph.nodes) {
            if (!visited.contains(node)) {
                deque.add(node);
                visited.add(node);
                while (!deque.isEmpty()) {
                    int size = deque.size();
                    for (int i = 0; i < size; i++) {
                        for (Node node1 : deque.remove().neighbors) {
                            map.put(node1, map.get(node1) + 1);
                            if (!visited.contains(node1)) {
                                deque.add(node1);
                                visited.add(node1);
                            }
                        }
                    }
                }
            }
        }
        return map;
    }
    
    public static List<Node> topologicalSort(Graph graph) {
        Map<Node, Integer> map = findInDegree(graph);
        Deque<Node> deque = new LinkedList<>();
        for (Map.Entry<Node, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 0) {
                deque.add(entry.getKey());
            }
        }
        List<Node> list = new LinkedList<>();
        while (!deque.isEmpty()) {
            Node node = deque.remove();
            list.add(node);
            for (Node node1 : node.neighbors) {
                map.put(node1, map.get(node1) - 1);
                if (map.get(node1) == 0) {
                    deque.add(node1);
                }
            }
        }
    	if (list.size() != graph.nodes.size()) {
        	throw new IllegalArgumentException("图中存在环");
    	}
        return list;
    }
    
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        node1.neighbors = Arrays.asList(node2);
        node2.neighbors = Arrays.asList(node3);
        node3.neighbors = Arrays.asList(node4);
        node4.neighbors = Arrays.asList(node2);

        Graph graph = new Graph(Arrays.asList(node1, node2, node3, node4));

        System.out.println(topologicalSort(graph));
    }
    
}