#BFS-Romania-Map-Problem from queue import Queue romaniaMap = { 'Arad': ['Sibiu', 'Zerind', 'Timisoara'], 'Zerind': ['Arad', 'Oradea'], 'Oradea': ['Zerind', 'Sibiu'], 'Sibiu': ['Arad', 'Oradea', 'Fagaras', 'Rimnicu'], 'Timisoara': ['Arad', 'Lugoj'], 'Lugoj': ['Timisoara', 'Mehadia'], 'Mehadia': ['Lugoj', 'Drobeta'], 'Drobeta': ['Mehadia', 'Craiova'], 'Craiova': ['Drobeta', 'Rimnicu', 'Pitesti'], 'Rimnicu': ['Sibiu', 'Craiova', 'Pitesti'], 'Fagaras': ['Sibiu', 'Bucharest'], 'Pitesti': ['Rimnicu', 'Craiova', 'Bucharest'], 'Bucharest': ['Fagaras', 'Pitesti', 'Giurgiu', 'Urziceni'], 'Giurgiu': ['Bucharest'], 'Urziceni': ['Bucharest', 'Vaslui', 'Hirsova'], 'Hirsova': ['Urziceni', 'Eforie'], 'Eforie': ['Hirsova'], 'Vaslui': ['Iasi', 'Urziceni'], 'Iasi': ['Vaslui', 'Neamt'], 'Neamt': ['Iasi'] } def bfs(startingNode, destinationNode): # For keeping track of what we have visited visited = {} # keep track of distance distance = {} # parent node of specific graph parent = {} bfs_traversal_output = [] # BFS is queue based so using 'Queue' from python built-in queue = Queue() # travelling the cities in map for city in romaniaMap.keys(): # since intially no city is visited so there will be nothing in visited list visited[city] = False parent[city] = None distance[city] = -1 # starting from 'Arad' startingCity = startingNode visited[startingCity] = True distance[startingCity] = 0 queue.put(startingCity) while not queue.empty(): u = queue.get() # first element of the queue, here it will be 'arad' bfs_traversal_output.append(u) # explore the adjust cities adj to 'arad' for v in romaniaMap[u]: if not visited[v]: visited[v] = True parent[v] = u distance[v] = distance[u] + 1 queue.put(v) # reaching our destination city i.e 'bucharest' g = destinationNode path = [] while g is not None: path.append(g) g = parent[g] path.reverse() # printing the path to our destination city print(path) # Starting City & Destination City bfs('Arad', 'Bucharest' Check this code and fix the errors

#BFS-Romania-Map-Problem from queue import Queue romaniaMap = { 'Arad': ['Sibiu', 'Zerind', 'Timisoara'], 'Zerind': ['Arad', 'Oradea'], 'Oradea': ['Zerind', 'Sibiu'], 'Sibiu': ['Arad', 'Oradea', 'Fagaras', 'Rimnicu'], 'Timisoara': ['Arad', 'Lugoj'], 'Lugoj': ['Timisoara', 'Mehadia'], 'Mehadia': ['Lugoj', 'Drobeta'], 'Drobeta': ['Mehadia', 'Craiova'], 'Craiova': ['Drobeta', 'Rimnicu', 'Pitesti'], 'Rimnicu': ['Sibiu', 'Craiova', 'Pitesti'], 'Fagaras': ['Sibiu', 'Bucharest'], 'Pitesti': ['Rimnicu', 'Craiova', 'Bucharest'], 'Bucharest': ['Fagaras', 'Pitesti', 'Giurgiu', 'Urziceni'], 'Giurgiu': ['Bucharest'], 'Urziceni': ['Bucharest', 'Vaslui', 'Hirsova'], 'Hirsova': ['Urziceni', 'Eforie'], 'Eforie': ['Hirsova'], 'Vaslui': ['Iasi', 'Urziceni'], 'Iasi': ['Vaslui', 'Neamt'], 'Neamt': ['Iasi'] } def bfs(startingNode, destinationNode): # For keeping track of what we have visited visited = {} # keep track of distance distance = {} # parent node of specific graph parent = {} bfs_traversal_output = [] # BFS is queue based so using 'Queue' from python built-in queue = Queue() # travelling the cities in map for city in romaniaMap.keys(): # since intially no city is visited so there will be nothing in visited list visited[city] = False parent[city] = None distance[city] = -1 # starting from 'Arad' startingCity = startingNode visited[startingCity] = True distance[startingCity] = 0 queue.put(startingCity) while not queue.empty(): u = queue.get() # first element of the queue, here it will be 'arad' bfs_traversal_output.append(u) # explore the adjust cities adj to 'arad' for v in romaniaMap[u]: if not visited[v]: visited[v] = True parent[v] = u distance[v] = distance[u] + 1 queue.put(v) # reaching our destination city i.e 'bucharest' g = destinationNode path = [] while g is not None: path.append(g) g = parent[g] path.reverse() # printing the path to our destination city print(path) # Starting City & Destination City bfs('Arad', 'Bucharest' Check this code and fix the errors

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

#BFS-Romania-Map-Problem

from queue import Queue

romaniaMap = {

'Arad': ['Sibiu', 'Zerind', 'Timisoara'],

'Zerind': ['Arad', 'Oradea'],

'Oradea': ['Zerind', 'Sibiu'],

'Sibiu': ['Arad', 'Oradea', 'Fagaras', 'Rimnicu'],

'Timisoara': ['Arad', 'Lugoj'],

'Lugoj': ['Timisoara', 'Mehadia'],

'Mehadia': ['Lugoj', 'Drobeta'],

'Drobeta': ['Mehadia', 'Craiova'],

'Craiova': ['Drobeta', 'Rimnicu', 'Pitesti'],

'Rimnicu': ['Sibiu', 'Craiova', 'Pitesti'],

'Fagaras': ['Sibiu', 'Bucharest'],

'Pitesti': ['Rimnicu', 'Craiova', 'Bucharest'],

'Bucharest': ['Fagaras', 'Pitesti', 'Giurgiu', 'Urziceni'],

'Giurgiu': ['Bucharest'],

'Urziceni': ['Bucharest', 'Vaslui', 'Hirsova'],

'Hirsova': ['Urziceni', 'Eforie'],

'Eforie': ['Hirsova'],

'Vaslui': ['Iasi', 'Urziceni'],

'Iasi': ['Vaslui', 'Neamt'],

'Neamt': ['Iasi']

}

def bfs(startingNode, destinationNode):

# For keeping track of what we have visited

visited = {}

# keep track of distance

distance = {}

# parent node of specific graph

parent = {}

bfs_traversal_output = []

# BFS is queue based so using 'Queue' from python built-in

queue = Queue()

# travelling the cities in map

for city in romaniaMap.keys():

# since intially no city is visited so there will be nothing in visited list

visited[city] = False

parent[city] = None

distance[city] = -1

# starting from 'Arad'

startingCity = startingNode

visited[startingCity] = True

distance[startingCity] = 0

queue.put(startingCity)

while not queue.empty():

u = queue.get() # first element of the queue, here it will be 'arad'

bfs_traversal_output.append(u)

# explore the adjust cities adj to 'arad'

for v in romaniaMap[u]:

if not visited[v]:

visited[v] = True

parent[v] = u

distance[v] = distance[u] + 1

queue.put(v)

# reaching our destination city i.e 'bucharest'

g = destinationNode

path = []

while g is not None:

path.append(g)

g = parent[g]

path.reverse()

# printing the path to our destination city

print(path)

# Starting City & Destination City

bfs('Arad', 'Bucharest'

Check this code and fix the errors

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 2 images

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.