【概述】

有向無(wú)環(huán)圖（Directed Acyclic Graph），即 DAG 圖，是指任意一條邊有方向且不存在環(huán)路的圖。

判斷 DAG 圖的方法有：拓?fù)渑判?O(E)、Bellman-Ford 算法 O(VE)、使用鄰接表的 DFS?O(V+E) 等

【拓?fù)渑判颉?/h1>

拓?fù)渑判蜻^(guò)程如果能生成 n 個(gè)頂點(diǎn)序列，那么說(shuō)明圖中不存在環(huán)，即圖是一個(gè) DAG 圖

關(guān)于拓?fù)渑判?#xff1a;點(diǎn)擊這里

struct Node{int x;int num;Node(){}Node(int x,int num):x(x),num(num){} }; vector<Node> edge[N]; int vis[N]; int n,m; bool dfs(int x,int m){if(vis[x]==1)//出環(huán)return true;if(vis[x]==-1)//已訪問(wèn)return false;vis[x]=1;//正在被占用for(int i=0;i<edge[x].size();i++)if(edge[x][i].num<=m&&dfs(edge[x][i].x,m))return true;vis[x]=-1;//解除占用并標(biāo)記訪問(wèn)return false; } bool judge(){memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++)if(!vis[i]&&dfs(i,m))return true;return false; } int main(){cin>>n>>m;for(int i=1;i<=m;i++){int x,y;cin>>x>>y;edge[x].push_back(Node(y,i));}if(judge())cout<<"Yes"<<endl;elsecout<<"No"<<endl;return 0; }

【Bellman-Ford 算法】

由于 Bellman-Ford 算法除求最短路外只能判斷是否存在負(fù)環(huán)，因此可以先把權(quán)值設(shè)為 -1，再進(jìn)行判斷

關(guān)于 Bellman-Ford 算法：點(diǎn)擊這里

struct Node{int x,y;int w; }G[N*2]; int dis[N];bool ford(int n, int m){for(int i=1;i<n;i++){for(int j=0;j<m;j++){int x=G[j].x;int y=G[j].y;int w=G[j].w;if(dis[y]>dis[x]+w)dis[y]=dis[x]+w;}}for(int i=0;i<m;i++)if(dis[G[i].x]>dis[G[i].y]+G[i].w)return true;return false; } int main(){int n,m;scanf("%d%d",&n,&m);memset(dis,INF,sizeof(dis));for(int i=0;i<m;i++){scanf("%d%d",&G[i].x,&G[i].y);G[i].w=-1;//把權(quán)值全部改為-1if(G[i].x==0)dis[G[i].y]=-1;}if(ford(n,m))printf("NO\n");elseprintf("YES\n");return 0; }

【使用鄰接表的 DFS】

枚舉起點(diǎn)進(jìn)行 DFS，如果當(dāng)某個(gè)點(diǎn)與起點(diǎn)相同，則說(shuō)明存在環(huán)，即非 DAG 圖?

struct Edge{int next;int to; }edge[N*2]; int cnt,head[N],son[N]; bool vis[N]; void add(int from,int to){edge[++cnt].next=head[from];edge[cnt].to=to;head[from]=cnt; } bool flag; void dfs(int x){if(vis[x])flag=false;if(!flag)return;vis[x]=true;for(int i=head[x];i!=-1;i=edge[i].next)dfs(edge[i].to);vis[x]=false; }int main(){int n,m;scanf("%d%d",&n,&m);memset(head,-1,sizeof(head));for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);}for(int i=1;i<=n;i++){flag=true;dfs(i);if(!flag)break;}if(flag)printf("Yes\n");elseprintf("No\n");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的图论 —— 环与块 —— DAG 图判定的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。