图的遍历

使用邻接表存储图。

支持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 += '\r\n'
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)
43.6K

发表评论

电子邮件地址不会被公开。