計算與人工智能概論第5章算法思維第四節(jié)DFS與BFS

深度優(yōu)先遍歷

DFS1PART深度優(yōu)先遍歷（DeepFirstSearch），簡稱DFS，是一種用于在樹型結(jié)構(gòu)（樹，tree）或網(wǎng)狀結(jié)構(gòu)（圖，graph）中進行搜索的有效算法。什么是DFS樹是由結(jié)點和邊組成的不存在任何環(huán)的一種數(shù)據(jù)結(jié)構(gòu)。一棵樹可以看成由根結(jié)點和子樹構(gòu)成，因此，樹具有天然的遞歸結(jié)構(gòu)。沒有結(jié)點的樹稱為空樹。假設(shè)某個班有10位同學(xué)，李明是班長，班級下面有3個小組，小組長分別為張華、馬芳和趙杰，每個小組又包含若干同學(xué)，對于這種結(jié)構(gòu)，我們可以用一顆樹來進行表達樹（tree）這顆樹可分解為如下4個部分，其中，子樹又可以繼續(xù)分解下去。根結(jié)點李明以張華為根結(jié)點的子樹以馬芳為根結(jié)點的子樹以趙杰為根結(jié)點的子樹樹的分解可以用Python語言的嵌套列表來表達這顆樹，一顆樹由根結(jié)點以及各個子樹構(gòu)成，子樹的結(jié)構(gòu)和原樹相同：tree=['李明',#根節(jié)點['張華',['朱麗'],['王曉']],#子樹1['馬芳',['李欣']],#子樹2['趙杰',['劉密'],['馬津'],['陳希']]#子樹3]樹的表達如果要求輸出班級中所有同學(xué)的姓名，需要對整顆樹進行遍歷，訪問每個節(jié)點。對一顆樹進行遍歷的方法有兩大類，一類是深度優(yōu)先遍歷（DeepFirstSearch，DFS），另一類是廣度優(yōu)先遍歷（BreadthFirstSearch，BFS）。樹的遍歷沿著樹的邊一直往下走，直到最底層的某個葉子結(jié)點，然后再往回走，從枝椏處繼續(xù)往下走，一直這樣下去，直到將所有的節(jié)點都訪問一次?？梢园凑諛涞姆纸夥绞揭来卧L問這顆樹的不同部分，其中子樹的訪問方式和原樹一樣，以遞歸的方式進行訪問：訪問根結(jié)點訪問以張華為根結(jié)點的子樹訪問以馬芳為根結(jié)點的子樹訪問以趙杰為根結(jié)點的子樹樹的DFSdefdfs(tree):forindex,iteminenumerate(tree):ifindex==0:print(item)else:dfs(item)

#遞歸訪問子樹dfs(tree)設(shè)樹中的節(jié)點總數(shù)為n，由于每個節(jié)點都會被訪問且只訪問1次，因此，dfs的時間復(fù)雜度為O(n)。樹的DFS源代碼圖（Graph）是另一種經(jīng)常使用dfs進行搜索的結(jié)構(gòu)。圖由一系列的頂點構(gòu)成，這些頂點之間存在一些連線，稱之為邊，邊可以具有權(quán)重的屬性。

地圖就是一種典型的圖結(jié)構(gòu)，地圖中的地名是頂點，邊是兩個地點之間的路徑，邊的權(quán)重就是路徑的距離（或者通行時間等）。圖（graph）湖南大學(xué)地圖的抽象對湖南大學(xué)地圖進行抽象抽取若干重要地點作為「頂點」將這些地點之間的道路用線條標(biāo)注出來形成「邊」得到右邊的「圖」湖南大學(xué)地圖的抽象假設(shè)有一臺機器人，要設(shè)計一個尋路算法，從天馬公寓出發(fā)，找到一條有效的路徑，最后到達圖書館。可行的路徑：路線1：天馬公寓->五食堂->體育館->圖書館路線2：天馬公寓->五食堂->逸夫樓->東方紅廣場->圖書館路線3：天馬公寓->綜合樓->圖書館路線4：天馬公寓->綜合樓->逸夫樓->東方紅廣場->圖書館路線5：天馬公寓->綜合樓->逸夫樓->五食堂->體育館->圖書館機器人尋路問題用鄰接矩陣來存儲圖的信息，鄰接矩陣是一個表格，表格中標(biāo)注為1的格子表示行和列所示地名之間存在一條直接路徑。圖的表達

天馬公寓綜合樓超算中心逸夫樓東方紅廣場圖書館體育館五食堂天馬公寓

1

1綜合樓1

11

1

超算中心

1

逸夫樓

1

1

1東方紅廣場

1

1

圖書館

1

1

1

體育館

1

1五食堂1

1

1

用Python語言的嵌套列表來表達鄰接矩陣：map=[[0,1,0,0,0,0,0,1], [1,0,1,1,0,1,0,0], [0,1,0,0,0,0,0,0], [0,1,0,0,1,0,0,1], [0,0,0,1,0,1,0,0], [0,1,0,0,1,0,1,0], [0,0,0,0,0,1,0,1], [1,0,0,1,0,0,1,0]]圖的表達天馬公寓、綜合樓、超算中心、逸夫樓、東方紅廣場、圖書館、體育館、五食堂的編號分別為0、1、2...7從天馬公寓到圖書館的尋路問題，轉(zhuǎn)化為從編號0到編號5的尋路問題。地名對應(yīng)的編號可當(dāng)作索引號對map中的元素進行索引，元素值為1表示有一條路徑，為0表示沒有路徑，例如，map[1][0]為1，表示綜合樓和天馬公寓之間有一條路徑。將圖看成一顆特殊的樹，以起點天馬公寓為根結(jié)點，其子節(jié)點是通過邊連接到的各個頂點。由于圖的特性，樹中很多結(jié)點都是重復(fù)的將圖看作樹對圖進行DFS和樹的DFS的基本原理是一樣的，但由于圖存在回路，導(dǎo)致對應(yīng)的樹存在重復(fù)結(jié)點，需要對已訪問過的結(jié)點進行標(biāo)記，遞歸時根據(jù)標(biāo)記避開已經(jīng)訪問過的結(jié)點。訪問根結(jié)點，如果是終點，算法結(jié)束將根結(jié)點的狀態(tài)標(biāo)記為已訪問依次遞歸訪問未訪問過的子樹問題分解機器人位于地點P1時，對所有和P1連接的其他地點進行循環(huán)若某個地點沒有訪問過，就控制機器人走過去，并且標(biāo)記為已訪問對于連接到P1的其他地點，依次進行嘗試如果沒有地方可去了，就退回去，再看看有沒有其他地方可走。路徑選擇路徑選擇源代碼name=['天馬公寓','綜合樓','超算中心','逸夫樓','東方紅廣場','圖書館','體育館','五食堂']visited=[0]*8

#記錄頂點是否訪問path=[]#保存路徑的列表def

dfs(start,end):#返回True表示已找到終點

path.append(name[start])#將頂點加入路徑

visited[start]=1

#標(biāo)記該頂點已訪問

ifstart==end:return

True

fori,xin

enumerate(map[start]):

ifx==1

andvisited[i]==0:

ifdfs(i,end):#對新的未訪問頂點遞歸

return

True

#循環(huán)完，沒有新的路可走，刪除路徑中最后的一個頂點

path.pop()

return

Falsedfs(0,5)#0，5分別是起點和終點的編號print(path)

廣度優(yōu)先遍歷

BFS2PART棧是一種常用的數(shù)據(jù)結(jié)構(gòu)，主要特點是后進先出（LastInFirstOut，LIFO）。例如：把書一本接一本的放到桌上，拿的時候只能先拿上面的。棧（stack）假設(shè)桌面一開始是空的，每次只往桌上放一本書。如此堆疊，便能構(gòu)建出一個棧。取書的順序正好與放書的順序相反，即：元素的插入順序正好與移除順序相反。這就是棧的反轉(zhuǎn)特性。棧的反轉(zhuǎn)特性模塊fromqueueimportLifoQueue定義棧（0表示容量無窮大）stack_=LifoQueue(maxsize=0)

將元素壓入棧頂stack_.put(x)從棧頂彈出元素x=stack_.get()

棧中元素數(shù)目stack_.qsize():實際上，python的棧叫做后進先出隊列，和后面介紹的隊列，擁有完全相同的使用方式。python的棧LifoQueue棧是一種后進先出的數(shù)據(jù)結(jié)構(gòu)，而隊列與之相反，是一種先進先出(FirstInFirstOut，F(xiàn)IFO)的數(shù)據(jù)結(jié)構(gòu)。顧名思義，隊列就是排隊，好比到食堂打飯，排在前面的人先打飯，然后出隊列；新來的人排到隊列的末尾。隊列（queue）模塊fromqueueimportQueue定義隊列（0表示容量無窮大）queue1=Queue(maxsize=0)

將元素追加入隊列末尾queue1.put(x)從隊列的最前面彈出元素x=queue1.get()

隊列中元素數(shù)目queue1.qsize():

python的隊列QueueBFS，即BreadthFirstSearch，所有因為展開節(jié)點而得到的子節(jié)點都會被加進一個先進先出的隊列中，隊列中的元素再以FIFO的順序取出并進行處理。通常，處理過的元素要進行標(biāo)記。廣度優(yōu)先搜索(BFS)給定給定一個M×N的迷宮圖、入口與出口、行走規(guī)則。求一條從指定入口到出口的最短路徑。所求路徑必須是簡單路徑，即路徑不重復(fù)。如有多條最短路徑，優(yōu)先順序為右、下、左、上。為了求解問題的方便，在數(shù)組的周圍加上圍墻，即在周圍加上兩行和兩列。形成M+2行，N+2列的迷宮數(shù)組。迷宮問題解題思路從入口節(jié)點開始，尋找所有下一個能繼續(xù)走的點，根據(jù)下一個的點繼續(xù)尋找所有能走的點，直到該點等于出口。實現(xiàn)方法：創(chuàng)建一個空隊列，將起點位置放入隊列。在隊列不為空的時候循環(huán)：出隊一次。如果當(dāng)前位置為出口，則結(jié)束算法；否則找出當(dāng)前方塊的4個相鄰方塊中可走的方塊（走過的方塊進行標(biāo)記，以后遇到不能再走），加入隊列。迷宮問題解題思路地圖信息保存在嵌套列表中，1表示墻，0表示通道。maze=[[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1],]迷宮問題解題思路如何找到并輸出最短路徑？定義一個列表path，每次從隊列中取出一個位置時，將該位置放入列表；加入隊列的位置信息，除了這個位置的坐標(biāo)之外，額外再記錄該坐標(biāo)上一個位置的坐標(biāo)在列表path中的索引號。到達終點后，從path最后一個元素出發(fā)，沿著上一位置信息，可以溯源到起點；將溯源信息倒著輸出，就是要找的最短路徑。因此，BFS從起點開始一圈圈往外擴，見到終點即結(jié)束遍歷，因此，可以高效地找到最短路徑。迷宮問題maze=[[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1],]dirs=[lambdax,y:(x+1,y),lambdax,y:(x,y+1),lambdax,y:(x-1,y),lambdax,y:(x,y-1),]實現(xiàn)代碼迷宮問題#通過path找到最短路徑defshortest_path(path):shortestpath=[]curNode=path[-1]whilecurNode!=path[0]:shortestpath.append(curNode)curNode=path[curNode[2]]#找到前一個位置

shortestpath.append(path[0])shortestpath.reverse()returnshortestpath迷宮問題defgo_maze(x1,y1,x2,y2):

queue=Queue()

path=[]

queue.put((x1,y1,-1))#起點

maze[y1][x1]=-1#標(biāo)記起點已經(jīng)走過

whilequeue.qsize()>0:

curNode=queue.get()

path.append(curNode)ifcurNode[0]==x2andcurNode[1]==y2:forx,y,_inshortest_path(path):print('%d%d'%(x,y))returnTruefordirindirs:#找四個方向

nextN