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

客官°小女子只卖身不卖艺 2022-05-24 06:50 238阅读 0赞

其实最初的想法是定义一个图类再基于此来实现两种遍历 ，但其实一个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))

print(DFS\_Graph(maps,x),'\\n')

输出结果 基于每个点实现两种遍历

\[0, 1, 2, 5, 6, 3, 4, 7\]  
\[0, 1, 3, 7, 4, 2, 5, 6\]   
  
  
\[1, 0, 3, 4, 7, 2, 5, 6\]  
\[1, 0, 2, 5, 6, 3, 7, 4\]   
  
  
\[2, 0, 5, 6, 1, 3, 4, 7\]  
\[2, 0, 1, 3, 7, 4, 5, 6\]   
  
  
\[3, 1, 7, 4, 0, 2, 5, 6\]  
\[3, 1, 0, 2, 5, 6, 4, 7\]   
  
  
\[4, 1, 7, 3, 0, 2, 5, 6\]  
\[4, 1, 0, 2, 5, 6, 3, 7\]   
  
  
\[5, 2, 6, 0, 1, 3, 4, 7\]  
\[5, 2, 0, 1, 3, 7, 4, 6\]   
  
  
\[6, 2, 5, 0, 1, 3, 4, 7\]  
\[6, 2, 0, 1, 3, 7, 4, 5\]   
  
  
\[7, 3, 4, 1, 0, 2, 5, 6\]  
\[7, 3, 1, 0, 2, 5, 6, 4\]