沈阳网站建设服务电话,品牌建设人才队伍建设,一个可以看qq空间的网站,免费图片网站建设深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点#xff0c;沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时#xff0c;则回到上一个顶点#xff0c;继续试探别的顶点#xff0c;直至所有的顶点都被访问过。
下图示例的…深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时则回到上一个顶点继续试探别的顶点直至所有的顶点都被访问过。
下图示例的图从 0 开始遍历顺序如右图所示 无向图 G 的一个极大连通子图称为 G 的一个连通分量或连通分支。连通图只有一个连通分量即其自身非连通的无向图有多个连通分量。连通分量与连通分量之间没有任何边相连。深度优先遍历可以用来求连通分量。
下面以求连通分量为例来实现图的深度优先遍历称为 dfs。下面代码片段中visited 数组记录 dfs 的过程中节点是否被访问ccount 记录联通分量个数id 数组代表每个节点所对应的联通分量标记两个节点拥有相同的 id 值代表属于同一联通分量。
...
// 构造函数, 求出无权图的联通分量
public Components(Graph graph){// 算法初始化G graph;visited new boolean[G.V()];id new int[G.V()];ccount 0;for( int i 0 ; i G.V() ; i ){visited[i] false;id[i] -1;}// 求图的联通分量for( int i 0 ; i G.V() ; i )if( !visited[i] ){dfs(i);ccount ;}
}
...
图的深度优先遍历是个递归过程实现代码
...
// 图的深度优先遍历
void dfs( int v ){visited[v] true;id[v] ccount;for( int i: G.adj(v) ){if( !visited[i] )dfs(i);}
}
...
Java 实例代码
src/runoob/graph/Components.java 文件代码
package runoob.graph;import runoob.graph.read.Graph;/*** 深度优先遍历*/
public class Components {Graph G; // 图的引用private boolean[] visited; // 记录dfs的过程中节点是否被访问private int ccount; // 记录联通分量个数private int[] id; // 每个节点所对应的联通分量标记// 图的深度优先遍历void dfs( int v ){visited[v] true;id[v] ccount;for( int i: G.adj(v) ){if( !visited[i] )dfs(i);}}// 构造函数, 求出无权图的联通分量public Components(Graph graph){// 算法初始化G graph;visited new boolean[G.V()];id new int[G.V()];ccount 0;for( int i 0 ; i G.V() ; i ){visited[i] false;id[i] -1;}// 求图的联通分量for( int i 0 ; i G.V() ; i )if( !visited[i] ){dfs(i);ccount ;}}// 返回图的联通分量个数int count(){return ccount;}// 查询点v和点w是否联通boolean isConnected( int v , int w ){assert v 0 v G.V();assert w 0 w G.V();return id[v] id[w];}
}
