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