DFS（Deep-first-search）:?是一種用于遍歷或搜索樹或圖的算法。 這個(gè)算法會(huì)盡可能深的搜索樹的分支。 當(dāng)節(jié)點(diǎn)v的所在邊都己被探尋過比肄，搜索將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始節(jié)點(diǎn)。 這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。（縱向搜索）
BFS（Breadth-First-Search）：是一種圖形搜索演算法莫秆。 簡單的說，BFS是從根節(jié)點(diǎn)開始悔详，沿著樹的寬度遍歷樹的節(jié)點(diǎn)镊屎，如果發(fā)現(xiàn)目標(biāo)，則演算終止茄螃。?算法分析:?BFS是一種盲目搜尋法缝驳，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果归苍。（橫向搜索）
找到有S到G的路徑
圖結(jié)構(gòu)如下：
DFS方式：
把圖寫成樹的形式
按節(jié)點(diǎn)向下搜尋
(S)
(SA,SD)
(SAB,SAD,SD)
(SABC,SABE,SAD,SD)
(SABED,SABEF,SAD,SD)
(SABEFG,SAD,SD)
搜索到第一條路徑 S--A--B--E--F--G
BFS方式：
從節(jié)點(diǎn)向下遍歷
(S)
(SA,SD)
(SD,SAB,SAD)
(SAB,SAD,SDA,SDE)
(SAD,SDA,SDE,SABC,SABE)
(SDA,SDE,SABC,SABE,SADE)
(SDE,SABC,SABE,SADE,SDAB)
(SABC,SABE,SADE,SDAB,SDEB,SDEF)
(SADE,SDAB,SDEB,SDEF,SABED,SABEF)
(SDAB,SDEB,SDEF,SABED,SABEF,SADEB,SADEF)
(SDEB,SDEF,SABED,SABEF,SADEB,SADEF,SDABC,SDABE)
(SDEF,SABED,SABEF,SADEB,SADEF,SDABC,SDABE,SDEB,SDEF)
(SABED,SABEF,SADEB,SADEF,SDABC,SDABE,SDEB,SDEF,SDEFG)
搜索到路徑： S -- D--E--F--G
方法對比：
1 時(shí)間復(fù)雜度：
DFS和BFS的時(shí)間復(fù)雜度是一樣的用狱，假設(shè)有b個(gè)節(jié)點(diǎn)，一共有d層深度
那么時(shí)間復(fù)雜度為O()
2 空間復(fù)雜度：
BFS的空間復(fù)雜度和時(shí)間復(fù)雜度一樣
DFS的空間復(fù)雜度為O（b*d）
python算法實(shí)現(xiàn)：
Note：對于python實(shí)現(xiàn)來說拼弃，深度優(yōu)先搜索和廣度優(yōu)先搜索的不同只是循環(huán)中對于列表的賦值前后的不同
