算法基础之有向图的拓扑序列

发布时间:2023年12月17日

有向图的拓扑序列

  • 核心思想: 拓扑排序 (有向图)

    • 有向图 —— 入度(有几条边指向自己) 出度(自己有几条边指向别人)

    • 边都是由小指向大 1->3 2->3 1->2

      • 将所有入度为0的点入队列 —> 宽搜
      #include <cstring>
      #include <iostream>
      #include <algorithm>
      
      using namespace std;
      
      const int N = 100010;
      
      int n, m;
      int h[N], e[N], ne[N], idx;
      int d[N];  //记录每个点的入度
      int q[N];  //数组模拟队列
      
      void add(int a, int b)
      {
          e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
      }
      
      bool topsort()
      {
          int hh = 0, tt = -1;
      
          for (int i = 1; i <= n; i ++ )
              if (!d[i])  //入度为0 作为起始点 加入队列
                  q[ ++ tt] = i;
      
          while (hh <= tt)
          {
              int t = q[hh ++ ];  //用数组模拟 因为取出元素以后不能删去元素
      
              for (int i = h[t]; i != -1; i = ne[i])
              {
                  int j = e[i];
                  if (-- d[j] == 0)  //删去j的一条边(入度-1)
                      q[ ++ tt] = j;  //到0 作为初始点 加入队列
              }
          }
      
          return tt == n - 1;  //如果全部加入队列(拓扑排序完成) 返回true
      }
      
      int main()
      {
          scanf("%d%d", &n, &m);
      
          memset(h, -1, sizeof h);
      
          for (int i = 0; i < m; i ++ )
          {
              int a, b;
              scanf("%d%d", &a, &b);
              add(a, b);  //a->b
      
              d[b] ++ ;  //加入一条边 b的入度+1
          }
      
          if (!topsort()) puts("-1");
          else
          {
              for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);  //队列存的顺序即为拓扑排序的顺序
              puts("");
          }
      
          return 0;
      }
      
文章来源:https://blog.csdn.net/Pisasama/article/details/134998395
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。