#!/usr/bin/python3
# Implementation of the Breadth-First Search algorithm (BFS) using an
# adjacency-list representation of a graph.
# Graph representation: V(G) = {0,1,2,...,n-1}, The graph is
# represented by an array of arrays G such that G[u]=[v1,v2,...]
# means that the graph contains edges u-->v1, u-->v2, etc.
def bfs(G,src): # G: adjacency list, src: source node
n = len(G) # n: number of nodes in G
D = [None]*n # D[v]: hop-distance from src to v
P = [None]*n # P[v]: previous node: src --> ... u --> v
Q = [None]*n
Q_tail = 0
Q_head = 0
Q[Q_tail] = src # We start the exploration from src
Q_tail = Q_tail + 1 #
D[src] = 0 # src is at distance 0 from itself
P[src] = src # by convention, P[src] is src itself
while Q_tail > Q_head:
u = Q[Q_head] # extract u = head of Q
Q_head = Q_head + 1
for v in G[u]: # for every adjacent node v
if D[v] == None:
D[v] = D[u] + 1
P[v] = u
Q[Q_tail] = v
Q_tail = Q_tail + 1
return P, D # return previous and distance vectors
# We read an undirected graph from the standard input. The input
# contains a sequence of undirected edges. For example:
#
# TI VS
# UR TI
# GR TI
# ...
Adj = [] # adjacency list
Idx = {} # Idx: node name --> node index in Adj
Name = [] # Name[v] is the name of node v
# Utility function to add a node u to the graph. u is the node name.
def add_vertex(u_name):
global Name, Idx, Adj
if u_name in Idx:
u = Idx[u_name]
else:
u = len(Adj)
Idx[u_name] = u
Adj.append([])
Name.append(u_name)
return u
import sys
for line in sys.stdin:
uname, vname = line.strip().split()
u = add_vertex(uname)
v = add_vertex(vname)
Adj[u].append(v)
Adj[v].append(u)
if len(sys.argv) > 1: # read the name of the starting node
src = Idx[sys.argv[1]] # from the first command-line argument,
else: # or start from the first node
src = 0
P,D = bfs(Adj, src)
print('BFS starting from', Name[src])
c = 0
for u in range(len(Adj)):
if D != None:
print(Name[u], D[u], Name[P[u]])
c = c + 1
print('reached',c,'out of',len(Adj),'nodes')