Topological-Sort

拓扑排序

近日实现了一下拓扑排序，在这里记录一下拓扑排序的思想，并附上一个具体的题目

这里使用bfs实现

思想

对一个有向无环图(DAG-Directed Acyclic Graph)G进行拓扑排序，将G中的所有顶点拍成一个线性序列，使得图中任何一对顶点u和v，若(u, v) 属于 E(G)，则u在线性序列中出现在v之前。

也就是说，由某集合上的偏序得到这个集合的全序

步骤

1. 计算所有节点的入度(in-degree)
2. 将所有入度为0的节点加入一个队列
3. 然后出队，得到一个元素
4. 将该元素指向的所有节点的入度都减1
5. 在减的过程中，如果其减后为0则将该元素也加入队列
6. 继续进行步骤3，直到队列为空

运用

除了以上提到的用途，还可以判断有向图中是否有环：

根据出队元素的个数，若出队元素的个数等于图中节点的个数，则该图无环；否则该有向图存在环

例题

hdu-1285

题目大意就是进行拓扑排序，来获得比赛的名次，但是名次的排列要按照最小的字典序–即同等排名的元素，编号小的放在前面，这里使用了两种方式

• 使用priority_queue代替queue

  保证每次出队的元素都是最小的那个，具体AC代码如下:

  #include <iostream>
  #include <vector>
  #include <algorithm>
  #include <queue>
  using namespace std;
  
  int n, m;
  
  vector<int> topSort(vector<vector<int> >& G){
      vector<int> result;
    // 记录每个节点的入度
      vector<int> in(n + 1, 0);
      for (int i = 1; i < G.size(); i++) {
          for (int j = 0; j < G[i].size(); j++) {
              in[G[i][j]]++;
          }
      }
    // 使用优先队列，保证每次出队的元素最小
      priority_queue<int, vector<int>, greater<int > > queue;
    // 第一次入队，所有in-degree为0的节点
      for (int i = 1; i < in.size();i ++) {
          if (in[i] == 0) {
              queue.push(i);
          }
      }
      while (!queue.empty()) {
          int current = queue.top();
          queue.pop();
        // 出队元素存到排序结果中
          result.push_back(current);
        // 将所有current指向的节点的in-degree全部-1
          for (int i = 0; i < G[current].size(); i++) {
              in[G[current][i]]--;
            // 如果减到0则入队
              if (in[G[current][i]] == 0) {
                  queue.push(G[current][i]);
              }
          }
      }
      return result;
  }
  
  int main() {
      while (cin >> n >> m) {
          vector<vector<int> > G(n + 1);
          int a, b;
          for (int i = 0; i < m; i++) {
              cin >> a >> b;
              G[a].push_back(b);
          }
          vector<int> result = topSort(G);
          for (int i = 0; i < result.size(); i++) {
              cout << result[i] << ((i == result.size() - 1) ? "" : " ");
          }
          cout << endl;
      }
  }

• 对于in-degree，每次从头开始寻找in-degree为0的节点，所以每次找到的都是当前编号最小的节点

  #include <iostream>
  #include <vector>
  #include <cstring>
  using namespace std;
  
  int n, m;
  // 存放结果
  int ans[505];
  
  void topSort(vector<vector<int>>& G) {
      vector<int> in(n + 1);
      for (int i = 0; i < G.size(); i++) {
          for (int j = 0; j < G[i].size(); j++) {
              in[G[i][j]]++;
          }
      }
      for (int i = 1; i <= n; i++) {
        // 每次从in数组的头部开始查找，那么每次找到的都是当前编号最小的节点
          int k = 1;
          while (in[k] != 0){
              k++;
          }
          ans[i] = k;
        // 将in[k]赋值为-1来表示删除节点
          in[k] = -1;
        // 将k连接的所有节点的in-degree都-1
          for (int j = 0; j < G[k].size(); j++) {
              in[G[k][j]]--;
          }
      }
  }
  
  int main() {
      while (cin >> n >> m) {
          memset(ans, 0, sizeof(ans));
          int a, b;
          vector<vector<int> > G(n + 1);
          for (int i = 0; i < m; i++) {
              cin >> a >> b;
              G[a].push_back(b);
          }
          topSort(G);
          for (int i = 1; i <= n; i++) {
              cout << ans[i] << ((i == n ) ? "" : " ");
          }
          cout << endl;
      }
      return 0;
  }