Java中深度優(yōu)先與廣度優(yōu)先的示例分析-創(chuàng)新互聯(lián)

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

10年積累的網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站建設(shè)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站設(shè)計(jì)制作后付款的網(wǎng)站建設(shè)流程，更有郊區(qū)免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。Java可以用來(lái)干什么

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

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

1、深度優(yōu)先

英文縮寫為DFS即Depth First Search.

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

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

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

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

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

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

將E節(jié)點(diǎn)彈出，同時(shí)將E的子節(jié)點(diǎn)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é)點(diǎn)的子節(jié)點(diǎn)，對(duì)于二叉樹(shù)就是獲得節(jié)點(diǎn)的左子結(jié)點(diǎn)和右子節(jié)點(diǎn)
		List<Map<String, Object>> children = getChildren(node);
		if (children != null && !children.isEmpty()) {
			for (Map child : children) {
				nodeStack.push(child);
			}
		}
	}
}
//節(jié)點(diǎn)使用Map存放

2、廣度優(yōu)先

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

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

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

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

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

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

將D節(jié)點(diǎn)彈出，D沒(méi)有子節(jié)點(diǎn)，此時(shí)E在隊(duì)列首，H在隊(duì)列尾部，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é)點(diǎn)的子節(jié)點(diǎn)，對(duì)于二叉樹(shù)就是獲得節(jié)點(diǎn)的左子結(jié)點(diǎn)和右子節(jié)點(diǎn)
  List<Map> children = getChildren(node);
  if (children != null && !children.isEmpty()) { 
   for (Map child : children) {
    nodeDeque.add(child);
   }
  }
 }
}
//這里使用的是雙端隊(duì)列，和使用queue是一樣的

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

網(wǎng)站欄目：Java中深度優(yōu)先與廣度優(yōu)先的示例分析-創(chuàng)新互聯(lián)
本文鏈接：http://muchs.cn/article16/dgcjdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標(biāo)簽優(yōu)化、外貿(mào)網(wǎng)站建設(shè)、定制開(kāi)發(fā)、網(wǎng)站設(shè)計(jì)、定制網(wǎng)站、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)