邻接表判断是否有回路
时间: 2023-12-19 09:32:21 浏览: 19
```java
// 使用邻接表判断图是否存在回路
public class Graph {
private int V; // 顶点数
private LinkedList<Integer> adj[]; // 邻接表
// 构造函数
Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// 添加边
void addEdge(int v, int w) {
adj[v].add(w);
}
// 检测从顶点v出发的深度优先搜索是否有环
Boolean isCyclicUtil(int v, Boolean visited[], int parent) {
visited[v] = true;
Integer i;
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i]) {
if (isCyclicUtil(i, visited, v))
return true;
} else if (i != parent)
return true;
}
return false;
}
// 检测图是否有环
Boolean isCyclic() {
Boolean visited[] = new Boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
for (int u = 0; u < V; u++)
if (!visited[u])
if (isCyclicUtil(u, visited, -1))
return true;
return false;
}
}
```