Java中深度優(yōu)先與廣度優(yōu)先的示例分析

這篇文章給大家分享的是有關(guān)Java中深度優(yōu)先與廣度優(yōu)先的示例分析的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

Java可以用來干什么

Java主要應(yīng)用于：1. web開發(fā)；2. Android開發(fā)；3. 客戶端開發(fā)；4. 網(wǎng)頁開發(fā)；5. 企業(yè)級應(yīng)用開發(fā)；6. Java大數(shù)據(jù)開發(fā)；7.游戲開發(fā)等。

在編程生活中，我們總會遇見樹性結(jié)構(gòu)，這幾天剛好需要對樹形結(jié)構(gòu)操作，就記錄下自己的操作方式以及過程。現(xiàn)在假設(shè)有一顆這樣樹，（是不是二叉樹都沒關(guān)系，原理都是一樣的）

1、深度優(yōu)先

英文縮寫為DFS即Depth First Search.

深度優(yōu)先搜索是一種在開發(fā)爬蟲早期使用較多的方法。它的目的是要達到被搜索結(jié)構(gòu)的葉結(jié)點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中，當一個超鏈被選擇后，被鏈接的HTML文件將執(zhí)行深度優(yōu)先搜索，即在搜索其余的超鏈結(jié)果之前必須先完整地搜索單獨的一條鏈。深度優(yōu)先搜索沿著HTML文件上的超鏈走到不能再深入為止，然后返回到某一個HTML文件，再繼續(xù)選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時，說明搜索已經(jīng)結(jié)束。其過程簡要來說是對每一個可能的分支路徑深入到不能再深入為止，而且每個節(jié)點只能訪問一次。對于上面的例子來說深度優(yōu)先遍歷的結(jié)果就是：A,B,D,E,I,C,F,G,H.(假設(shè)先走子節(jié)點的的左側(cè))。

深度優(yōu)先遍歷各個節(jié)點，需要使用到堆（Stack）這種數(shù)據(jù)結(jié)構(gòu)。stack的特點是是先進后出。整個遍歷過程如下：

首先將A節(jié)點壓入堆中，stack（A）;

將A節(jié)點彈出，同時將A的子節(jié)點C，B壓入堆中，此時B在堆的頂部，stack(B,C)；

將B節(jié)點彈出，同時將B的子節(jié)點E，D壓入堆中，此時D在堆的頂部，stack（D,E,C）；

將D節(jié)點彈出，沒有子節(jié)點壓入,此時E在堆的頂部，stack（E，C）；

將E節(jié)點彈出，同時將E的子節(jié)點I壓入，stack（I,C）；

...依次往下，最終遍歷完成，Java代碼大概如下：

public void depthFirst() {
	Stack<Map<String, Object>> nodeStack = new Stack<Map<String, Object>>();
	Map<String, Object> node = new HashMap<String, Object>();
	nodeStack.add(node);
	while (!nodeStack.isEmpty()) {
		node = nodeStack.pop();
		System.out.println(node);
		//獲得節(jié)點的子節(jié)點，對于二叉樹就是獲得節(jié)點的左子結(jié)點和右子節(jié)點
		List<Map<String, Object>> children = getChildren(node);
		if (children != null && !children.isEmpty()) {
			for (Map child : children) {
				nodeStack.push(child);
			}
		}
	}
}
//節(jié)點使用Map存放

2、廣度優(yōu)先

英文縮寫為BFS即Breadth FirstSearch。其過程檢驗來說是對每一層節(jié)點依次訪問，訪問完一層進入下一層，而且每個節(jié)點只能訪問一次。對于上面的例子來說，廣度優(yōu)先遍歷的 結(jié)果是：A,B,C,D,E,F,G,H,I(假設(shè)每層節(jié)點從左到右訪問)。

廣度優(yōu)先遍歷各個節(jié)點，需要使用到隊列（Queue）這種數(shù)據(jù)結(jié)構(gòu)，queue的特點是先進先出，其實也可以使用雙端隊列，區(qū)別就是雙端隊列首位都可以插入和彈出節(jié)點。整個遍歷過程如下：

首先將A節(jié)點插入隊列中，queue（A）;

將A節(jié)點彈出，同時將A的子節(jié)點B，C插入隊列中，此時B在隊列首，C在隊列尾部，queue（B，C）；

將B節(jié)點彈出，同時將B的子節(jié)點D，E插入隊列中，此時C在隊列首，E在隊列尾部，queue（C，D，E）;

將C節(jié)點彈出，同時將C的子節(jié)點F，G，H插入隊列中，此時D在隊列首，H在隊列尾部，queue（D，E，F(xiàn)，G，H）；

將D節(jié)點彈出，D沒有子節(jié)點，此時E在隊列首，H在隊列尾部，queue（E，F(xiàn)，G，H）；

...依次往下，最終遍歷完成，Java代碼大概如下：

public void breadthFirst() {
 Deque<Map> nodeDeque = new ArrayDeque<Map>();
 Mapnode = new HashMap();
 nodeDeque.add(node);
 while (!nodeDeque.isEmpty()) {
  node = nodeDeque.peekFirst();
  System.out.println(node);
  //獲得節(jié)點的子節(jié)點，對于二叉樹就是獲得節(jié)點的左子結(jié)點和右子節(jié)點
  List<Map> children = getChildren(node);
  if (children != null && !children.isEmpty()) { 
   for (Map child : children) {
    nodeDeque.add(child);
   }
  }
 }
}
//這里使用的是雙端隊列，和使用queue是一樣的

感謝各位的閱讀！關(guān)于“Java中深度優(yōu)先與廣度優(yōu)先的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！