Source code for tryalgo.bfs
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Breadth-first search (bfs)
christoph dürr - jill-jênn vie - 2015-2019, 2023
"""
# snip{
from collections import deque
[docs]
def bfs(graph, start=0):
"""Shortest path in unweighted graph by BFS
:param graph: directed graph in listlist or listdict format
:param int start: source vertex
:returns: distance table, precedence table
:complexity: `O(|V|+|E|)`
"""
to_visit = deque()
dist = [float('inf')] * len(graph)
prec = [None] * len(graph)
dist[start] = 0
to_visit.appendleft(start)
while to_visit: # an empty queue is considered False
node = to_visit.pop()
for neighbor in graph[node]:
if dist[neighbor] == float('inf'):
dist[neighbor] = dist[node] + 1
prec[neighbor] = node
to_visit.appendleft(neighbor)
return dist, prec
# snip}
[docs]
def bfs_implicit(graph, start, end):
"""Shortest path by BFS in an implicitly directed graph
:param graph: function mapping a given vertex to
an iterator over the neighboring vertices
:param start: source vertex
:param end: target vertex
:returns: list of vertices of a shortest path or None
:complexity: `O(|V|+|E|)`
"""
to_visit = deque()
prec = {start: None} # predecessor on shortest path
to_visit.appendleft(start)
while to_visit:
node = to_visit.pop()
for neighbor in graph(node):
if neighbor not in prec: # not yet discovered
prec[neighbor] = node
to_visit.appendleft(neighbor)
if end in prec:
# solution found
L = [end] # backtrack the shortest path
while prec[L[-1]] is not None:
L.append(prec[L[-1]])
return L[::-1] # return in start to end order
return None