127.拓扑排序

描述

给定一个有向图，图节点的拓扑排序被定义为：
对于每条有向边A--> B，则A必须排在B之前　　
拓扑排序的第一个节点可以是任何在图中没有其他节点指向它的节点

拓扑排序即按照图中每个结点优先级顺序将结点排好顺序

挑战

用 bfs 和 dfs 完成

注意事项

你可以假设图中至少存在一种拓扑排序

统计图中每个点的入度
将入度为0的点放到队列中去
bfs 整个图，每遍历一个循环即代表当前层全部遍历结束，结点的度减一

代码

/*
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> result = new ArrayList<>(); 
        if (graph == null) {
            return result;
        }
        
        // 调用定义好的方法统计入度
        Map<DirectedGraphNode, Integer> indegree = getIndegree(graph);
        
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        // 把indegree为0的存入queue中去
        for (DirectedGraphNode node : graph) {
            if (indegree.get(node) == 0) {
                queue.offer(node);
                result.add(node);
            }
        }
        // 进入BFS计算模版
        while (!queue.isEmpty()) {
            DirectedGraphNode node = queue.poll();
            for (DirectedGraphNode neighbor : node.neighbors) {
                // node 从队列中拿出来后，相邻结点的 indegree 要减 1
                // neighbor 的入度先减 1，然后再用 if 判断入度是否为 0
                // 在 BFS 中入度代表有几个结点在前面没有遍历
                indegree.put(neighbor, indegree.get(neighbor) - 1);
                if (indegree.get(neighbor) == 0) {
                    queue.offer(neighbor);
                    result.add(neighbor);
                }
            }
        }
        return result;
    }
    
    private Map<DirectedGraphNode, Integer> getIndegree(ArrayList<DirectedGraphNode> graph) {
        // 结点和度值之间是哈希表对应关系
        Map<DirectedGraphNode, Integer> indegree = new HashMap<>();
        // 初始化每个结点的入度为0
        for (DirectedGraphNode node : graph) {
            indegree.put(node, 0);
        }
        // node->neighbor
        for (DirectedGraphNode node : graph) {
            for (DirectedGraphNode neighbor: node.neighbors) {
                indegree.put(neighbor, indegree.get(neighbor) + 1);
            }
        }
        return indegree;
    }
}

应注意graph是存储着结点的数组
如下错误写法：

while (!queue.isEmpty()) {
    DirectedGraphNode node = queue.poll();
    // 前面已经for循环过所有结点了就不要再加下面这句
    for (DirectedGraphNode node : graph) {
        for (DirectedGraphNode neighbor : node.neighbors) {
            indegree.put(neighbor, indegree.get(neighbor) - 1);
            if (indegree.get(neighbor) == 0) {
                queue.offer(neighbor);
                result.add(neighbor);
            }
        }
    }
    return result;
}

3 .本题前提说明了图一定存在拓扑排序，如果没有说明一定存在拓扑排序，则把return result;换成

if (result.size() == graph.size()) {
    return result;
}
return null;

127.拓扑排序

代码

推荐阅读更多精彩内容