数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英文
经济学
心理学
社会科学
时尚
法律检测无向图中的环
要检测无向图中是否存在环，我们应该对给定的图使用 DFS 遍历。对于每个访问过的顶点 v，当我们找到任何相邻顶点 u 时，u 已被访问，并且 u 不是顶点 v 的父级。那么将检测到一个环。
我们假设对于任何一对顶点，没有平行边。
Input and Output: Adjacency matrix 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 Output: The graph has cycle.
算法
dfs(vertex, visited, parent)
Input: The start vertex, the visited set, and the parent node of the vertex.
Output: True a cycle is found.Begin add vertex in the visited set for all vertex v which is adjacent with vertex, do if v = parent, then return true if v is not in the visited set, then return true if dfs(v, visited, vertex) is true, then return true done return false End hasCycle(graph) Input: The given graph. Output: True when a cycle has found.Begin for all vertex v in the graph, do if v is not in the visited set, then go for next iteration if dfs(v, visited, φ) is true, then //parent of v is null return true return false done End
示例
#include<iostream>
#include<set>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 0, 1, 1, 0}
};
bool dfs(int vertex, set<int>&visited, int parent) {
visited.insert(vertex);
for(int v = 0; v<NODE; v++) {
if(graph[vertex][v]) {
if(v == parent) //if v is the parent not move that direction
continue;
if(visited.find(v) != visited.end()) //if v is already visited
return true;
if(dfs(v, visited, vertex))
return true;
}
}
return false;
}
bool hasCycle() {
set<int> visited; //visited set
for(int v = 0; v<NODE; v++) {
if(visited.find(v) != visited.end()) //when visited holds v, jump to next iteration
continue;
if(dfs(v, visited, -1)) { //-1 as no parent of starting vertex
return true;
}
}
return false;
}
int main() {
bool res;
res = hasCycle();
if(res)
cout << "The graph has cycle." << endl;
else
cout << "The graph has no cycle." << endl;
}输出
The graph has cycle.
更新时间：16-Jun-2020
7K+ 浏览
广告