深度优先搜索用于寻找图（G）中与顶点s连通的其它顶点。
设计一个类实现该算法，类的API如下：
算法实现
用递归的方法来遍历所有的顶点，在访问一个顶点时：
将它标记为已访问；
递归的访问它的没有被标记的邻接点。
实现代码如下：
public class DepthFirstSearch { private boolean[] marked; private int count; /** * Find the vertices connected to vertex s */ public DepthFirstSearch(Graph G, int s) { marked = new boolean[G.V()]; dfs(G, s); } private void dfs(Graph G, int v) { marked[v] = true; count++; for (int w:G.adj(v)) if (!marked[w]) dfs(G, w); } /** * Is vertex v connected to s */ public boolean marked(int v) { return marked[v]; } /** * Return the count of vertices connected to s */ public int count() { return count; } }
测试下图，与顶点0连通的顶点
public static void main(String[] args) { Graph G = new Graph(13); G.addEdge(0, 1); G.addEdge(0, 2); G.addEdge(0, 5); G.addEdge(0, 6); G.addEdge(3, 4); G.addEdge(3, 5); G.addEdge(4, 5); G.addEdge(4, 6); G.addEdge(7, 8); G.addEdge(9, 10); G.addEdge(9, 11); G.addEdge(9, 12); G.addEdge(11, 12); DepthFirstSearch search = new DepthFirstSearch(G, 0); for (int i=0; i<G.V(); i++) if (search.marked(i)) System.out.print(i + " "); }
输出结果：0 1 2 3 4 5 6
原文：https://www.cnblogs.com/deltadeblog/p/9037955.html