Scribd
Upload
7 views1 page

SVAI3 New

The document contains Python code implementing Selection Sort and Prim's Algorithm. The Selection Sort function sorts an array, while the Prim function calculates the Minimum Spanning Tree of a given graph. The output shows the sorted array and the edges of the Minimum Spanning Tree.

Uploaded by

uldesoleha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views1 page

SVAI3 New

The document contains Python code implementing Selection Sort and Prim's Algorithm. The Selection Sort function sorts an array, while the Prim function calculates the Minimum Spanning Tree of a given graph. The output shows the sorted array and the edges of the Minimum Spanning Tree.

Uploaded by

uldesoleha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

4/8/25, 11:54 AM ai3

Name: Shaikh Aman


Roll No.: COTB72
In [1]: # ------------------- Selection Sort -------------------
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr

a1 = [20, 10, 5, 7, 9, 13]


print("Sorted Array:", selection_sort(a1))

# ------------------- Prim's Algorithm -------------------


import heapq

def prim(graph, start):


mst = []
visited = set([start])
edges = [(cost, start, to) for to, cost in graph[start].items()]
heapq.heapify(edges)

while edges:
cost, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst.append((frm, to, cost))

for to_next, cost2 in graph[to].items():


if to_next not in visited:
heapq.heappush(edges, (cost2, to, to_next))

return mst

graph = {
'A': {'B': 2, 'C': 3},
'B': {'A': 2, 'C': 1, 'D': 1},
'C': {'A': 3, 'B': 1, 'D': 4},
'D': {'B': 1, 'C': 4}
}

print("Minimum Spanning Tree:", prim(graph, 'A'))

Sorted Array: [5, 7, 9, 10, 13, 20]


Minimum Spanning Tree: [('A', 'B', 2), ('B', 'C', 1), ('B', 'D', 1)]

file:///C:/Users/onkar/OneDrive/Desktop/ai3.html 1/1

You might also like