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

1. 拓扑排序

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

数据结构如下：

#include 
   
    using namespace std;class Graph{
       int v;//顶点个数    list
    
      *adj;//邻接表public:    Graph(int vn)    {
           v = vn;        adj = new list
     
       [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 
   
    #include 
    
     #include 
     
      using namespace std;class G_Node    //节点类{
   public:    char info;//节点存储信息    int indegree;//节点入度    G_Node(char ch = '/'):info(ch),indegree(0){
   };};class Graph //图类{
       int v;  //顶点个数    list
      
        *adj;  //邻接表    G_Node *pGNode;//节点public:    Graph(int vn)    {
           v = vn;        adj = new list
       
         [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
        
          nodeQueue; //坑，要存指针在里面，后面才能修改入度，否则修改的是副本 G_Node *frontNode; list
         
          ::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
   
     *reverseadj;  //逆邻接表reverseadj = new list
    
      [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
   
     *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第二次被访问的时候，就说明存在环。

4. 类似题目练习

转载地址：https://michael.blog.csdn.net/article/details/97575522 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！