方法1：DFS判斷有向圖是否有環

對一個節點u進行DFS，判斷是否能從u回到自己這個節點，即是否存在u到u的回路。

color數組代表每個節點的狀態

-1代表還沒訪問，0代表正在被訪問，1代表訪問結束

如果一個狀態為0的節點，與它相連的節點狀態也為0，則有環

#include <iostream> #include <vector> #include <string.h> using namespace std; /* color代表每個結點的狀態，-1代表還沒被訪問，0代表正在被訪問，1代表訪問結束 如果一個狀態為“0”的結點，與他相連的結點狀態也為0的話就代表有環,這個可以用dfs實現 */ vector<int> vec[1200]; int color[1200]; bool flag;//標記是否有環void dfs(int x){if(flag){//如果有環就返回，否者繼續搜索return;}color[x] = 0;//x正在被反問，狀態為0for(int i = 0 ; i < vec[x].size() ; i++){if(color[vec[x][i]] == -1){//與x相連的結點狀態也為-1，代表還未被訪問，則繼續搜索dfs(vec[x][i]);} else if(color[vec[x][i]] == 0){//與x相連的結點狀態也為0，代表有環，返回flag = true;return;}}color[x] = 1;//對x的訪問結束 }int main(){memset(color, -1, sizeof(color));int n , m;cin >> n >> m;//n個結點，m條邊for(int i = 0 ; i < m ; i++){//建立鄰接表int u,v;cin >> u >> v;vec[u].push_back(v);}flag = false;dfs(1);if(flag){cout<<" have "<<endl;} else {cout << " not have" <<endl;}return 0; }

總結

以上是生活随笔為你收集整理的两种方法判断有向图是否有环【DFS】【拓扑排序】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。