【演算法設計與分析基礎】10、深度優先遍歷

package cn.xf.algorithm.ch03;

import org.junit.Test;

/**
 * 深度優先遍歷
 * @author xiaof
 *
 */
public class DFS {

	public void deepFirstSearch(int graph[][], char points[], int marks[]){
		//吧所有點設置為0，表示還未訪問過
		for(int i = 0; i < marks.length; ++i) {
			marks[i] = 0;
		}
		//遍歷所有節點，挨個訪問
		for(int i = 0; i < points.length; ++i) {
			//判斷這個節點沒有被訪問過
			if(marks[i] == 0) {
//				System.out.println(" => " + key);
				//表示當前節點已經被遍歷
				marks[i] = 1;
				//深度遍歷，這裡是設置開始的節點
				StringBuilder path = new StringBuilder(points[i] + "");
				dfsw(graph, points, marks, i, path);
				System.out.println(path.toString());
			}
		}
	}
	
	//深度遍歷
	public void dfsw(int graph[][], char points[], int marks[], int curIndex, StringBuilder path){
		//遍歷其他節點，判斷是否相連
		for(int i = 0; i < marks.length; ++i) {
			//遍歷序列，並且獲取對應的位置index
			int curNum = graph[curIndex][i];
			if(marks[i] == 0 && curNum != 0) {
				//這個節點還沒有被訪問過,並且這個節點可達
//				System.out.println(" => " + points[i]);
				path.append(" => " + points[i]);
				marks[i] = 1;
				//遞歸到下一個
				dfsw(graph, points, marks, i, path);
			}
		}
	}

	@Test
	public void test1(){
		
		DFS dfs = new DFS();
		//a,b,c,d,e,f,g,h,i,j一共10個節點，兩顆樹
		//以下是矩陣圖，0表示不相連，1表示相連，節點本身自己到自己為0
		int graph[][] = {
			//   a,b,c,d,e,f,g,h,i,j
				{0,0,1,1,1,0,0,0,0,0},  //a 到其他節點
				{0,0,0,0,1,1,0,0,0,0},	//b 到其他節點
				{1,0,0,1,0,1,0,0,0,0},	//c 到其他節點
				{1,0,1,0,0,0,0,0,0,0},	//d 到其他節點
				{1,1,0,0,0,1,0,0,0,0},	//e 到其他節點
				{0,1,1,0,1,0,0,0,0,0},	//f 到其他節點
				{0,0,0,0,0,0,0,1,0,1},	//g 到其他節點
				{0,0,0,0,0,0,1,0,1,0},	//h 到其他節點
				{0,0,0,0,0,0,0,1,0,1},	//i 到其他節點
				{0,0,0,0,0,0,1,0,1,0}	//j 到其他節點
		};
		char points[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};
		int marks[] = {0,0,0,0,0,0,0,0,0,0};
		dfs.deepFirstSearch(graph, points, marks);
		
		
	}
}

結果：