Advanced Algorithm - MST(Kruskal's Algorithm)(3)

1. 크루스칼 알고리즘의 구현

1) 기본 그래프의 구현 

- 아래의 그림과 같은 기본 그래프를 딕셔너리를 이용하여 구현한다. 

기본 그래프

 

mygraph = {
    'vertices':['A', 'B', 'C', 'D', 'E', 'F', 'G'],
    'edges':[
        (7, 'A', 'B'),
        (5, 'A', 'D'),
        (7, 'B', 'A'),
        (8, 'B', 'C'),
        (9, 'B', 'D'),
        (7, 'B', 'E'),
        (8, 'C', 'B'),
        (5, 'C', 'E'),
        (5, 'D', 'A'),
        (9, 'D', 'B'),
        (7, 'D', 'E'),
        (6, 'D', 'F'),
        (7, 'E', 'B'),
        (5, 'E', 'C'),
        (7, 'E', 'D'),
        (8, 'E', 'F'),
        (9, 'E', 'G'),
        (6, 'F', 'D'),
        (8, 'F', 'E'),
        (11, 'F', 'G'),
        (9, 'G', 'E'),
        (11, 'G', 'F')
    ]
}

 

 

2) 크루스칼 알고리즘 구현 

# 4. 2번과정의 make_set 함수에 필요한 작성 - 추후 union-by-rank 기법에 사용 
# 각 부분집합의 루트노드와 rank를 저장할 딕셔너리 생성
parent = dict() #각 노드의 루트노드를 저장
rank = dict() #각 부분집합의 rank를 저장 

# 7. 5번과정에서 작성한 find(), union() 함수를 작성 
def find(node):
    # path compression 기법을 함께 구현한다. 
    if parent[node] != node: #현재 노드와 부모노드가 다른 경우(상위 노드가 있음)
        parent[node] = find(parent[node]) # 재귀함수를 이용한 루트노드를 찾는 방식 
        
    # 재귀함수를 통해 현재 노드가 부모노드인 경우, 해당 노드가 루트노드이다.(상위 노드가 없음)
    return parent[node]
    
def union(node_v, node_u): 
    root1 = find(node_v)
    root2 = find(node_u)
    
    # 각 부분집합의 rank가 같은 경우와 다른 경우를 구현
    if rank[root1] > rank[root2]: #root1의 랭크가 더 높은 경우 
    
        # rank가 낮은 부분집합의 루트노드를 rank가 높은 부분집합의 루트노드로 변경
        parent[root2] = root1 
        
    
    # union-by-rank 기법 
    else: # root2의 랭크가 더 높거나 root1과 root2의 랭크가 동일한 경우 
        parent[root1] = root2 # root1의 루트노드를 root2로 변경 
        
        # 이미 이전코드에서 root2에 붙였기 때문에
        # 만약 rank가 동일하다면 rank2의 루트노드를 1 증가
        if rank[root1] == rank[root2]:
            rank[root2] += 1
        
    

# 3. 초기화 과정에 필요한 함수 작성 - 각 원소를 개별원소로 만듬
def make_set(node):
    parent[node] = node
    rank[node] = 0

# 1. 크루스칼 함수 작성     
def kruskal(graph):
    mst = list()
    
    # 2. Union-Find 알고리즘 - 초기화 과정
    for node in graph['vertices']:
        make_set(node)
        
    # 5. 간선 정렬 - 가중치 기준으로 오름차순 정렬
    edges = graph['edges']
    edges.sort() 
    # sort 메소드를 사용하면 edges에 저장된 데이터가 정렬된다. 퀵정렬을 사용해도 된다.
    
    # 6. 간선 연결 - 가장 가중치가 낮은 간선을 꺼내온다
    for edge in edges:
        
        # weight = 가중치, node_v = 연결된 노드1, node_u = 연결된 노드2
        # ex) (11, 'G', 'F')가 있다면, weight = 11, node_v = 'G', node_u = 'F'
        weight, node_v, node_u = edge
        
        # find 메소드 - 각 노드의 루트노드를 찾아 비교
        if find(node_v) != find(node_u):
            
            # 루트노드가 다르다면 합친다
            union(node_v, node_u)
            
            # mst 리스트에 삽입한다
            mst.append(edge)
    
    return mst

 

 

 

3) 크루스칼 알고리즘 수행결과

구현한 크루스칼 알고리즘 결과

 

결과 - MST

---

2. 크루스칼 알고리즘의 시간복잡도

크루스칼 알고리즘의 시간복잡도 설명

 

- 최종적으로 크루스칼 알고리즘의 시간복잡도는 O(E log E) 이다. 그 이유는 다음과 같다.

 

• 1단계 - 모든 정점을 독립적인 집합으로 만든다 → O(V)
   - 여기서 V는 Vertex(노드)를 의미한다. 노드의 개수만큼 시간복잡도가 계산된다.
  
  
• 2단계 - 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다 → O(E log E)
   - 여기서 E는 Edge를 의미한다. 간선의 개수만큼 시간복잡도가 계산된다. 
  
  
• 3단계 - 2개 부분집합 각각의 루트노드를 확인(find)하고 서로 다른 경우 union한다 → O(1)
   - union-by-rank 기법과 path compression 기법을 사용하면 상수에 가까운 시간복잡도를 갖는다. 

 

- 빅 오 표기법은 최악의 상황에서의 알고리즘 성능을 표기하기 때문에, 크루스칼 알고리즘의 연산에서 가장 높은 시간복잡도인 O(E log E)만큼의 시간복잡도를 갖는다.