▶ 书中第四章部分程序，加上自己补充的代码，图的环相关
● 无向图中寻找环
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Graph;
import edu.princeton.cs.algs4.Stack; public class class01
{
private boolean[] marked;
private int[] edgeTo;
private Stack<Integer> cycle; // 用来存储环的顶点 public class01(Graph G)
{
if (hasSelfLoop(G))
return;
if (hasParallelEdges(G))
return;
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
for (int v = 0; v < G.V(); v++)
{
if (!marked[v])
dfs(G, -1, v); // 首次调用时参数 u 要赋成非定点编号的值
}
} private void dfs(Graph G, int u, int v) // 深度优先探索，传入起点 v 及其父顶点 u
{
marked[v] = true;
for (int w : G.adj(v))
{
if (cycle != null) // 已经找到环，停止搜索（只搜一个就停）
return;
if (!marked[w])
{
edgeTo[w] = v;
dfs(G, v, w);
}
else if (w != u) // 顶点 w 已经遍历，且边 w-v 不是来边 u-v，说明成环
{
cycle = new Stack<Integer>();
for (int x = v; x != w; x = edgeTo[x]) // 这里 w 指向该环在本次遍历中最早遇到的顶点
cycle.push(x);
cycle.push(w);
cycle.push(v);
}
}
} private boolean hasSelfLoop(Graph G) // 自环
{
for (int v = 0; v < G.V(); v++)
{
for (int w : G.adj(v))
{
if (v == w)
{
cycle = new Stack<Integer>();
cycle.push(v);
cycle.push(v);
return true;
}
}
}
return false;
} private boolean hasParallelEdges(Graph G) // 平行边
{
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
{
for (int w : G.adj(v))
{
if (marked[w])
{
cycle = new Stack<Integer>();
cycle.push(v);
cycle.push(w);
cycle.push(v);
return true;
}
marked[w] = true;
}
for (int w : G.adj(v)) // 恢复遍历前的状态，一遍其他顶点进行检查
marked[w] = false;
}
return false;
} public boolean hasCycle()
{
return cycle != null;
} public Iterable<Integer> cycle() // 将环用迭代器方式输出
{
return cycle;
} public static void main(String[] args)
{
In in = new In(args[0]);
Graph G = new Graph(in);
class01 finder = new class01(G);
if (finder.hasCycle())
{
for (int v : finder.cycle())
StdOut.print(v + " ");
StdOut.println();
}
else
StdOut.println("\n<main> Graph is aycyclic.\n");
}
}
● 有向图中找环
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.Stack; public class class01
{
private boolean[] marked;
private int[] edgeTo;
private boolean[] onStack; // 记录递归顺序，递归回退时需要恢复（marked 不恢复）
private Stack<Integer> cycle; public class01(Digraph G)
{
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
onStack = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
{
if (!marked[v] && cycle == null)
dfs(G, v);
}
} private void dfs(Digraph G, int v) // 有向图不用传递起点的父顶点
{
onStack[v] = true; // 进入新节点时两个变量都要记录
marked[v] = true;
for (int w : G.adj(v))
{
if (cycle != null)
return;
if (!marked[w])
{
edgeTo[w] = v;
dfs(G, w);
}
else if (onStack[w]) // 用 onStack 来检测本次递归是否已经遍历过顶点 w
{
cycle = new Stack<Integer>();
for (int x = v; x != w; x = edgeTo[x])
cycle.push(x);
cycle.push(w);
cycle.push(v);
}
}
onStack[v] = false; // 递归回退，恢复搜索痕迹
} public boolean hasCycle()
{
return cycle != null;
} public Iterable<Integer> cycle()
{
return cycle;
} public static void main(String[] args)
{
In in = new In(args[0]);
Digraph G = new Digraph(in);
class01 finder = new class01(G);
if (finder.hasCycle())
{
for (int v : finder.cycle())
StdOut.print(v + " ");
StdOut.println();
}
else
StdOut.println("\n<main> Graph is aycyclic.\n");
}
}
● 有向图中找环，广度优先搜索，非递归
package package01; import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.DigraphGenerator;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.Queue; public class class01
{
private Stack<Integer> cycle; public class01(Digraph G)
{
int[] indegree = new int[G.V()];
for (int v = 0; v < G.V(); v++)
indegree[v] = G.indegree(v);
Queue<Integer> queue = new Queue<Integer>();
for (int v = 0; v < G.V(); v++) // 所有入度为 0 的点入队，可作为遍历的起点，且绝对不是环的顶点
{
if (indegree[v] == 0)
queue.enqueue(v);
}
for (; !queue.isEmpty();) // 广度优先遍历，反复将 “入度为 0 的顶点的相邻顶点” 的入度减 1，相当于砍掉所有的链
{
int v = queue.dequeue();
for (int w : G.adj(v))
{
indegree[w]--;
if (indegree[w] == 0)
queue.enqueue(w);
}
}
int[] edgeTo = new int[G.V()]; // 父顶点数组是局部变量就够了
int root = -1; // 初始化为非顶点的编号
for (int v = 0; v < G.V(); v++) // 遍历顶点，如果还有顶点有入度，说明存在环，将其顶点赋给 root
{
if (indegree[v] == 0) // 跳过链中的顶点
continue;
else
root = v;
for (int w : G.adj(v)) // 顺着入度仍大于 0 的顶点往前爬
{
if (indegree[w] > 0)
edgeTo[w] = v;
}
}
if (root != -1) // root 被覆盖，说明存在环，root 值为最后一个换的最后一个顶点
{
cycle = new Stack<Integer>();
//for (boolean[] visited = new boolean[G.V()]; !visited[root]; visited[root] = true, root = edgeTo[root]);
// 源码中维护了最后一个环的顶点集，但是以后再也没有用到，删掉
cycle.push(root);
for (int v = edgeTo[root]; v != root; v = edgeTo[v])
cycle.push(v);
//cycle.push(root); 多压一次根节点
}
} public boolean hasCycle()
{
return cycle != null;
} public Iterable<Integer> cycle()
{
return cycle;
} public static void main(String[] args)
{
int V = Integer.parseInt(args[0]); // 生成 DAG G(V,E)，然后再添上 F 条边
int E = Integer.parseInt(args[1]);
int F = Integer.parseInt(args[2]);
Digraph G = DigraphGenerator.dag(V, E);
for (int i = 0; i < F; i++)
{
int v = StdRandom.uniform(V);
int w = StdRandom.uniform(V);
G.addEdge(v, w);
}
StdOut.println(G);
class01 finder = new class01(G);
if (finder.hasCycle())
{
for (int v : finder.cycle())
StdOut.print(v + " ");
StdOut.println();
}
else
StdOut.println("\n<main> Graph is aycyclic.\n");
}
}