一、无向图的环判断
1.1 环的定义
此处的环不包含自环和平行边。
1-1-1 自环和平行边
无向图中环的示意图如下所示：
1-1-2 无向图中环的示意图
上图中，0-6-4-5构成了环
1.2 环的判断
基本思想：
采用深度优先遍历（DFS）无向图。
如果在遍历的过程中，发现某个顶点有一条边指向已经访问过的顶点，且这个已访问过的顶点不是当前顶点的父节点（这里的父节点表示DFS遍历顺序中的父节点），则说明图包含环。
如图1-1-2中：从0开始DFS，0->6->4->5，此时顶点5的一条边指向顶点0，顶点0已经访问过，但却不是顶点5的父节点（顶点4），说明出现了环。
源码实现：
public class Cycle {
private boolean[] marked;
private boolean hasCycle;
public Cycle(Graph G) {
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
if (!marked[v])
dfs(G, -1, v);
}
/**
* 从顶点v开始进行深度优先搜索，u表示v的前驱顶点：u->v
*/
private void dfs(Graph G, int u, int v) {
marked[v] = true;
for (int w : G.adj(v)) { // w为v的后继顶点：v->w
if (!marked[w]) { // 如果w未访问过
dfs(G, v, w);
} else {
// 如果w已经访问过，但w不是当前v的前驱顶点u
// 此时说明w有两个前驱结点
if (w != u) {
hasCycle = true;
break;
}
}
}
}
public boolean hasCycle() {
return hasCycle;
}
}
二、有向图的环路判断
2.1 环的定义
有向图中环的示意图如下所示：
2-1-1 有向图中环的示意图
1.2 环的判断
基本思想：
采用深度优先遍历（DFS）有向图。
用一个boolean数组表示顶点是否在调用栈上。如果发现某个顶点v有一条边指向已经访问过的顶点w，而w已经在深度优先调用栈上，则说明存在环。
1-2-1 有向图中环的查找
源码实现：
public class EdgeWeightedDirectedCycle {
private boolean[] marked; // marked[v] = has vertex v been marked?
private DirectedEdge[] edgeTo; // edgeTo[v] = previous edge on path to v
private boolean[] onStack; // onStack[v] = is vertex on the stack?
private Stack<DirectedEdge> cycle; // directed cycle (or null if no such cycle)
/**
* Determines whether the edge-weighted digraph {@code G} has a directed cycle and,
* if so, finds such a cycle.
* @param G the edge-weighted digraph
*/
public EdgeWeightedDirectedCycle(EdgeWeightedDigraph G) {
marked = new boolean[G.V()];
onStack = new boolean[G.V()];
edgeTo = new DirectedEdge[G.V()];
for (int v = 0; v < G.V(); v++)
if (!marked[v]) dfs(G, v);
// check that digraph has a cycle
assert check();
}
// check that algorithm computes either the topological order or finds a directed cycle
private void dfs(EdgeWeightedDigraph G, int v) {
onStack[v] = true;
marked[v] = true;
for (DirectedEdge e : G.adj(v)) {
int w = e.to();
// short circuit if directed cycle found
if (cycle != null) return;
// found new vertex, so recur
else if (!marked[w]) {
edgeTo[w] = e;
dfs(G, w);
}
// trace back directed cycle
else if (onStack[w]) {
cycle = new Stack<DirectedEdge>();
DirectedEdge f = e;
while (f.from() != w) {
cycle.push(f);
f = edgeTo[f.from()];
}
cycle.push(f);
return;
}
}
onStack[v] = false;
}
/**
* Does the edge-weighted digraph have a directed cycle?
* @return {@code true} if the edge-weighted digraph has a directed cycle,
* {@code false} otherwise
*/
public boolean hasCycle() {
return cycle != null;
}
/**
* Returns a directed cycle if the edge-weighted digraph has a directed cycle,
* and {@code null} otherwise.
* @return a directed cycle (as an iterable) if the edge-weighted digraph
* has a directed cycle, and {@code null} otherwise
*/
public Iterable<DirectedEdge> cycle() {
return cycle;
}
// certify that digraph is either acyclic or has a directed cycle
private boolean check() {
// edge-weighted digraph is cyclic
if (hasCycle()) {
// verify cycle
DirectedEdge first = null, last = null;
for (DirectedEdge e : cycle()) {
if (first == null) first = e;
if (last != null) {
if (last.to() != e.from()) {
System.err.printf("cycle edges %s and %s not incident\n", last, e);
return false;
}
}
last = e;
}
if (last.to() != first.from()) {
System.err.printf("cycle edges %s and %s not incident\n", last, first);
return false;
}
}
return true;
}
/**
* Unit tests the {@code EdgeWeightedDirectedCycle} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
// create random DAG with V vertices and E edges; then add F random edges
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]);
int F = Integer.parseInt(args[2]);
EdgeWeightedDigraph G = new EdgeWeightedDigraph(V);
int[] vertices = new int[V];
for (int i = 0; i < V; i++)
vertices[i] = i;
StdRandom.shuffle(vertices);
for (int i = 0; i < E; i++) {
int v, w;
do {
v = StdRandom.uniform(V);
w = StdRandom.uniform(V);
} while (v >= w);
double weight = StdRandom.uniform();
G.addEdge(new DirectedEdge(v, w, weight));
}
// add F extra edges
for (int i = 0; i < F; i++) {
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
double weight = StdRandom.uniform(0.0, 1.0);
G.addEdge(new DirectedEdge(v, w, weight));
}
StdOut.println(G);
// find a directed cycle
EdgeWeightedDirectedCycle finder = new EdgeWeightedDirectedCycle(G);
if (finder.hasCycle()) {
StdOut.print("Cycle: ");
for (DirectedEdge e : finder.cycle()) {
StdOut.print(e + " ");
}
StdOut.println();
}
// or give topologial sort
else {
StdOut.println("No directed cycle");
}
}
}
网友评论