13.2.1 그래프의 표현
먼저 전체적인 코드를 구현해서 해결해야 할 문제점만 추려 냅니다.1
코드 13-1
class Edge:
def __init__(self, u, v, w):
self.u = u
self.v = v
self.w = w
class Graph:
def __init__(self, vertex_num):
self.adj_list = [[] for _ in range(vertex_num)]
self.edge_list = []
self.vertex_num = vertex_num
def add_edge(self, u, v, weight):
self.adj_list[u].append(v)
self.adj_list[v].append(u)
self.edge_list.append(Edge(u, v, weight))
코드 13-1을 보면 크루스칼 알고리즘을 적용하기 전에 그래프가 가질 멤버 등을 설계했습니다. MST는 무방향 그래프고 가중치 그래프입니다. 그리고 MST를 구한다는 것은 V(T)가 관심사가 아니라 E(T)만을 구하는 것이 목적이기 때문에 Edge 클래스를 따로 두었고 그래프에서도 에지 객체를 담아 둘 edge_list를 두었습니다.
1 코드 13-1~코드 13-8은 kruskal.py 파일에 있습니다.