我們常常用檢查一張圖中是否包含環(huán)來判斷是否可以對這張圖進(jìn)行拓?fù)渑判颉５菍τ跓o向圖，由于無向圖中每條邊都可以表示成其對應(yīng)某點(diǎn)的入邊和出邊，所以不能用拓?fù)渑判虻姆椒▉頇z查是否包含環(huán)。但是我們可以用DFS方法來進(jìn)行檢查：從某一個點(diǎn)開始進(jìn)行DFS遍歷，如果在某個點(diǎn)所連接的點(diǎn)中，包含一個已經(jīng)經(jīng)過過的且不是這個點(diǎn)的父節(jié)點(diǎn)的點(diǎn)，說明有環(huán)。 代碼：
//有向圖bool checkLoop(vector<vector<int>>& graph,vector<int>& inDegree){ int n = graph.size(); vector<bool> v(n,false); //檢查點(diǎn)是否被經(jīng)過過 queue<int> vv(n,true);//入度為0的點(diǎn) vector<int> in = inDegree; for(int i = 0;i < n;++i) if(in[i] == 0) vv.push(i); while(vv.size()){ int x = vv.front(); vv.pop(); v[x] = true; for(int i = 0;i < n;++i) if(graph[x][i] == 1 && v[i] == false){ in.push(i); --in[i]; if(in[i] == 0) vv.push(i); } } for(int i = 0;i < n;++i) if(v[i] == false) return true; return false;}//無向圖bool checkLoop(vector<vector<int>> &graph){ int n = graph.size(); stack<int> v; vector<pair<bool,int>> through(n, make_pair(false,0));//bool表示有沒有through，int表示父節(jié)點(diǎn) v.push(0); while (v.size()) { int x = v.top(); v.pop(); if (through[x].first)continue; through[x].first = true; for (int i = 0; i < n; ++i) { if (graph[x][i] == 1) { if (through[i].first && through[i].second != i) return true; else if (!through[i].first) { v.push(i); through[i] = make_pair(false, x); } } } for (int i = 0; i < n; ++i) if (!through[i].first) return true; return false; }}新聞熱點(diǎn)
疑難解答
