《图论》——深度优先搜索算法(DFS)

十大算法之广度优先遍历：

深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索递归调用包含以下操作：

（1）访问搜索到的未被访问的邻接点；

（2）将此顶点的visited数组元素值置1；

（3）搜索该顶点的未被访问的邻接点，若该邻接点存在，则从此邻接点开始进行同样的访问和搜索。

深度优先搜索DFS可描述为：

（1）访问v₀顶点；

（2）置 visited[v₀]=1；

（3）搜索v₀未被访问的邻接点w，若存在邻接点w，则DFS(w)。

遍历过程：     

 DFS在访问图中某一起始顶点 v后，由 v 出发，访问它的任一邻接顶点 w1；再从 w1出发，访问与 w1邻接但还没有访问过的顶点 w2；然后再从 w2出发，进行类似的访问，…如此进行下去，直至到达所有的邻接顶点都被访问过的顶点 u为止。

接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。如下图所示：

           在此小编的代码主要是根据如下图编写个人代码：

         采用的是存放于邻接链表中

        

         0：代表两个结点没有关联；1：代表两个结点有关联

         思路：

        1、定义vet数组存放结点信息；array数组为邻接链表，初始值为0；ifvisit是判断结点是否被访问过，初始值为false

        2、从A开始遍历，找到第一个与之关联的结点，然后从关联的结点开始遍历，直到所有的结点都被访问过

       代码如下：

package Graph;

import java.util.ArrayList;
import java.util.List;

/*
 * 深度优先遍历算法
 * DFS
 */
public class DFS {

	private static Object[] vet; //定义vet数组用来存放顶点信息
	private static int[][] array;  //定义邻接矩阵用来存放图的顶点信息
	private static int vexnum;      //存放边的条数
	private static boolean[] ifvisited; //存放节点是否被访问过
	private static List<Object> list = new ArrayList<Object>();  //定义一个临时的队列用来存放已经被访问过的节点

	public static void main(String[] args) {
		DFS map = new DFS(5); //初始化队列
		Character[] vet = {'A','B','C','D','E'};
		map.addVet(vet);   //添加顶点
		map.addEage(0,1);
		map.addEage(0,4);
		map.addEage(1,3);
		map.addEage(2,3);
		map.addEage(2,4);
		
		System.out.println("深度优先遍历开始...");
		visited(0);
		ifvisited[0]=true;
		map.dfs(0);
	}
	
	//深度优先遍历
	private void dfs(int k) {
		// TODO Auto-generated method stub
		for(int i=0; i< vexnum; i++)
			if(array[k][i] == 1 && !ifvisited[i])//判断是否被访问过，且其值是否为1
			{
				ifvisited[i] = true;
				visited(i);   //添加到被访问过的节点队列
				for(int j=0; j<vexnum; j++)
				{
					if(!ifvisited[j] && array[i][j] ==1)
					{
						ifvisited[j] = true;
						visited(j);
						dfs(j);  //下次循环从vet[j]开始循环
					}
				}
			}
	}

	//往临时队列里添加已经访问过的结点，并输出
	private static void visited(int k) {
		// TODO Auto-generated method stub
		list.add(vet[k]);
		System.out.println("   -> " + vet[k]);
	}

	//构建邻接矩阵，保存边的信息
	private void addEage(int m, int n) {
		// TODO Auto-generated method stub
		if(m!=n){
			array[m][n] =1;
			array[n][m] =1;
		}
		else
			return;
	}
	
	//初始化图的顶点
	private void addVet(Character[] vet2) {
		// TODO Auto-generated method stub
		this.vet = vet2;
	}

	//图的初始化
	public DFS(int num) {
		// TODO Auto-generated constructor stub
		vexnum = num;   //顶点
		vet = new Object[num]; //顶点的信息
		array = new int[num][num];  //边的信息
		ifvisited = new boolean[num]; //是否被访问过
		for(int i =0 ;i< num; i++)    //初始化边
		{
			ifvisited[i] = false;
			for(int j =0;j<num;j++)
				array[i][j]=0;
		}
	}


}

输出为：

深度优先遍历开始...
   -> A
   -> B
   -> D
   -> C
   -> E