2019-07-20

图的遍历

使用邻接表存储图。

支持bfs,dfs,获取从指定节点到目的节点的bfs路径，dfs路径。

from collections import deque

class Graph:
def init(self, n):
self._n = n
self._e = [set() for _ in range(n)]

def add_edge(self, start, end):  
    self._e[start].add(end)  
    self._e[end].add(start)  

def __str__(self):  
    graph=''

for v in range(self._n):
graph += ‘%d ‘%v
for e in self._e[v]:
graph += ‘–>%d’ % e
graph += ‘rn’
return graph

def bfs(self):  
    bfs_order = ''

q = deque()
seen = set()
paths = [-1 for _ in range(self._n)]
for v in range(self._n):
if v not in seen:
q.append(v)
while q:
n = q.popleft()
if n not in seen:
bfs_order+=’–>%d’ % n
seen.add(n)
for e in self._e[n]:
q.append(e)
if paths[e] == -1 and e not in seen:
paths[e] = n
return bfs_order

def bfs_path(self, start, node):  
    paths = [-1 for _ in range(self._n)]  
    seen = set()  
    q = deque()  
    q.append(start)  
    while q:  
        n = q.popleft()  
        if n not in seen:  
            seen.add(n)  
            if n == node:  
                break

for e in self._e[n]:
q.append(e)
if paths[e] == -1 and e not in seen:
paths[e] = n

    end = node  
    path = [end]  
    while paths[end] != -1:  
        path.append(paths[end])  
        end = paths[end]  
    path.reverse()  
    return path

if name == “main“:
g = Graph(8)
g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,2)
g.add_edge(1,3)
g.add_edge(2,3)
g.add_edge(3,4)
g.add_edge(4,5)
g.add_edge(6,7)
print(g)
print(g.bfs())
print(g.bfs_path(2, 5)