Define a function breadthFirst, which performs a breadth-first traversal on a graph, given a start vertex. This function should return a list of the labels of the vertices in the order in which they are visited. Test the function thoroughly with the case study program.(In Python with comments) Use this template: class Vertex: def __init__(self, label): self.label = label self.neighbors = [] def __str__(self): return self.label def add_neighbor(self, neighbor): self.neighbors.append(neighbor) self.neighbors.sort() # Graph definition provided, please don't modify any of the provided code # Add any helper methods if necessary class Graph: def __init__(self): self.vertices = [] # Add a vertex object def add_vertex(self, vertex): self.vertices.append(vertex) # Get index of a vertex with corresponding label # Return -1 if not found def get_vertex_index(self, label): index = 0 for vertex in self.vertices: if label == str(vertex):
Define a function breadthFirst, which performs a breadth-first traversal on a graph, given a start vertex. This function should return a list of the labels of the vertices in the order in which they are visited. Test the function thoroughly with the case study program.(In Python with comments)
Use this template:
class Vertex:
def __init__(self, label):
self.label = label
self.neighbors = []
def __str__(self):
return self.label
def add_neighbor(self, neighbor):
self.neighbors.append(neighbor)
self.neighbors.sort()
# Graph definition provided, please don't modify any of the provided code
# Add any helper methods if necessary
class Graph:
def __init__(self):
self.vertices = []
# Add a vertex object
def add_vertex(self, vertex):
self.vertices.append(vertex)
# Get index of a vertex with corresponding label
# Return -1 if not found
def get_vertex_index(self, label):
index = 0
for vertex in self.vertices:
if label == str(vertex):
return index
index += 1
return -1
# Find a vertex with corresponding label and return as Vertex object
def find_vertex(self, label):
for vertex in self.vertices:
if label == str(vertex):
return vertex
return None
# Add an edge from a vertex with from_label to a vertex with to_label
# These vertices must already exist in the graph
def add_edge(self, from_label, to_label):
source_vertex = self.find_vertex(from_label)
dest_vertex = self.find_vertex(to_label)
if source_vertex is not None and dest_vertex is not None:
source_vertex.add_neighbor(to_label)
# Perform breadth-first search on a directed graph g starting at vertex with label start_label
# Return a list of vertices' name in the order in which they are visited
# Remove the "pass" statement and implement the function
def breadthFirst(g, start_label):
pass
if __name__ == "__main__":
# TODO: (Optional) your test code here
my_graph = Graph()
vertices = ["0", "1", "2", "3", "4", "5"]
edges = [["0", "1"], ["0", "2"], ["1", "3"], ["1", "4"], ["2", "5"]]
for vertex in vertices:
my_graph.add_vertex(Vertex(vertex))
for edge in edges:
my_graph.add_edge(edge[0], edge[1])
for vertex in my_graph.vertices: # Print out adjacency list
print("Vertex " , vertex, ":", vertex.neighbors)
print(breadthFirst(my_graph, "0")) # Correct Output: ["0","1","2","3","4","5"]
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 3 images
