Question

Python: Complete the function create_bfs_graph using python. Do not use any libraries

def create_bfs_graph():
"""
Initializes the undirected graph from the lecture
  
Uses the add_edge method
  
Returns Graph object of the lecture graph
Example use:
>>> ex_graph = create_bfs_graph()
>>> [x in ex_graph.children_of('Jared') for x in ['John', 'Helena', 'Donald', 'Paul']]
[False, False, True, True]
>>> ex_graph = create_bfs_graph()
>>> [x in ex_graph.children_of('Helena') for x in ['John', 'Helena', 'Donald', 'Paul']]
[True, False, False, True]
"""
# DON'T CHANGE ANYTHING ABOVE
# YOUR CODE BELOW
g = Graph()
g.add_edge('John', 'Helena')
g.add_edge('John', 'Chris')
g.add_edge('Helena', 'Chris')
g.add_edge('Helena', 'Paul')

return g

# use this method as reference:

Class Digraph – (directed graph) methods:

__init__: creates a new (empty) Digraph

add_node(node): adds a node

add_edge(edge): adds an edge

children_of(node): returns all edges from node

has_node(node): returns True if it is in the graph, False otherwise

__str__: returns a string with all the edges of the graph

Class Graph(Digraph) – undirected graph:

add_edge(edge): adds an edge and its reverse edge to the graph

Example of object inheritance: Graph does everything that Digraph except the add_edge method is different

Answer 1

graph = {

  'A' : ['B','C'],

  'B' : ['D', 'E'],

  'C' : ['F'],

  'D' : [],

  'E' : ['F'],

  'F' : []

}

visited = [] # List to keep track of visited nodes.

queue = []     #Initialize a queue

def bfs(visited, graph, node):

  visited.append(node)

  queue.append(node)

  while queue:

    s = queue.pop(0)

    print (s, end = " ")

    for neighbour in graph[s]:

      if neighbour not in visited:

        visited.append(neighbour)

        queue.append(neighbour)

# Driver Code

bfs(visited, graph, 'A')