Algorithms/Prims Algorithm/Prims Algorithm.py at ffa201722c57b8b33c479689505d9f73b78e2f4e · Vishal1003/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#prims algorithm
import sys

class Graph:
    def __init__(self,vertices):
        self.vert=vertices
        self.AM=[[0 for i in range(self.vert)]for j in range(self.vert)]
    def addEdge(self,v1,v2,wt):
        self.AM[v1][v2]=wt
        self.AM[v2][v1]=wt

    def getMinVertex(self,visited,weight):
        minVertex=-1
        for i in range(self.vert):
            if visited[i]==False and (minVertex==-1 or weight[minVertex]>weight[i]):
                minVertex=i
        return minVertex

    def prims(self):
        visited=[False for i in range(self.vert)]
        parent=[-1 for i in range(self.vert)]
        weight=[sys.maxsize for i in range(self.vert)]
        weight[0]=0
        for i in range(self.vert-1):
            minVertex=self.getMinVertex(visited,weight)
            visited[minVertex]=True
            for j in range(self.vert):
                if visited[j]==False and self.AM[minVertex][j]>0:
                    if weight[j]>self.AM[minVertex][j]:
                        weight[j]=self.AM[minVertex][j]
                        parent[j]=minVertex
        for i in range(1,self.vert):
            if i<parent[i]:
                print(str(i)+' '+str(parent[i])+' '+str(weight[i]))
            else:
                print(str(parent[i])+' '+str(i)+' '+str(weight[i]))

li=[int(i) for i in input().split()]
n=li[0]
e=li[1]
g=Graph(n)
for i in range(e):
    cur=[int(i) for i in input().split()]
    g.addEdge(cur[0],cur[1],cur[2])
g.prims()