图Graph--拓扑排序（Topological Sorting）

Michael阿明

发布于 2021-02-20 10:54:04

59300

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

一个项目往往会包含很多代码源文件。编译器在编译整个项目时，需按照依赖关系，依次编译每个源文件。比如，A.cpp依赖B.cpp，那在编译时，编译器需要先编译B.cpp，才能编译A.cpp。

编译器通过分析源文件或者编译配置文件（比如Makefile文件），来获取这种局部的依赖关系。那编译器又该如何通过源文件两两之间的局部依赖关系，确定一个全局的编译顺序呢？

1. 拓扑排序

可以把源文件与源文件之间的依赖关系，抽象成一个有向图。每个源文件对应图中的一个顶点，源文件之间的依赖关系就是顶点之间的边。
如果a先于b执行，也就是说b依赖于a，那么就在顶点a和顶点b之间，构建一条从a指向b的边。而且，这个图不仅要是有向图，还要是一个有向无环图，也就是不能存在像a->b->c->a这样的循环依赖关系。

数据结构如下：

#include <list>
using namespace std;
class Graph
{
    int v;//顶点个数
    list<int> *adj;//邻接表
public:
    Graph(int vn)
    {
        v = vn;
        adj = new list<int> [v];
    }
    ~Graph()
    {
        delete [] adj;
    }
    void addEdge(int s, int t)//s先于t,边s->t
    {
        adj[s].push_back(t);
    }
};

2. 算法实现

2.1 Kahn算法

Kahn 算法是贪心思想
如果 s 需要先于 t 执行，就添加一条 s 指向 t 的边。如果某个顶点入度为0，也就表示，没有任何顶点必须先于这个顶点执行，那么这个顶点就可以执行了。
先从图中，找出一个入度为0的顶点，将其输出，并删除这个顶点（也就是把这个顶点可达的顶点的入度都减1）。我们循环执行上面的过程，直到所有的顶点都被输出。最后输出的序列，就是满足局部依赖关系的拓扑排序。

/**
 * @description: 拓扑排序，有向无环图
 * @author: michael ming
 * @date: 2019/7/29 0:36
 * @modified by: 
 */
#include <list>
#include <iostream>
#include <queue>

using namespace std;
class G_Node    //节点类
{
public:
    char info;//节点存储信息
    int indegree;//节点入度
    G_Node(char ch = '/'):info(ch),indegree(0){};
};
class Graph //图类
{
    int v;  //顶点个数
    list<G_Node*> *adj;  //邻接表
    G_Node *pGNode;//节点
public:
    Graph(int vn)
    {
        v = vn;
        adj = new list<G_Node*> [v];
        pGNode = new G_Node [v];
        cout << "请顺序输入节点的信息：" << endl;
        char ch;
        for(int i = 0; i < v; ++i)
            cin >> pGNode[i].info;
    }
    ~Graph()
    {
        delete [] pGNode;
        delete [] adj;
    }
    int findIdx(char ch)
    {
        for(int i = 0; i < v; ++i)
        {
            if(pGNode[i].info == ch)
                return i;
        }
        return -1;
    }
    void addEdge(char s, char t)//s先于t,边s->t
    {
        int i = findIdx(s), j = findIdx(t);
        if(i != -1 && j != -1)
        {
            adj[i].push_back(&pGNode[j]);
            pGNode[j].indegree++;
        }
    }
    void topoSortByKahn()
    {
        int i, j, k;
        queue<G_Node*> nodeQueue;
        //坑，要存指针在里面，后面才能修改入度，否则修改的是副本
        G_Node *frontNode;
        list<G_Node*>::iterator it;
        for(i = 0; i < v; ++i)
        {
            if(pGNode[i].indegree == 0)
                nodeQueue.push(&pGNode[i]);//找到所有入度为0的入队
        }
        while(!nodeQueue.empty())
        {
            frontNode = nodeQueue.front();
            i = findIdx(frontNode->info);
            nodeQueue.pop();
            cout << frontNode->info << "->";//输出入度为0的，出队
            for(it = adj[i].begin(); it != adj[i].end(); ++it)
            {
                (*it)->indegree--;//该节点后面跟着的所有节点入度-1
                if((*it)->indegree == 0)//入度如果等于0
                    nodeQueue.push(*it);//入队，一会可以打印了
            }
        }
    }
};
int main()
{
    Graph grp(6);
    grp.addEdge('a','b');
    grp.addEdge('b','e');
    grp.addEdge('b','d');
    grp.addEdge('d','c');
    grp.addEdge('d','f');
    grp.topoSortByKahn();
    return 0;
}

2.2 DFS算法

构造逆邻接表。邻接表中，边 s->t 表示 s 先于 t 执行，也就是 t 要依赖 s。在逆邻接表中，边 s->t 表示 s 依赖于 t，s 后于 t 执行。
递归处理每个顶点。对顶点 i ，先输出它可达的所有顶点，也就是，先把它依赖的所有的顶点输出了，然后再输出自己。

在上面程序代码中添加

list<G_Node*> *reverseadj;  //逆邻接表
reverseadj = new list<G_Node*> [v];

void addEdge(char s, char t)//s先于t,边s->t
{
      int i = findIdx(s), j = findIdx(t);
      if(i != -1 && j != -1)
      {
          adj[i].push_back(&pGNode[j]);//s->t，邻接表
          pGNode[j].indegree++;
          reverseadj[j].push_back(&pGNode[i]);//逆邻接表
      }
  }

void topoSortByDFS()
{
    cout << "topoSortByDFS:" << endl;
    bool *visited = new bool [v];
    memset(visited,0,v*sizeof(bool));
    for(int i = 0; i < v; ++i)  //深度优先遍历
    {
        if(visited[i] == false)
        {
            visited[i] = true;
            dfs(i, reverseadj, visited);
        }
    }
    delete [] visited;
}
void dfs(int i, list<G_Node*> *reverseadj, bool *visited)
{
    int idx;
    for(auto it = reverseadj[i].begin(); it != reverseadj[i].end(); ++it)
    {
        idx = findIdx((*it)->info);
        if(visited[idx] == true)
            continue;
        visited[idx] = true;
        dfs(idx,reverseadj,visited);
    }
    cout << pGNode[i].info << "->";
}

2.3 时间复杂度

Kahn代码中，每个顶点被访问了一次，每个边也都被访问了一次，所以，Kahn算法的时间复杂度就是O（V+E）（V表示顶点个数，E表示边的个数）。
DFS算法中，每个顶点被访问两次，每条边都被访问一次，所以时间复杂度也是O（V+E）。
注意，这里的图可能不是连通的，有可能是有好几个不连通的子图构成，所以，E并不一定大于V，V E的大小关系不定。所以，在表示时间复杂度的时候，V、E都要考虑在内。

3. 应用

拓扑排序应用非常广泛。凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决。
拓扑排序还能检测图中环的存在。对于Kahn算法来说，如果最后输出出来的顶点个数，少于图中顶点个数，图中还有入度不是0的顶点，那就说明，图中存在环。
关于图中环的检测，递归那节讲过一个例子，在查找最终推荐人的时候，可能会因为脏数据，造成存在循环推荐，比如，用户A推荐了用户B，用户B推荐了用户C，用户C又推荐了用户A。如何避免这种脏数据导致的无限递归？这就是环的检测问题。因为我们每次都只是查找一个用户的最终推荐人，所以，我们并不需要动用复杂的拓扑排序算法，而只需要记录已经访问过的用户ID，当用户ID第二次被访问的时候，就说明存在环。