크루스칼

■ 그래프 정리
다음 참조 :

korshika.tistory.com/42

graph(map) 구현(python)

 

■ 크루스칼 알고리즘

1) 정의 :

최소 비용으로 모든 그래프가 cycle이 없도록 연결되게 하는 연결방식을 찾는 알고리즘

> 존재하는 간선들 중 선택 된 간선의 개수는 노드V 간선E 일시, V-1 개가 선택 됨

2) 사용 그래프 구조 : 

> 인접리스트 사용

> 필요한건 순위로 정렬된 간선 비용과 그것을 이루는 노드이므로, 필요한 데이터만 담겨있는 인접리스트가 유리

 

■ 서로소 집합 - 알고리즘

1) 정의 :

공통원소가 없는 두 집합을 의미

ex) {1, 2} / {3, 4}

2) 사용 개념

> Union
   - 합집합 연산

> Find
   - 특정 원소가 속한 집합을 찾아주는 연산

 

 

■ 알고리즘

1) 모든 간선 정보에 대하여 비용 순으로 오름차순 정렬 수행 

   ( 최소비용 신장트리 이므로 )

   > 여기서는 간선 가독성 위해 간선 순으로 나열

---

2)  

가장 적은 비용을 가진 3-4 간선을 선택

3, 4 노드는 같은 집합이 아니므로 같은 집합에 속할 수 있도록 union 함수 호출

---

3)

그 다음 적은 비용을 가진 4 - 7 간선을 선택

4, 7 노드는 같은 집합이 아니므로 같은 집합에 속할 수 있도록 union 함수 호출

---

4)

그 다음 적은 비용을 가진 4 - 6 간선을 선택

4, 6 노드는 같은 집합이 아니므로 같은 집합에 속할 수 있도록 union 함수 호출

---

5)

그 다음 적은 비용을 가진 6 - 7 간선을 선택

6, 7 노드는 같은 집합이므로 cycle이 발생하므로 확인후 신장트리에 포함시키지 않음

.... 반복작업

 

6)

 

 

---

 

■ 구현

# 정점을 독립적인 집합으로 만듦
# union set 이전 각 node를 parent를 설정
def make_set(vertices):
	
    parent = {}
    rank = {}
	
    for v in vertices:
        parent[v] = v
        rank[v] = 0
        
    return parent, rank

# 특정 원소의 root V(Node) 집합을 찾기
def find_parent(parent, x):
    # root V(Node) 집합 찾을 때 까지 재귀호출
    if parent[x] != x :
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]
    
    
# 두 원소가 속한 집합을 합치기
# list의 mutable속성 사용
def union_parent(parent, rank, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    
    # union-by-rank 기법
    # 짧은 트리의 루트가 긴 트리의 루트를 가리키게 만드는 것이 좋다.
    if rank[a] > rank[b]:
        parent[b] = a
    else:
        parent[a] = b
        if rank[a] == rank[b]:
            rank[b] += 1



# kruskal 수행
def kruskal(graph):    
    parent, rank = make_set(graph['vertices'])
    
    mst = []
    
    edges = graph['edges']
    edges.sort() # 상승하는 방향으로 비용순으로 정렬
    
    for edge in edges:
        weight, v, u = edge
                
        if find_parent(parent, v) != find_parent(parent, u):
            union_parent(parent, rank, v, u)
            mst.append(edge)

    return mst

parent = {}
rank = {}

graph = {
'vertices': ['A', 'B', 'C', 'D'],
'edges': [
    (7, 'A', 'B'),
    (5, 'A', 'D'),
    (7, 'B', 'A'),
    (8, 'B', 'C'),
    (9, 'B', 'D'),
    (8, 'C', 'B'),
    (5, 'D', 'A'),
    (9, 'D', 'B'),
    ]
}


print(kruskal(graph))
>>>
[(7, '3', '4'), (13, '4', '7'), (23, '4', '6'), (29, '1', '2'), (34, '2', '6'), (53, '5', '6')]

 

 

■ 분석

# 정점을 독립적인 집합으로 만듦
# union set 이전 각 node를 parent를 설정
def make_set(vertices):
	
    parent = {}
    rank = {}
	
    for v in vertices:
        parent[v] = v
        rank[v] = 0
        
    print(f'initial make_set result :: \n parent : {parent}\n rank : {rank}')
        
    return parent, rank

# 특정 원소의 root V(Node) 집합을 찾기
def find_parent(parent, x):
    # root V(Node) 집합 찾을 때 까지 재귀호출
    if parent[x] != x :
    	parent[x] = find_parent(parent, parent[x])
    return parent[x]
    
    
# 두 원소가 속한 집합을 합치기
# list의 mutable속성 사용
def union_parent(parent, rank, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    
    
    # union-by-rank 기법
    # 짧은 트리의 루트가 긴 트리의 루트를 가리키게 만드는 것이 좋다.
    if rank[a] > rank[b]:
        parent[b] = a
    else:
        parent[a] = b
        if rank[a] == rank[b]:
            rank[b] += 1



# kruskal 수행
def kruskal(graph):    
    parent, rank = make_set(graph['vertices'])
    
    mst = []
    
    edges = graph['edges']
    edges.sort() # 상승하는 방향으로 비용순으로 정렬
    
    for edge in edges:
        weight, v, u = edge
                
        if find_parent(parent, v) != find_parent(parent, u):
            union_parent(parent, rank, v, u)
            mst.append(edge)
        
        print(f'parent : {parent}')
        print(f'rank : {rank}')
        print(f'\n'*2)
    
    return mst

parent = {}
rank = {}

graph = {
'vertices': ['1', '2', '3', '4', '5', '6', '7'],
'edges': [
    (29, '1', '2'),
    (75, '1', '5'),
    (34, '2', '6'),
    (35, '2', '3'),
    (7,  '3', '4'),
    (23, '4', '6'),
    (13, '4', '7'),
    (53, '5', '6'),
    (25, '6', '7'),
    ]
}


print(kruskal(graph))
>>>

initial make_set result :: 
 parent : {'1': '1', '2': '2', '3': '3', '4': '4', '5': '5', '6': '6', '7': '7'}
 rank : {'1': 0, '2': 0, '3': 0, '4': 0, '5': 0, '6': 0, '7': 0}
parent : {'1': '1', '2': '2', '3': '4', '4': '4', '5': '5', '6': '6', '7': '7'}
rank : {'1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 0, '7': 0}



parent : {'1': '1', '2': '2', '3': '4', '4': '4', '5': '5', '6': '6', '7': '4'}
rank : {'1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 0, '7': 0}



parent : {'1': '1', '2': '2', '3': '4', '4': '4', '5': '5', '6': '4', '7': '4'}
rank : {'1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 0, '7': 0}



parent : {'1': '1', '2': '2', '3': '4', '4': '4', '5': '5', '6': '4', '7': '4'}
rank : {'1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 0, '7': 0}



parent : {'1': '2', '2': '2', '3': '4', '4': '4', '5': '5', '6': '4', '7': '4'}
rank : {'1': 0, '2': 1, '3': 0, '4': 1, '5': 0, '6': 0, '7': 0}



parent : {'1': '2', '2': '4', '3': '4', '4': '4', '5': '5', '6': '4', '7': '4'}
rank : {'1': 0, '2': 1, '3': 0, '4': 2, '5': 0, '6': 0, '7': 0}



parent : {'1': '2', '2': '4', '3': '4', '4': '4', '5': '5', '6': '4', '7': '4'}
rank : {'1': 0, '2': 1, '3': 0, '4': 2, '5': 0, '6': 0, '7': 0}



parent : {'1': '2', '2': '4', '3': '4', '4': '4', '5': '4', '6': '4', '7': '4'}
rank : {'1': 0, '2': 1, '3': 0, '4': 2, '5': 0, '6': 0, '7': 0}



parent : {'1': '4', '2': '4', '3': '4', '4': '4', '5': '4', '6': '4', '7': '4'}
rank : {'1': 0, '2': 1, '3': 0, '4': 2, '5': 0, '6': 0, '7': 0}



[(7, '3', '4'), (13, '4', '7'), (23, '4', '6'), (29, '1', '2'), (34, '2', '6'), (53, '5', '6')]

 

---

참조 :

it-garden.tistory.com/411

크루스칼(Kruskal) 알고리즘 이론과 파이썬 구현

www.fun-coding.org/Chapter20-kruskal-live.html

파이썬과 컴퓨터 사이언스(고급 알고리즘): 최소 신장 트리 (Kruskal Algorithm) - 잔재미코딩

www.youtube.com/watch?v=Gj7s-Nrt1xE