本文共 3018 字，大约阅读时间需要 10 分钟。

有向图的拓扑排序是数据处理和算法设计中的一个常见问题。拓扑排序使得我们可以确定一个顺序，使得对于图中的每一条有向边A→B，A在序列中都出现在B之前。以下将介绍两种常用的方法：一种基于广度优先搜索（BFS），另一种基于深度优先搜索（DFS）。

方法一：BFS实现

这种方法的核心思想是逐步构建结果列表，确保每次添加一个节点时，该节点是当前图中没有入边的节点。

示例代码

public class Solution {    public ArrayList topSort(ArrayList graph) {        ArrayList res = new ArrayList();        if (graph.isEmpty()) return res;        Map nodeMap = new HashMap();        for (DirectedGraphNode node : graph) {            nodeMap.put(node, new HashSet());        }        for (DirectedGraphNode node : graph) {            for (int i = 0; i < node.neighbors.size(); i++) {                nodeMap.get(node.neighbors.get(i)).add(node);            }        }        while (!graph.isEmpty()) {            int index = 0;            while (index < graph.size()) {                DirectedGraphNode cur = graph.get(index);                if (nodeMap.get(cur).isEmpty()) {                    res.add(cur);                    graph.remove(index);                    for (DirectedGraphNode elem : graph) {                        if (nodeMap.get(elem).contains(cur)) {                            nodeMap.get(elem).remove(cur);                        }                    }                } else {                    index++;                }            }        }        return res;    }}

方法二：DFS实现

这种方法采用深度优先搜索，确保每次处理一个节点时，先处理它的所有前置节点。

示例代码

public class Solution {    public ArrayList topSort(ArrayList graph) {        ArrayList res = new ArrayList();        if (graph.isEmpty()) return res;        Map status = new HashMap();        for (DirectedGraphNode elem : graph) {            status.put(elem, 0);        }        ArrayList templist = new ArrayList();        templist.add(null);        while (hasUnvisited(graph, status, templist)) {            DirectedGraphNode cur = templist.get(0);            templist.set(0, null);            search(cur, status, res);        }        return res;    }    public boolean hasUnvisited(ArrayList graph, Map status, ArrayList templist) {        for (DirectedGraphNode elem : graph) {            if (status.get(elem) == 0) {                templist.set(0, elem);                return true;            }        }        return false;    }    public void search(DirectedGraphNode cur, Map status, ArrayList res) {        if (status.get(cur) == 1) {            System.out.println("不是DAG");            return;        }        if (status.get(cur) == 2) {            return;        }        status.put(cur, 1);        for (DirectedGraphNode neigh : cur.neighbors) {            search(neigh, status, res);        }        status.put(cur, 2);        res.add(0, cur);    }}

总结

以上两种方法都可以实现对有向图的拓扑排序，无论是BFS还是DFS，都可以奏效。但选择哪种方法取决于具体的应用场景和性能需求。BFS方法通常更为简单，实现起来也较为直接；而DFS方法则允许灵活的选择，甚至可以通过修改实现来支持不同的拓扑排序风格。

转载地址：http://bywfk.baihongyu.com/