拓扑排序 | Notes

算法依赖的数据结构

一个完整的项目会包含很多代码源文件。编译器在编译整个项目的时候，需要按照依赖关系，依次编译每个源文件。
把源文件与源文件之间的依赖关系，抽象成一个有向图。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。

如果a先于b执行，也就是说b依赖于a，那么就在顶点a和顶点b之间，构建一条从a指向b的边。这个图不仅要是有向图，还要是一个有向无环图，不能存在循环依赖关系。图中一旦出现环，拓扑排序就无法工作了。拓扑排序是基于有向无环图的算法。

拓扑排序-数据结构- 图

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

    //s先于t，边 s->t
    public void addEdge(int s, int t) {
        adj[s].add(t);
    }
}

算法的实现

拓扑排序有两种实现方法：Kahn算法和DFS深度优先搜索算法。

Kahn算法
Kahn算法实际上用的是贪心算法思想。
定义数据结构的时候，如果s需要先于t执行，那就添加一条s指向t的边。如果某个顶点入度为0，表示没有任何顶点必须先于这个顶点执行，那么这个顶点就可以执行了。

先从图中找出一个入度为0的顶点，将其输出到拓扑排序的结果列中，并且把这个顶点从图中删除（把这个顶点可达的顶点的入度都减一）。循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。

拓扑排序-Kahn算法

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<>();
    //将入度为0的顶点加入队列
    for(int i = 0; i < v; ++i) {
        if(inDegree[i] == 0) queue.add(i);
    }

    while(!queue.isEmpty()) {
        //从队列中取出一个入度为0的顶点
        int i = queue.remove();
        System.out.print("->"+i);
        for(int j = 0; j < adj[i].size(); ++j) {
            //将该顶点指向的所有顶点的入度减1
            int k = adj[i].get(j);
            inDegree[k]--;
            //处理后入度为0的顶点加入队列
            if(inDegree[k] == 0) queue.add(k);
        }
    }
}

DFS算法
拓扑排序可以用深度优先搜索来实现。
深度优先遍历，遍历图中的所有顶点，并非只是搜索一个顶点到另一个顶点的路径。

拓扑排序-DFS算法

public void topoSortByDFS() {
    //先构建逆邻接表，边s->表示，s依赖于t，t先于s(与kahn相反)
    LinkedList<Integer> inverseAdj[] = new LinkedList[v];
    //申请空间
    for(int i = 0; i < v; ++i) {
        inverseAdj[i] = new LinkedList<>();
    }
    for(int i = 0; i < v; ++j) {
        //通过邻接表生成逆邻接表
        for(int j = 0; j < adj[i].size(); ++j) {
            int w = adj[i].get(j);//i->w存在一条订单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);
}

算法包含两个关键部分
第一部分是通过邻接表构造逆邻接表。邻接表中，边s->t表示s先于t执行，也就是t要依赖s。在逆邻接表中，边s->t表示s依赖于t，s后于t执行。

第二部分算法的核心，递归处理每个顶点。对于顶点vertex来说，先输出它可达的所有顶点，也就是先把它依赖的所有的顶点输出了，然后再输出自己。

时间复杂度分析：
Kahn代码中，每个顶点被访问了一次，每个边也被访问了一次，所以，Kahn算法的时间复杂度是O(V+E)（V表示顶点个数，E表示边的个数）。

DFS算法中，每个顶点被访问两次，每条边被访问依次，时间复杂度为O(V+E)。

图可以是不连通的，有可能是好几个不连通的子图构成，所以E不一定大于V，两者大小关系不确定。在表示时间复杂度的时候，V、E都要考虑在内。

总结

凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决。

拓扑排序还能检测图中环的存在。
在Kahn算法中，如果最后输出出来的顶点个数，少于图中顶点个数，图中还有入度不是0的顶点，那就说明图中存在环。

递归中，查找最终推荐人。每一次只查找一个用户的最终推荐人，不需要动用拓扑排序算法，只需要纪录已经访问过的用户ID，当用户ID第二次被访问的时候，说明存在环。

如果求数据库中所有用户之间的推荐关系，有没有存在环的情况。把用户之间的推荐关系，从数据库中加载到内存中，然后构建成有向图数据结构，再利用拓扑排序快速检测出是否存在环。