圖的深度優先搜索(Depth First Search)，和樹的先序遍歷比較類似。
它的思想：假設初始狀態是圖中所有頂點均未被訪問，則從某個頂點v出發，首先訪問該頂點，然后依次從它的各個未被訪問的鄰接點出發深度優先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到。 若此時尚有其他頂點未被訪問到，則另選一個未被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。
顯然，深度優先搜索是一個遞歸的過程。
廣度優先搜索算法(Breadth First Search)，又稱為"寬度優先搜索"或"橫向優先搜索"，簡稱BFS。
它的思想是：從圖中某頂點v出發，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發依次訪問它們的鄰接點，并使得“先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。如果此時圖中尚有頂點未被訪問，則需要另選一個未曾被訪問過的頂點作為新的起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。
換句話說，廣度優先搜索遍歷圖的過程是以v為起點，由近至遠，依次訪問和v有路徑相通且路徑長度為1,2...的頂點。
# -*- coding: utf-8 -*-"""Created on Wed Sep 27 00:41:25 2017@author: my"""from collections import OrderedDictclass graph: nodes=OrderedDict({})#有序字典 def toString(self): for key in self.nodes: print key+'鄰接點為'+str(self.nodes[key].adj) def add(self,data,adj,tag): n=Node(data,adj) self.nodes[tag]=n for vTag in n.adj: if self.nodes.has_key(vTag) and tag not in self.nodes[vTag].adj: self.nodes[vTag].adj.append(tag) visited=[] def dfs(self,v): if v not in self.visited: self.visited.append(v) print v for adjTag in self.nodes[v].adj: self.dfs(adjTag) visited2=[] def bfs(self,v): queue=[] queue.insert(0,v) self.visited2.append(v) while(len(queue)!=0): top=queue[len(queue)-1] for temp in self.nodes[top].adj: if temp not in self.visited2: self.visited2.append(temp) queue.insert(0,temp) print top queue.pop()class Node: data=0 adj=[] def __init__(self,data,adj): self.data=data self.adj=adjg=graph()g.add(0,['e','c'],'a')g.add(0,['a','g'],'b')g.add(0,['a','e'],'c')g.add(0,['a','f'],'d')g.add(0,['a','c','f'],'e')g.add(0,['d','g','e'],'f')g.add(0,['b','f'],'g')g.toString()print '深度優先遍歷的結構為'g.dfs('c')print '廣度優先遍歷的結構為'g.bfs('c')
新聞熱點
疑難解答
