图的广度优先遍历和深度优先遍历-蒲公英云

图的广度优先遍历和深度优先遍历

其实最初的想法是定义一个图类再基于此来实现两种遍历，但其实一个import就可以搞定的事，为了练习决定还是打了一遍，后来发现这种做法真的很二，因为定义一个图类也仅仅只用到了顶点数的传值，以及得到一个顶点出发的出边而已，但是后来觉得完全是自己给自己找麻烦，顶点数直接一个len就ok了，出边通过一个for循环也ok了，单纯就图的遍历来讲没必要，因为定义图类后各种出错，各种累，各种想不到的鬼都出来了。。。

‘’’class Graph(object):

  def \_\_init\_\_(self,maps,unconn=0):  
        vnum=len(maps)  
        self.\_maps=\[maps\[i\]\[:\] for i in range(vnum)\]  
        self.\_unconn=unconn  
        self.\_vnum=vnum  
  def vertex\_num(self):  
        return self.\_vnum  
  def add\_edges(self,x,y,weight):  
        if x<0 or y<0 or x>=self.\_vnum or y>=self.\_vnum or x==y or weight<0:  
              raise ValueError  
        self.\_maps\[x\]\[y\]=self.\_maps\[y\]\[x\]=weight  
  def get\_edge(self,x,y):  
        return self.\_maps\[x\]\[y\]  
  def get\_out\_edges(self,x):  
        return self.\_out\_edges(self.\_maps\[x\],self.\_unconn)  
  @staticmethod  
  def \_out\_edges(row,unconn):  
        edges=\[\]  
        for i in range(len(row)):  
              if self.\_maps\[i\]!=unconn:  
                    edges.append((i, row\[i\]))  
        return edges'''

上面一块是定义的图类，以下完全没用到

‘’’图的深度优先遍历’’’
def DFS_Graph(maps,x): #基于x出发实现的遍历
vnum=len(maps)
res=[]
visited=[False]*vnum
def dfs(i):
res.append(i)
visited[i]=True
for j in range(vnum):
if maps[i][j]>0 and visited[j]==False:
dfs(j)
dfs(x)
for y in range(vnum):
if visited[y]==False:
dfs(y)
return res

‘’’图的广度优先遍历’’’
def BFS_Graph(maps,x):
vnum=len(maps)
res=[]

 queue=\[\]        \#对于广度搜索而言这里queue要理解成一个队列 而不是单纯的list，由于list的强大而实现了队列的功能              visited=\[False\]\*vnum
  def bfs():  
        while len(queue)>0:  
              i=queue.pop()  
              for j in range(vnum):  
                    if maps\[i\]\[j\]>0 and visited\[j\]==False:  
                          res.append(j)  
                          visited\[j\]=True  
                          queue.append(j)  
  if vnum>0:  
        queue.append(x)  
        visited\[x\]=True  
        res.append(x)  
        bfs()  
  for y in range(vnum):  
        if visited\[y\]==False:  
              queue.append(y)  
              visited\[y\]=True  
              res.append(y)  
              bfs()  
  return res

inf=0 #此处不将inf赋值为零就需要对程序中的判断做调整，若直接将inf定义为无穷大程序可以执行但无法得到正确的遍历
maps = [[inf,1,1,inf,inf,inf,inf,inf],
[1,inf,inf,1,1,inf,inf,inf],
[1,inf,inf,inf,inf,1,1,inf],
[inf,1,inf,inf,inf,inf,inf,1],
[inf,1,inf,inf,inf,inf,inf,1],
[inf,inf,1,inf,inf,inf,1,inf],
[inf,inf,1,inf,inf,1,inf,inf],
[inf,inf,inf,1,1,inf,inf,inf]]
for i in range(len(maps)):
x=i
print(BFS_Graph(maps,x))