최소비용신장트리, Prim/Kruskal 파이썬(Python) 소스 코드
- Prim 알고리즘
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586# 출처 : https://coderbyte.com/algorithm/find-minimum-spanning-tree-using-prims-algorithm# create adjacency matrix for use in prims algorithm# note: we could improve the running time of prims algorithm by# implementing a priority queue data structure instead of a matrixdef createAdjMatrix(V, G):adjMatrix = []# create N x N matrix filled with 0 edge weights between all verticesfor i in range(0, V):adjMatrix.append([])for j in range(0, V):adjMatrix[i].append(0)# populate adjacency matrix with correct edge weightsfor i in range(0, len(G)):adjMatrix[G[i][0]][G[i][1]] = G[i][2]adjMatrix[G[i][1]][G[i][0]] = G[i][2]return adjMatrixdef prims(V, G):# create adj matrix from graphadjMatrix = createAdjMatrix(V, G)# arbitrarily choose initial vertex from graphvertex = 0# initialize empty edges array and empty MSTMST = []edges = []visited = []minEdge = [None, None, float('inf')]# run prims algorithm until we create an MST# that contains every vertex from the graphwhile len(MST) != V - 1:# mark this vertex as visitedvisited.append(vertex)# add each edge to list of potential edgesfor r in range(0, V):if adjMatrix[vertex][r] != 0:edges.append([vertex, r, adjMatrix[vertex][r]])# find edge with the smallest weight to a vertex# that has not yet been visitedfor e in range(0, len(edges)):if edges[e][2] < minEdge[2] and edges[e][1] not in visited:minEdge = edges[e]# remove min weight edge from list of edgesedges.remove(minEdge)# push min edge to MSTMST.append(minEdge)# start at new vertex and reset min edgevertex = minEdge[1]minEdge = [None, None, float('inf')]return MST# graph vertices are actually represented as numbers# like so: 0, 1, 2, ... V-1a, b, c, d, e, f = 0, 1, 2, 3, 4, 5# graph edges with weights# diagram of graph is shown abovegraph = [[a, b, 2],[a, c, 3],[b, d, 3],[b, c, 5],[b, e, 4],[c, e, 4],[d, e, 2],[d, f, 3],[e, f, 5]]# pass the # of vertices and the graph to run prims algorithmprint(prims(6, graph)) - Kruskal, Prim 알고리즘(출처 : github)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110import re# Class WeightedGraphclass WeightedGraph:def __init__(self, path):# open file to initialize the graphfile = open(path, "r")p = re.compile("\d+")# initialize the graphself.vertices, self.edges = map(int, p.findall(file.readline()))# use adjacent matrix to represent the graphself.graph = [[0]*self.vertices for _ in range(self.vertices)]# populate the graphfor i in range(self.edges):u, v, weight = map(int, p.findall(file.readline()))self.graph[u][v] = weightself.graph[v][u] = weight# Union find data structure for quick kruskal algorithmclass UF:def __init__(self, N):self._id = [i for i in range(N)]# judge two node connected or notdef connected(self, p, q):return self._find(p) == self._find(q)# quick union two componentdef union(self, p, q):p_root = self._find(p)q_root = self._find(q)if p_root == q_root:returnself._id[p_root] = q_root# find the root of pdef _find(self, p):while p != self._id[p]:p = self._id[p]return p# prim algorithmdef prim(G):# initialize the MST and the set XMST = set()X = set()# select an arbitrary vertex to begin withX.add(0)while len(X) != G.vertices:crossing = set()# for each element x in X, add the edge (x, k) to crossing if# k is not in Xfor x in X:for k in range(G.vertices):if k not in X and G.graph[x][k] != 0:crossing.add((x, k))# find the edge with the smallest weight in crossingedge = sorted(crossing, key=lambda e:G.graph[e[0]][e[1]])[0]# add this edge to MSTMST.add(edge)# add the new vertex to XX.add(edge[1])return MST# kruskal algorithmdef kruskal(G):# initialize MSTMST = set()edges = set()# collect all edges from graph Gfor j in range(G.vertices):for k in range(G.vertices):if G.graph[j][k] != 0 and (k, j) not in edges:edges.add((j, k))# sort all edges in graph G by weights from smallest to largestsorted_edges = sorted(edges, key=lambda e:G.graph[e[0]][e[1]])uf = UF(G.vertices)for e in sorted_edges:u, v = e# if u, v already connected, abort this edgeif uf.connected(u, v):continue# if not, connect them and add this edge to the MSTuf.union(u, v)MST.add(e)return MSTif __name__ == '__main__':WG = WeightedGraph("Graph")print("================USING PRIM ALGORITHM================")MST = prim(WG)# print the edges of the MSTfor edge in MST:print(edge)print("================END PRIM ALGORITHM================")print("================USING KRUSKAL ALGORITHM================")MST = kruskal(WG)# print the edges of the MSTfor edge in MST:print(edge)print("================END KRUSKAL ALGORITHM================")
