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

2번째, 프림 알고리즘

개념은 이해가 되는데 코드로 구현한거는 이해가 안됬다.

그래서 수기로 순서대로 정리를...

import sys;

N = 7;

s = 0;

g = [None] * N # size 를 설정하기 위해서

g[0] = [(1,9), (2,10)];

g[1] = [(0,9), (3,10), (4,5), (6,3)];

g[2] = [(0,10),(3,9),(4,7),(5,2)];

g[3] = [(1,10),(2,9),(5,4),(6,8)];

g[4] = [(1,5),(2,7),(6,1)];

g[5] = [(2,2),(3,4),(6,6)]

g[6] = [(1,3), (3,8), (4,1), (5,6)];

visited = [False] * N

D = [sys.maxsize] * N #?????

D[s] = 0

previous = [None] * N;

previous[s] = s

if __name__ == '__main__':

 for k in range(N):

  m = -1

  min_value = sys.maxsize;

  print("k is %d" %k);

  for j in range(N):

   print("j in %d" %j);

   print("outter D[j] is %d" %D[j]);

   if not visited[j] and D[j] < min_value:

    print("D[j] is %d" %D[j]);

    min_value = D[j]

    m = j

  visited[m] = True

  

  for w, wt in list(g[m]):

   print("w : %d, wt : %d" %(w, wt));

   if not visited[w]:

    if wt < D[w]:

     print("if  wt :%d, D[w] : %d" %(wt, D[w]))

     print("previo", previous[w]);

     D[w] = wt

     previous[w] = m

     print("afeter pri", previous[w]);

    

 print("min tree", end = '');

 mst_cost = 0;

 for i in range(1, N):

  print("(%d, %d)" %(i, previous[i]), end='');

이 코드의 핵심은 방문리스트와 이전리스트를 활용하는 것이다.

방문이 되는 것은 최소 가중치로 선정이 됬을때이다.

이전 리스트는 가중치가 무한에서 자기가 갖고 있는 값으로 업데이트 됬을때 된다