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

最近在看图论算法，准备后面每天更新一个自己看的算法以及相应实现：

拓扑排序概念

是对有向无环图的顶点的一种排序，它使得如果存在一条从v_i到v_j的路径。那么在排序中v_j出现在v_i后面。

算法思想：先在图中找一个没有入度的顶点，显示该顶点，并把它和它连的边一起删除，同时其他以该顶点为入度的顶点的入度数减一。之后，对其余顶点进行相同操作。

——————-

应用场景

这个很常见，比如在选课时，如果要想修某门课，必须提前修其他课，以及类似的场景。

两个相应的实现以及测试

实现一

#ifndef StringTopoSort_h#define StringTopoSort_h#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;class StringTopoSort{private:    vector
        
          indegree; vector
         
           *str_lists; stack
          
            mystack; stack
           
             mystack_print; int len;public: StringTopoSort(vector
            
             *,int _len);//构造函数，用于初始化 ~StringTopoSort();//析构函数，用于析构 int Creat(); void print_stack(); void topsort();};StringTopoSort::StringTopoSort(vector
             
              *_str_lists,int _len){ str_lists = _str_lists; for (int i = 0;i < _len;i++) indegree.push_back(0); //每个顶点的入度都初始化为0 len = _len;}StringTopoSort::~StringTopoSort() {}int StringTopoSort::Creat(){ return 1;}void StringTopoSort::topsort(){ for (int i = 0;i < len;i++) //计算每个顶点的入度数 { int string_size = str_lists[i].size(); for (int j = 1; j < string_size; j++) { int index = str_lists[i].at(j)-'1'; indegree[index] ++; } } for (int i = 0; i < len; i++) //顶点入度都为0的进栈 { if (indegree[i] == 0) mystack.push(i+1); } while (mystack.size() != 0) { int i = mystack.top(); mystack.pop(); mystack_print.push(i);//出完栈的元素重新进栈，用于最后的输出 for (int k = 1; k < str_lists[i-1].size(); k++) { indegree[str_lists[i-1].at(k) - '1']--; if (indegree[str_lists[i-1].at(k) - '1'] == 0) mystack.push(str_lists[i-1].at(k) - '0'); } }}void StringTopoSort::print_stack(){ if (mystack_print.size() < len) { cout << "有回路" << endl; cout << len << " " << mystack_print.size() << endl; } else { for (int i = 0; i < len; i++) { int value = mystack_print.top(); mystack_print.pop(); if (i == len - 1) cout << value; else cout << value << "-----"; } cout << endl; }}#endif // !StringTopoSort_h
             
            
           
          
         
        
       
      
     
    
   

#include"StringTopoSort.h"#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int main(){    vector
        
          headers[] = { { '1','4','2','3' },{ '2' },{ '3','5','2' }, { '4', '5'},{ '5' },{ '6','5','4' } }; //输入的数据为有向无环图的邻接表，出度的邻接表 StringTopoSort sorter(headers, 6);//调用拷贝构造函数 sorter.topsort(); sorter.print_stack(); system("pause"); return 0;}
        
       
      
     
    
   

实现二

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define MAX 9999using namespace std;stack
        
          mystack; //栈，后入先出int indegree[MAX];struct node{ int adjvex; node *next;};node adj[MAX];int Create(node adj[], int n, int m)//邻接表建表函数，n代表顶点数，m代表边数{ int i; node *p; for (i = 1; i <= n;i++)//对顶点初始化 { adj[i].adjvex = i; adj[i].next = NULL; } for (i = 1;i <= m;i++)//对边初始化 { cout << "请输入第" << i << "条边："; int u, v; cin >> u >> v; p = new node; p->adjvex = v; //其实就是类似于建立一个邻接表，每个adj[i]是邻接表的表头 p->next = adj[u].next; adj[u].next = p; } return 1;}void print(int n)//邻接表打印{ int i; node *p; for (i = 1;i <= n;i++) { p = &adj[i]; while (p != NULL) { cout << p->adjvex << " "; p = p->next; } cout << endl; }}void topsort(node adj[], int n){ int i; node *p; memset(indegree, 0, sizeof(indegree));//存放每个顶点的入度 for (i = 1;i <= n;i++)//遍历所有顶点指向的元素，后面的所有元素都可以增加其入度数 { p = adj[i].next; while (p != NULL) { indegree[p->adjvex]++; p = p->next; } } for (int i = 1;i <= n;i++) //所有入度为0的顶点都置为0 { if (indegree[i] == 0) mystack.push(i); } int count = 0; while (mystack.size() != 0) { i = mystack.top(); mystack.pop(); cout << i << " "; count++; for (p = adj[i].next;p != NULL;p = p->next) { int k = p->adjvex; indegree[k]--; if (indegree[k] == 0) mystack.push(k); } } cout << endl; if (count < n) cout << "有回路" << endl;}int main(){ int n, m; cout << "请输入顶点数和边数"; cin >> n >> m; Create(adj, n, m); cout << "输入的邻接表为：" << endl; print(n); cout << "拓扑排序结果为:" << endl; topsort(adj, n); system("pause"); return 0;}
        
       
      
     
    
   

分析与总结

其实编程思路很简单，对于输入的图，用邻接表表示，之后对于每个顶点，用一个数组来保存其入度个数信息， 先出栈顶层元素，然后对于以该元素为入度的其他顶点的入度个数都减一，在这个操作过程中如果遇到入度个数为0的顶点，就加入栈中。直到跳出循环。在上述操作过程中，每次出栈一个元素，就用计数器加一，最后判断计数器的值是否和顶点总数相等，如果不等，则说明该图有回路，相等，则证明排序成功。其实mystack的作用就是一个判断。