深度优先搜索法：深度优先查找（depth-first search，DFS）可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时候，该算法紧接着处理与当前顶点邻接的未访问顶点。这个过程一直持续，直到遇到一个终点——该顶点的所有邻接顶点都已被访问过。在该终点上，该算法沿着来路后退一条边，并试着继续从那里访问未访问的顶点。再后退到起始顶点上，并且起始顶点也是一个终点时，该算法最终停了下来。这样，起始顶点所在的连通分量的所有顶点都被访问过了。如果，未访问过的顶点仍然存在，该算法必须从其中任一点开始，重复上述过程。
代码如下：
package com.qdcz.breadth.demo;
import java.util.Scanner;
/** * * <p>Title: DepthAl</p> * <p>Description: 深度优先搜索算法</p> * <p>Company:奇点创智 </p> * <p>Version: 1.0</p> * @author Administrator * @date 2017年6月6日 上午9:36:25 */public class DepthAl { private int count=0;//遍历次数 /** * *<p>Title: dfs</p> *<p>Description: 深度遍历核心算法前 的准备</p> *@param adjMat *@param value *@param result *@return void *@author Administrator *@date 2017年6月6日 上午10:24:25 */ public void dfs(int[][] adjMat,int [] value,char[] result){ for (int i = 0; i < value.length; i++) { if(value[i]==0){ char temp=(char) ('a'+i); System.out.println(); System.out.println("深度为："+i+",当前出发点："+temp); result[i]=temp;//存放当前正在遍历顶点下标字母 dfsVist(adjMat,value,result,i); } } } /** * *<p>Title: dfsVist</p> *<p>Description:深度遍历核心类</p> *@param adjMat *@param value *@param result *@param number *@return void *@author Administrator *@date 2017年6月6日 上午10:26:27 */ private void dfsVist(int[][] adjMat, int[] value, char[] result, int number) { value[number]=++count;//把++count赋值给当前正在遍历顶点判断值数组元素，变为非0，代表已被遍历 System.out.println("当前已行走到顶点value["+number+"]="+value[number]+" "); for (int i = 0; i < value.length; i++) { if(adjMat[number][i]==1&&value[i]==0){//当前顶点的相邻有相邻顶点可行走且其为被遍历 char temp=(char) ('a'+i); result[count]=temp; System.out.println("当前i值："+i+"到达"+temp+"地"); dfsVist(adjMat,value,result,i);//递归调用。行走第i个顶点 } } } public static void main(String[] args) { Scanner sca=new Scanner(System.in); int[] value=new int [5]; char[] result=new char[5]; int[][] adj=new int[5][5]; System.out.println("请输入列阵"); for (int i = 0; i < adj.length; i++) { for (int j = 0; j < adj[i].length; j++) { int x=sca.nextInt(); adj[i][j]=x; } } DepthAl de=new DepthAl(); de.dfs(adj, value, result); System.out.println(); System.out.println("判断节点是否遍历过，（0表示未遍历，非0表示遍历）"); for (int i = 0; i < value.length; i++) { System.out.print(" "+value[i]); } System.out.println("深度优先查找遍历顺序如下："); for (int i = 0; i <result.length; i++) { System.out.print(" "+result[i]); } }}
转载于:https://www.cnblogs.com/1x-zfd50/p/6958784.html
