8. 120 points Program You will implement a suite of graph algorithms including D

Question

8. 120 points Program You will implement a suite of graph algorithms including DFS,The edges (pairs of vertices) that make up a minimum spanning tree of the graph along with the total weight of the MST . A complete list of vertex pairs along with the weight of the shortest path between BFS, MST (either Prim's or Kruskal's) and a minimum weighted-distance finding algo- rithm (either Floyd-Warshall or Dijsktra's). In particular, you will write a program to themi parse an input file (file name should be read from the command line with data repre- senting a weighted undirected graph as follows. The first line is an integer n, the number of vertices in the graph. By convention, vertices will be identified with the integers thru n - 1 inclusive. Each line after that contains two integers and a decimal number delimited by spaces. The first two are the vertices (since it is undirected, nothing should Breadth First Search Traversal: be inferred from their order) and the last is a weight. An example: An example output: 0 Depth First Search Traversal 0. 2. 1. 3. 4 0. 3, 2, 4, 1 Minimum Spanning Tree V [0, 1, 2, 3, 4] Total Weight: 11.90 Shortest Paths 0 2 3.0 0 3 2.1 0 4 4.3 1 2 3.14 1 3 2.5 2 3 3.9 2 4 10.3 Path Weight = 4.6 0-> 2 = (0, 2, 3.0) Path Weight 3.0 Path Weight = 2.1 0-> 4 . (0, 4, 4.3) Path Weight 4.3 |-> 2 = (1, 2, 3.14) Path Weight 3.14 1-) 3 = (1, 3, 2.5) Path Weight: 2.5 (1, Once output statistics associated with it. In particular, your output should display: l your program will run several graph algorithms on the input graph and ·A DFS traversal (visited order of vertices) starting at vertex 0 according to the following strategy: the next vertex should be the least numbered unvisited vertex 3, 2.5) -> (0, 3, 2.1) 8.899999999999999 1-> 4- -) (0, 4, 4.3) Path Weight * A BFS traversal (visited order of vertices) starting at vertex 0 according to the 2->3- (2, 3, 3.9) following strategy: the next vertex should be an unvisited vertex with least edgePath Weight 3.9 Path Weight = 7.3 Path Weight6.4 2-4 (0, 2, 3.0) -> (0. 4, 4.3) weight You may use a library to represent graphs in your language of choice if you wish. You may use basic methods on a graph (such as getting the vertex set or tsting if two vertices are connected, et). However, you may not use any graph algorithms within that library that would make the assignment trivial.

Explanation / Answer

Hello Sir/Madam

Here is the Python Code Which Traverses the any graph in the Given way

import sys
  
def get_breadth_first_nodes(root):
nodes = []
stack = [root]
while stack:
cur_node = stack[0]
stack = stack[1:]
nodes.append(cur_node)
for child in cur_node.get_children():
stack.append(child)
return nodes

def get_depth_first_nodes(root):
nodes = []
stack = [root]
while stack:
cur_node = stack[0]
stack = stack[1:]
nodes.append(cur_node)   
for child in cur_node.get_rev_children():
stack.insert(0, child)
return nodes

class Node(object):
def __init__(self, id_):
self.id = id_
self.children = []
  
def __repr__(self):
return "Node: [%s]" % self.id
  
def add_child(self, node):
self.children.append(node)
  
def get_children(self):
return self.children
  
def get_rev_children(self):
children = self.children[:]
children.reverse()
return children

def println(text):
sys.stdout.write(text + " ")
  
def make_test_tree():
a0 = Node("a0")
b0 = Node("b0")   
b1 = Node("b1")   
b2 = Node("b2")   
c0 = Node("c0")   
c1 = Node("c1")  
d0 = Node("d0")
  
a0.add_child(b0)
a0.add_child(b1)
a0.add_child(b2)
  
b0.add_child(c0)
b0.add_child(c1)
  
c0.add_child(d0)
  
return a0   

def test_breadth_first_nodes():
root = make_test_tree()
node_list = get_breadth_first_nodes(root)
for node in node_list:
println(str(node))

def test_depth_first_nodes():
root = make_test_tree()
node_list = get_depth_first_nodes(root)
for node in node_list:
println(str(node))

if __name__ == "__main__":
test_breadth_first_nodes()
println("")
test_depth_first_nodes()
  

Hope It works and looking forward to help if have any doubts..

Thank You Sir/Madam.

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.