快捷導(dǎo)航

python深度優(yōu)先搜索和廣度優(yōu)先搜索

更新時(shí)間：2018年02月07日 10:50:55 作者：chuangshishen0

這篇文章主要介紹了python實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索相關(guān)知識(shí)點(diǎn)，對(duì)此有興趣的朋友學(xué)習(xí)下。

1. 深度優(yōu)先搜索介紹

圖的深度優(yōu)先搜索(Depth First Search)，和樹的先序遍歷比較類似。

它的思想：假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)均未被訪問，則從某個(gè)頂點(diǎn)v出發(fā)，首先訪問該頂點(diǎn)，然后依次從它的各個(gè)未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。若此時(shí)尚有其他頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。

顯然，深度優(yōu)先搜索是一個(gè)遞歸的過程。

2. 廣度優(yōu)先搜索介紹

廣度優(yōu)先搜索算法(Breadth First Search)，又稱為"寬度優(yōu)先搜索"或"橫向優(yōu)先搜索"，簡稱BFS。

它的思想是：從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使得“先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問，則需要另選一個(gè)未曾被訪問過的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。

換句話說，廣度優(yōu)先搜索遍歷圖的過程是以v為起點(diǎn)，由近至遠(yuǎn)，依次訪問和v有路徑相通且路徑長度為1,2...的頂點(diǎn)。

# -*- coding: utf-8 -*-
"""
Created on Wed Sep 27 00:41:25 2017
@author: my
"""
from collections import OrderedDict
class graph:
 nodes=OrderedDict({})#有序字典
 def toString(self):
 for key in self.nodes:
 print key+'鄰接點(diǎn)為'+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=adj
g=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 '深度優(yōu)先遍歷的結(jié)構(gòu)為'
g.dfs('c')
print '廣度優(yōu)先遍歷的結(jié)構(gòu)為'
g.bfs('c')

您可能感興趣的文章: