判断DAG图-白红宇

判断DAG图

阅读量：4306 次

发布时间：2019-06-06

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

拓扑排序O(E)， bellman O(VE) ，使用邻接表的dfs O(V+E) ，floyd O(N*N*N)

bellman算法只能判断是否存在负环。

所以可以先把权值全部设为-1

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 const int N = 10000 + 10; 7 const int INF = 1<<30; 8 struct node 9 {10     int u,v,weight;11 }g[N+N];12 int dist[N];13 inline int max(const int &a, const int &b)14 {15     return a < b ? b : a;16 }17 18 void init(int n)19 {20     for(int i=0; i<=n; ++i)21     {22     23         dist[i] = INF;24     }25 }26 27 void relax(int u, int v, int weight)28 {29     if(dist[v]  > dist[u] + weight)30         dist[v] = dist[u] + weight;    31 }32 bool bell(int n, int m)33 {34     int i,j;35     for(i=1; i
          
            dist[g[i].u] +g[i].weight)41             return true;42     return false;43 }44 int main()45 {46     int n,m,i,u,v;47     while(scanf("%d%d",&n,&m)!=EOF)48     {49         if(n==0 && m==0)50             break;51         init(n);52         for(i=0; i

View Code

枚举起点进行dfs，如果能遇到顶点和起点相同，则存在环

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 const int N = 10000 + 10; 7 vector
          
            g[N]; 8 int start; 9 bool vis[N],flag;10 void dfs(int u)11 {12     if(flag)13         return;14     for(int i=0;i

View Code

拓扑排序如果能生成n个顶点序列，那么说明是GAG图

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 const int N = 10000 + 10; 7 vector
          
            g[N]; 8 stack
           
             st; 9 int in[N],add[N],cnt;10 inline int max(const int &a, const int &b)11 {12 return a < b ? b : a;13 }14 void topSort(int n, int m)15 { 16 int u,i;17 for(i=1; i<=n; ++i)18 if(in[i]==0)19 st.push(i);20 while(!st.empty())21 {22 u = st.top();23 cnt++;24 st.pop();25 for(i=0; i