圖形結(jié)構(gòu)，是樹形結(jié)構(gòu)的擴(kuò)展。

我們?cè)诨厮莘ɡ锩媪私獾綆追N結(jié)構(gòu)：二叉樹，排列樹，完全n叉樹，這幾種解空間類型，都可以直接使用回溯法的框架解決。

二叉樹，排列樹，完全n叉樹，都可以看成x叉樹的變形，而圖形結(jié)構(gòu)就是x叉樹。

在此之前，我們先明白一點(diǎn)：一顆二叉樹是什么，他是某一顆二叉樹的子樹，同樣的道理，一個(gè)圖是什么，他是某個(gè)圖的子圖。

一般的二叉樹問題，我們先處理當(dāng)前結(jié)點(diǎn)，再處理左子樹和右子樹，對(duì)應(yīng)一般的圖的問題，我們先處理當(dāng)前頂點(diǎn)，再依次處理各個(gè)子圖。

在回溯法里，都是看成解空間的深入，對(duì)應(yīng)這里的就是子問題的逐步變小，回溯法使用條件是：解空間滿足多米諾性質(zhì)，也就是部分解不滿足最終解，部分解后面的解也就不滿足最終解，子問題的逐步縮小也是滿足多米諾性質(zhì)的。

圖的寬度優(yōu)先遍歷，和限界分支法類似，應(yīng)該可以使用基于隊(duì)列方式或者優(yōu)先級(jí)隊(duì)列的方式，因?yàn)閳D是一般形式的x叉樹，每一層的叉不知道幾個(gè)，都是借助于標(biāo)記來判斷是否完全遍歷的，注意標(biāo)記visited的用法。

又思考了一下，為什么圖會(huì)使用標(biāo)記visited，其本質(zhì)是：一個(gè)圖分解成：當(dāng)前頂點(diǎn)+相鄰頂點(diǎn)各個(gè)子圖，這種劃分是分治，但是劃分的子問題有重疊，子問題多且相互不獨(dú)立時(shí)，使用動(dòng)態(tài)規(guī)劃編程時(shí)使用備忘模型，一般使用標(biāo)記數(shù)組避免重復(fù)計(jì)算子問題。

# 圖的定義，鄰接表，使用字典的方式，用于演示，比較直觀g = {'A':{'B':1,'C':2},'B':{'A':1,'C':3,'D':4},'C':{'A':2,'B':3,'D':5,'E':6},'D':{'B':4,'C':5,'E':7,'F':8},'E':{'C':6,'D':7,'G':9},'F':{'D':8},'G':{'E':9}} # 圖的遍歷，寬度優(yōu)先，也就是從起點(diǎn)開始，一層一層掃描，需要使用隊(duì)列數(shù)據(jù)結(jié)構(gòu) # 同時(shí)圖的遍歷，不同于樹的遍歷，樹的結(jié)構(gòu)確定了，而圖點(diǎn)和點(diǎn)的相連情況無法提前確定 # 搜索時(shí)，需要標(biāo)記已掃描的點(diǎn)，避免重復(fù)掃描def BFS(graph,start_vertex):# 初始化隊(duì)列，把起點(diǎn)放入隊(duì)列queue =[start_vertex,]# 我們還需要定義一個(gè)數(shù)組記錄已訪問的頂點(diǎn)，一般使用哈希表，每次查找時(shí)間復(fù)雜度O(1)visited = set()# 記錄遍歷的結(jié)果result = []while queue:# 彈出一個(gè)頂點(diǎn)current_vertex = queue.pop(0)# 假如該節(jié)點(diǎn)沒有訪問過，就訪問它，并標(biāo)記已訪問if current_vertex not in visited:result.append(current_vertex)visited.add(current_vertex)# 下面就需要訪問這個(gè)結(jié)點(diǎn)的鄰接頂點(diǎn)for neighbour_vertex in graph[current_vertex].keys():# 把鄰接頂點(diǎn)放入隊(duì)列，放入之前可以判斷一下，是否已經(jīng)訪問過 # if neighbour_vertex not in visited:queue.append(neighbour_vertex)return result# 這里面判斷結(jié)點(diǎn)是否訪問過，在彈出的時(shí)候判斷，可以改進(jìn)一下，也就是在入隊(duì)的時(shí)候 # 就標(biāo)記成已訪問的頂點(diǎn)，也就是重復(fù)的結(jié)點(diǎn)不會(huì)入棧 def BFS2(graph,start_vertex):queue = [start_vertex,]# 入棧就標(biāo)記已訪問visited = set()visited.add(start_vertex)# 用于記錄訪問的結(jié)點(diǎn)順序result =[]while queue:current_vertex = queue.pop(0)result.append(current_vertex)for neighbour_vertex in graph[current_vertex].keys():if neighbour_vertex not in visited:queue.append(neighbour_vertex)visited.add(neighbour_vertex)return result

圖的深度優(yōu)先遍歷：

# 這里面也需要注意標(biāo)記的用法，我們?cè)谑裁磿r(shí)候標(biāo)記頂點(diǎn)已經(jīng)被訪問了 # 第一次訪問頂點(diǎn)的時(shí)候，還是打印結(jié)點(diǎn)結(jié)束也就是最后一次訪問結(jié)點(diǎn)的時(shí)候 # 一般情況下我們習(xí)慣在在一個(gè)結(jié)點(diǎn)確定訪問完畢也就是最后訪問結(jié)點(diǎn)的時(shí)候，標(biāo)記結(jié)點(diǎn)已訪問 # 實(shí)際操作的效率高的是，在我們第一次碰見頂點(diǎn)的時(shí)候就標(biāo)記結(jié)點(diǎn)，因?yàn)榈谝淮闻鲆娝痛?/span> # 處理他已經(jīng)開始了 # BFS在入隊(duì)列的時(shí)候，標(biāo)記已訪問，這樣重復(fù)的結(jié)點(diǎn)就不會(huì)入隊(duì)列 # DFS在進(jìn)入遞歸前，標(biāo)記頂點(diǎn)已訪問，這樣重復(fù)結(jié)點(diǎn)就不會(huì)進(jìn)入遞歸 # DFS的遞歸，把原問題看成：當(dāng)前頂點(diǎn)+ 所有相鄰頂點(diǎn)為起點(diǎn)子圖的子問題 # 為什么不是當(dāng)前頂點(diǎn)+ 一個(gè)相鄰頂點(diǎn)為起點(diǎn)子圖的子問題？想一下你要處理的是當(dāng)前頂點(diǎn)+ # 剩余n-1個(gè)頂點(diǎn)構(gòu)成的子圖，這個(gè)子圖可能是好幾個(gè)分離的圖。 def DFS(graph,start_vertex): def DFSRecursion(graph,start_vertex,visited): result.append(start_vertex) # 遍歷訪問子圖集，訪問前先判斷是否已訪問，未訪問標(biāo)記已訪問，然后進(jìn)入子圖處理for neighbour_vertex in graph[start_vertex].keys():if neighbour_vertex not in visited:visited.add(neighbour_vertex)DFSRecursion(graph,neighbour_vertex,visited)result =[] visited = set()# 在進(jìn)入遞歸前，把頂點(diǎn)標(biāo)記為已訪問visited.add(start_vertex) DFSRecursion(graph,start_vertex,visited)return result# 深度優(yōu)先遍歷，明顯需要用到棧的數(shù)據(jù)結(jié)構(gòu) # 一個(gè)圖的處理，分為兩個(gè)大部分，當(dāng)前頂點(diǎn)處理 + 所有子圖的處理， # 所以這個(gè)問題的結(jié)構(gòu)是n叉樹， # 可以參考，回溯法處理（基于深度優(yōu)先的回溯法，在那里使用迭代的方法比較少）， # 或者參考二叉樹的處理，先序遍歷，先訪問頂點(diǎn)，再左子樹，后訪問右子樹，逆序放入棧中 # 那么對(duì)應(yīng)圖的先序遍歷，先訪問頂點(diǎn)，在訪問各個(gè)子圖，只要把他們逆序放入棧中就行了 # 同理放入棧中前，先標(biāo)記頂點(diǎn)已訪問 def DFS2(graph,start_vertex):visited = set()# 在入棧之前需要先看是否已標(biāo)記，未標(biāo)記標(biāo)記之后放入棧中visited.add(start_vertex)stack =[start_vertex,]result = []while stack:current_vertex = stack.pop()# 處理當(dāng)前結(jié)點(diǎn)result.append(current_vertex)# 處理子圖子問題for neighbour_vertex in graph[current_vertex].keys(): # 子問題入棧前需要判斷是否已標(biāo)記，未標(biāo)記標(biāo)記之后放入棧中if neighbour_vertex not in visited:visited.add(neighbour_vertex)stack.append(neighbour_vertex)return result

測(cè)試結(jié)果：

print(BFS(g,'A')) print(BFS2(g,'A')) print(DFS(g,'A')) print(DFS2(g,'A'))runfile('D:/share/test/graph.py', wdir='D:/share/test') ['A', 'B', 'C', 'D', 'E', 'F', 'G'] ['A', 'B', 'C', 'D', 'E', 'F', 'G'] ['A', 'B', 'C', 'D', 'E', 'G', 'F'] ['A', 'C', 'E', 'G', 'D', 'F', 'B']

不要認(rèn)為深度優(yōu)先遍歷的遞歸方式和迭代方式結(jié)果不一樣，假如需要一樣，那迭代棧實(shí)現(xiàn)方式就需要逆序放入棧。

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的图形结构：遍历模型，分治法，动态规划，回溯法，BFS，DFS的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。