這是兩種常用的搜索方式截汪，但是應(yīng)用不同。
廣度優(yōu)先搜索植捎，在與搜索一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的最短距離衙解。
深得優(yōu)先搜索則側(cè)重圖中節(jié)點(diǎn)（假設(shè)節(jié)點(diǎn)代表某些事件）的發(fā)生順序。
廣度優(yōu)先搜索
廣度優(yōu)先搜索焰枢，類似與將圖組織稱一種樹的形式（但是可能不是一棵樹蚓峦，應(yīng)為有環(huán)形）。
然后分層進(jìn)行遍歷济锄，一層遍歷玩以后遍歷下一層暑椰。
使用隊(duì)列作為輔助。遍歷一層節(jié)點(diǎn)（也就是所有分支）的時(shí)候?qū)⑾乱粚庸?jié)點(diǎn)都添加到隊(duì)列拟淮，這樣干茉，一層結(jié)束以后，下一層的節(jié)點(diǎn)都在隊(duì)列中很泊。然后從該隊(duì)列中取元素角虫，進(jìn)行處理，處理的同時(shí)委造，將本層的節(jié)點(diǎn)的下一層（也就是相關(guān)聯(lián)節(jié)點(diǎn)再次添加到隊(duì)列）戳鹅。
在遍歷的時(shí)候需要一個(gè)memo，用來記錄該節(jié)點(diǎn)的遍歷狀態(tài)
第一種memo：已遍歷昏兆，正在遍歷枫虏，未遍歷。
原因在于爬虱，當(dāng)節(jié)點(diǎn)處于正在遍歷的狀態(tài)時(shí)隶债，如果節(jié)點(diǎn)的兄弟節(jié)點(diǎn)相互連通，那么第二個(gè)兄弟節(jié)點(diǎn)將會(huì)遍歷兩次跑筝，所以在第一次遇到一個(gè)節(jié)點(diǎn)的時(shí)候死讹，標(biāo)記為正在遍歷。當(dāng)再次遇到帶節(jié)點(diǎn)（兄弟節(jié)點(diǎn)要添加該節(jié)點(diǎn)進(jìn)隊(duì)列）曲梗，節(jié)點(diǎn)為正在遍歷赞警，因此跳過添加。
只添加未遍歷的節(jié)點(diǎn)進(jìn)隊(duì)列虏两。
第二種memo：已遍歷愧旦，為遍歷
這種memo方法，在添加如隊(duì)列之前就將其標(biāo)記為已遍歷定罢。這樣就避免了循環(huán)添加笤虫。
最短路徑
廣度有限搜索是可以的到最短路徑的，其的到最短路徑的方式在于：
每個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)值d表示該節(jié)點(diǎn)到起點(diǎn)的距離。同時(shí)存放一個(gè)本節(jié)點(diǎn)的父節(jié)點(diǎn)p耕皮。
在遍歷的過程中境蜕，如果本節(jié)點(diǎn)為未遍歷，那么：本節(jié)點(diǎn)的d等于上一個(gè)節(jié)點(diǎn)的d+1凌停，本節(jié)點(diǎn)的p等于上一個(gè)節(jié)點(diǎn)。
該賦值過程發(fā)生在添加到隊(duì)列之前售滤，某點(diǎn)已經(jīng)被添加到隊(duì)列罚拟，那么不應(yīng)該在賦值。
當(dāng)遍歷存在分支完箩，在某個(gè)點(diǎn)的時(shí)候兩個(gè)分支回合赐俗，第一次遍歷的時(shí)候?qū)⒒睾宵c(diǎn)添加到隊(duì)列，而本條分支就是會(huì)合點(diǎn)距離起始點(diǎn)的最短路徑弊知。而下一次遍歷到回合點(diǎn)的分支阻逮，一定大于等于本次的。
因?yàn)閺V度優(yōu)先遍歷按層遍歷秩彤。
最短路徑就保存在這些p中叔扼，從結(jié)束點(diǎn)，依次遞歸或者迭代的去訪問節(jié)點(diǎn)的p就可以到達(dá)起始點(diǎn)漫雷。
所以瓜富，可以看出，廣度優(yōu)先搜索其按層搜索的特征決定了可以用于最短路徑的搜索
深度優(yōu)先搜索
深度優(yōu)先搜索其搜索過程降盹，是与柑，優(yōu)先搜索分支的每一條分支。到達(dá)最深處返回蓄坏，再去搜索另一條分支价捧。
這類似與一個(gè)棧。
同樣也需要上面兩種形式的memo涡戳，來防止節(jié)點(diǎn)的循環(huán)添加结蟋。
在遍歷一個(gè)節(jié)點(diǎn)的時(shí)候，處理完該節(jié)點(diǎn)以后妹蔽，將其分支全部壓入棧中椎眯。再?gòu)臈Ｖ腥〕鲆粋€(gè)元素，處理該元素結(jié)束以后再將該元素的分支壓入此棧胳岂。编整。。乳丰。掌测。。如此循環(huán)，可以發(fā)現(xiàn)汞斧，椧褂簦基本上是在增長(zhǎng)的（當(dāng)分支只有一個(gè)時(shí)，不變化）粘勒，直到到達(dá)了分支的末端竞端，棧開始減少。
深度優(yōu)先搜索中的d（距離）并沒有什么用庙睡，因?yàn)槠湟呀?jīng)不再代表最短距離事富，而是取決于同一個(gè)節(jié)點(diǎn)不同分支的遍歷順序。
拓?fù)渑判?/h2>
因?yàn)樯疃葍?yōu)先搜索的搜索特性乘陪，其可以用來表示節(jié)點(diǎn)（將節(jié)點(diǎn)想象成事件）的發(fā)生先后順序统台，而遍歷的結(jié)果是其中一種可能的順序（存在環(huán)形）。
比如啡邑，我們從起始點(diǎn)開始遍歷圖贱勃，可以想為，穿衣的順序谤逼。
起始點(diǎn)有兩條分支：穿上衣贵扰，穿下衣，穿鞋襪森缠。
那么深度優(yōu)先搜索會(huì)盡可能深的遍歷其中一條分支拔鹰，比如穿上衣：內(nèi)衣->襯衣->外套。
在襯衣和外套之間可能存在戴領(lǐng)帶贵涵，帶臂章最終又在穿外套點(diǎn)回合列肢，因此是一個(gè)環(huán)形。
內(nèi)衣->襯衣->領(lǐng)帶->臂章->外套宾茂。
因?yàn)榄h(huán)形的存在因此給出一種順序瓷马。
因此如果每個(gè)點(diǎn)保存一個(gè)：該點(diǎn)開始處理時(shí)間，該點(diǎn)處理結(jié)束的時(shí)間跨晴。
那么在這兩個(gè)時(shí)間之間欧聘，是該節(jié)點(diǎn)的分支的處理時(shí)間。
{a{b...b}{c...c}a}
bb,cc 中間是其節(jié)點(diǎn)分支端盆。
最短路徑
http://blog.csdn.net/qq_32353771/article/details/52820176
使用最深優(yōu)先搜索求最短路徑怀骤，需要在遍歷完一個(gè)點(diǎn)的時(shí)候，再將這個(gè)點(diǎn)該為未遍歷焕妙。
但是低效蒋伦，如果一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)相互連通，那么一定會(huì)被重復(fù)遍歷焚鹊！
強(qiáng)連通分量
一個(gè)有向圖中痕届，如果任意兩點(diǎn)之間可到達(dá)，那么該圖是一個(gè)強(qiáng)連通圖
在一個(gè)非強(qiáng)連通圖中，某個(gè)子圖可以是強(qiáng)連通圖研叫，那么最大的強(qiáng)連通子圖就是強(qiáng)連通分量
