In this programming exercise you will implement two functions. The first function will prompt the user for a file containing the number of vertices and entries of the adjacency matrix of a graph. It will return a two-dimensional list (a list of lists) containing the adjacency matrix.The second function will take as input the a two-dimensional list that represents the adjacency matrix of a graph, runs Prim's algorithm, and returns the list of edges in a minimal spanning tree and the total weight of the spanning tree.I have figured out the first part of the program. i need help with the second part. Thankstext file 80 1 2 3 100 100 100 1001 0 2 100 3 4 100 1002 2 0 4 4 100 5 1003 100 4 0 100 100 4 100100 3 4 100 0 3 3 3100 4 100 100 3 0 100 1100 100 5 4 3 100 0 2100 100 100 100 3 1 2 0 def readMatrix(inputfilename):Returns a two-dimentional array created from the data in the given file.Pre: 'inputfilename' is the name of a text file whose first row contains thenumber of vertices in a graph and whose subsequent rows contain the rows ofthe adjacency matrix of the graph.# Open the fileopen (inputfilename, 'r')f%3D# Read the number of vertices from the first line of the fileint((f.readline().strip()))n =# Read the rest of the file stripping off the newline characters and splitting it into# a list of intger valuesrest =f.read().strip().split()# Create the adjacency matrixadjMat = []adjr=[]k=[]#putting 8-8 at a time in a listt=0for i in range (n):k.append(rest[t:t + n])t+= nfor i in k:adjr=[]for b in i:adjr.append(int(b)) #adding the element to a sublist adjradjMat.append (adjr)# adding the sublist of adjr to adjmat so the rows of the matrix can be created#Return the matrixreturn adjMatTest your function.testFile = input("Enter the name of the input file")Enter the name of the input fileinputfilename.txtFinihs the implementation of Prim's algorithm.graphMatrix = readMatrix(testfile)graphMatrix[[0, 1, 2, 3, 100, 100, 100, 100],[1, е, 2, 100, 3, 4, 100, 100],[2, 2, 0, 4, 4, 100, 5, 100],[3, 100, 4, в, 100, 100, 4, 100],[100, 3, 4, 100, 0, 3, 3, 3],[100, 4, 100, 100, 3, 0, 100, 1],[100, 100, 5, 4, 3, 100, в, 2],[100, 100, 100, 100, 3, 1, 2, 0]] def Prim(m):Runs Prim's algorithm on the graph G with adjacency matrix 'm'.POST: The list of edges in a minimum spanning tree of G and the total weightof the spanning tree has been returned.PRE:'m' is the adjacency matrix of a connected graph.# Initialize dictionaries to hold the nearest and distance vectorsn = len(m) # the number of vertices is equal to the number of rows in the matrix%3Ddistance = {}for i in range(1,n):distance[i] = m[@][i]{}nearest =for i in range (1,n):nearest[i] = 0# Implement Prim's algorithm...# Create the list of edges and calculate the total weight...return list_of_edges, weightTest your implementation.edgelist, totalweight = Prim(graphMatrix)print(f'The list of edges in the spanning tree is: {edgelist}')print(f'The total weight of the spanning tree is: {totalweight}')

I am implementing the prim's algorithm part of this code, which will help you out. The…

Answered: The second function will take as input…

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

In this programming exercise you will implement two functions. The first function will prompt the user for a file containing the number of vertices and entries of the adjacency matrix of a graph. It will return a two-dimensional list (a list of lists) containing the adjacency matrix.

The second function will take as input the a two-dimensional list that represents the adjacency matrix of a graph, runs Prim's algorithm, and returns the list of edges in a minimal spanning tree and the total weight of the spanning tree.

I have figured out the first part of the program. i need help with the second part. Thanks

text file

8
0 1 2 3 100 100 100 100
1 0 2 100 3 4 100 100
2 2 0 4 4 100 5 100
3 100 4 0 100 100 4 100
100 3 4 100 0 3 3 3
100 4 100 100 3 0 100 1
100 100 5 4 3 100 0 2
100 100 100 100 3 1 2 0

def readMatrix(inputfilename):
Returns a two-dimentional array created from the data in the given file.
Pre: 'inputfilename' is the name of a text file whose first row contains the
number of vertices in a graph and whose subsequent rows contain the rows of
the adjacency matrix of the graph.
# Open the file
open (inputfilename, 'r')
f
%3D
# Read the number of vertices from the first line of the file
int((f.readline().strip()))
n =
# Read the rest of the file stripping off the newline characters and splitting it into
# a list of intger values
rest =
f.read().strip().split()
# Create the adjacency matrix
adjMat = []
adjr=[]
k=[]
#putting 8-8 at a time in a list
t=0
for i in range (n):
k.append(rest[t:t + n])
t+= n
for i in k:
adjr=[]
for b in i:
adjr.append(int(b)) #adding the element to a sublist adjr
adjMat.append (adjr)# adding the sublist of adjr to adjmat so the rows of the matrix can be created
#Return the matrix
return adjMat
Test your function.
testFile = input("Enter the name of the input file")
Enter the name of the input fileinputfilename.txt
Finihs the implementation of Prim's algorithm.
graphMatrix = readMatrix(testfile)
graphMatrix
[[0, 1, 2, 3, 100, 100, 100, 100],
[1, е, 2, 100, 3, 4, 100, 100],
[2, 2, 0, 4, 4, 100, 5, 100],
[3, 100, 4, в, 100, 100, 4, 100],
[100, 3, 4, 100, 0, 3, 3, 3],
[100, 4, 100, 100, 3, 0, 100, 1],
[100, 100, 5, 4, 3, 100, в, 2],
[100, 100, 100, 100, 3, 1, 2, 0]]

def Prim(m):
Runs Prim's algorithm on the graph G with adjacency matrix 'm'.
POST: The list of edges in a minimum spanning tree of G and the total weight
of the spanning tree has been returned.
PRE:
'm' is the adjacency matrix of a connected graph.
# Initialize dictionaries to hold the nearest and distance vectors
n = len(m) # the number of vertices is equal to the number of rows in the matrix
%3D
distance = {}
for i in range(1,n):
distance[i] = m[@][i]
{}
nearest =
for i in range (1,n):
nearest[i] = 0
# Implement Prim's algorithm
...
# Create the list of edges and calculate the total weight
...
return list_of_edges, weight
Test your implementation.
edgelist, totalweight = Prim(graphMatrix)
print(f'The list of edges in the spanning tree is: {edgelist}')
print(f'The total weight of the spanning tree is: {totalweight}')

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

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.

Similar questions