파이썬과 함께하는 자료구조 8장 그래프(알고리즘)

이 장에선 여러가지 알고리즘을 배운다

이러한 알고리즘의 핵심은 최단 경로 혹은 최소 가중치로 신장트리를 만드는 것.

네비게이션이나 경로 탐색 등 다양한 분야에서 실제로 사용된다고 한다.

1. kruskal 알고리즘.

최소 신장트리를 만드는 것

if __name__ == '__main__':

 weights = [(0,1,9), (0,2,10), (1,3,10), (1,4,5), (1,6,3), (2,3,9), (2,4,7), (2,5,2), (3,5,4,), (3,6,8),(4,6,1),(5,6,6)]

 weights.sort(key = lambda t:t[2])

 mst = []

 N = 7

 p = []

 check = 0;  

 

 for i in range(N):

  p.append(i);

  

 def find(u):

  print("find", u)

  if u != p[u]:

   print("inner find", u, p[u]);ㅎ

   p[u] =find(p[u]);

  print("find p[u] : %d" %p[u]); 

  return p[u]

  

 def union(u,v):

  root1 = find(u)

  root2 = find(v)

  print("root1 :%d, root:%d" %(root1, root2));

  p[root2] = root1;

  print("p[r2] : %d, r1:%d" %(p[root2],root1))

  

 tree_edges = 0;

 mst_cost = 0;

 while True:

  if tree_edges == N-1:

   break;

  print("check", weights)

  u,v,wt = weights.pop(0);

  print("not if check", u, v, wt)

  if find(u) != find(v):

   print("check", u, v, wt)

   print("ch", p);

   union(u,v)

   mst.append((u,v))

   mst_cost += wt;

   tree_edges += 1

   

  

 print("최소 신장트리 :", end = '');

 print(mst)

 print('최소 신장트리 가중치 :', mst_cost)

코드는 위와 같다.

이 알고리즘의 핵심은 union-find 이다.

가중치로 정렬을 했기 때문에 제일 위부터 아래로 연결을 해주면 되는데

문제는 이 정점들이 싸이클이 되는지 확인하는 것이다.

그렇기에 이 싸이클 여부를 확인하는 것은 해당 정점의 최상 루트가 무엇인지를 파악 해주면 된다.

예를 들어 1-2, 2-3, 3-4, 4-5 이렇게 연결 되어 있는 경우에 5번 노드가 2,3번에 연결이 안되는 이유는 2,3의 최상 루트가 1번이기 때문이다.

재귀적 방식을 통해서 제일 위의 루트를 찾는것, 그리고 그것이 다를때만 연결을 해주는 것이 핵심이다.(이를 위해 p라는 임의의 리스트를 형성)