数据结构与算法-拓扑排序

初始化以及原理

拓扑排序基于一个有向无环图构成，当B依赖A，A先B执行的时候，我们画一条A–>B的边。如下代码：

public class Graph {
    private int v;
    private LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.v = v;
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) {
        adj[s].add(t);
    }
}

排序

有俩种排序算法Kahn算法

Kahn排序

采用贪心算法思想。

• 因为图的关系A–>B，A先执行，所以我们统计每个顶点的入度，凡是入度为0的说明没有依赖应该他先执行;
• 将顶点放到结果执行序列后。将该顶点从图中删除，即该顶点所到达的顶点的入度都-1，如果到0放到执行结果集中;
• 重复上一步直到所有的顶点都在执行序列中。

    public void topoSortByKahn() {
        //统计入度
        int[] indegree = new int[v];
        for (int i = 0; i < adj.length; i++) {
            for (int j = 0; j < adj[i].size(); j++) {
//              i先执行于j,j依赖i，统计j的入度w，等于统计j有多少前置依赖
                int w = adj[i].get(j);
                indegree[w]++;
            }
        }

        //队列，先执行的先放入队列中
        Map<Integer, LinkedList<Integer>> queueMap = new HashMap<>();

        //执行结果序列
        Map<Integer, List<Integer>> result = new HashMap<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queueMap.put(i, new LinkedList<>());
                queueMap.get(i).add(i);
                result.put(i, new ArrayList<>());
            }
        }

        //遍历队列
        for (Map.Entry<Integer, LinkedList<Integer>> queue : queueMap.entrySet()) {
            //循环放入执行队列
            while (!queue.getValue().isEmpty()) {
                //入度为0的顶点出队，放入到结果执行序列中
                int v = queue.getValue().remove();
                result.get(queue.getKey()).add(v);
                for (int j = 0; j < adj[v].size(); j++) {
                    //将当前顶点到达的顶点入度--,等价于删除顶点。
                    int k = adj[v].get(j);
                    indegree[k]--;
                    //如果这个顶点的入度为0将其放到到执行序列中重复知道队列为空
                    if (indegree[k] == 0) {
                        queue.getValue().add(k);
                    }
                }
            }
        }

        //打印
        for (List<Integer> ret : result.values()) {
            System.out.print(ret);
            System.out.println();
        }
    }

DFS

采用图的深度遍历法

• 制造逆邻接表
• 遍历所有的顶点，如果遇到

//深度优先遍历
public void topoSortByDFS() {
    //构造逆邻接表
    LinkedList<Integer>[] inverseAdj = new LinkedList[adj.length];
    for (int i = 0; i < adj.length; i++) {
        inverseAdj[i] = new LinkedList<>();
    }
    for (int i = 0; i < adj.length; i++) {
        for (int j = 0; j < adj[i].size(); j++) {
            int w = adj[i].get(j);
            inverseAdj[w].add(i);
        }
    }

    //深度遍历，遍历所有的顶点，从第一个顶点开始处理
    Map<Integer, Boolean> visted = new HashMap<>();
    for (int i = 0; i < adj.length; i++) {
        if (visted.get(i) == null || !visted.get(i)) {
            visted.put(i, true);
            dfs(i, inverseAdj, visted);
        }
    }
}

//递归深度遍历图
public void dfs(int v, LinkedList<Integer>[] inverseAdj, Map<Integer, Boolean> visted) {
    for (int j = 0; j < inverseAdj[v].size(); j++) {
        int w = inverseAdj[v].get(j);
        if (visted.get(w) != null && visted.get(w)) {
            continue;
        }
        visted.put(w, true);
        dfs(w, inverseAdj, visted);
    }
    //最后da
    System.out.print("->" + v);
}

时间复杂度

kahn复杂度是O(v+e),所有的顶点和边都访问了一次
dfs复杂度是O(v+e),所有的顶点和边都访问了一次

引申

如果A先于B执行我们的边是 A–>B，反过来A<–B，代码是否能正常执行？
答：不能，结果相反的结果，kahn：在算法中A–>B所以A的入度为0，这个入度为0很类似哨兵一样的机制，可以很方便的计入到执行结果中，并且可以一次减少入度。反之，我们入度为0的就变成了最后的数组，如果修改，需要统计出度凡是从出度为0的就是没有依赖的最先执行的，同时简历逆邻接表，在打印完出度为0的数据后在逆邻接表中循环递减出度同时输出,见下方代码。DFS:这个很简单，接别用逆邻接表了。

  public void topoSortByKahn() {
    //统计出度
    int[] outdegree = new int[v];
    LinkedList<Integer>[] inverseList = new LinkedList[v];
    for (int i = 0; i < v; i++) {
        inverseList[i] = new LinkedList<>();
    }
    for (int i = 0; i < adj.length; i++) {
        outdegree[i] = adj[i].size();
        for (int j : adj[i]) {
                inverseList[j].addLast(i);
        }
    }

    //队列，先执行的先放入队列中
    Map<Integer, LinkedList<Integer>> queueMap = new HashMap<>();

    //执行结果序列
    Map<Integer, List<Integer>> result = new HashMap<>();
    for (int i = 0; i < outdegree.length; i++) {
        if (outdegree[i] == 0) {
            queueMap.put(i, new LinkedList<>());
            queueMap.get(i).add(i);
            result.put(i, new ArrayList<>());
        }
    }

    //遍历队列
    for (Map.Entry<Integer, LinkedList<Integer>> queue : queueMap.entrySet()) {
        //循环放入执行队列
        while (!queue.getValue().isEmpty()) {
            //入度为0的顶点出队，放入到结果执行序列中
            int v = queue.getValue().remove();
            result.get(queue.getKey()).add(v);
            for (int j = 0; j < inverseList[v].size(); j++) {
                //将当前顶点到达的顶点入度--,等价于删除顶点。
                int k = inverseList[v].get(j);
                outdegree[k]--;
                //如果这个顶点的入度为0将其放到到执行序列中重复知道队列为空
                if (outdegree[k] == 0) {
                    queue.getValue().add(k);
                }
            }
        }
    }

    //打印
    for (List<Integer> ret : result.values()) {
        System.out.print(ret);
        System.out.println();
    }
}