최소신장트리!(프림과 크루스칼)

*그래프 내의 모든 정점을 포함하는 트리(최소로)

*사이클 있으면 ㄴㄴ

---

프림 — 시작정점을 기준으로 신장트리를 확장— 방법은 다익스트라와 동일한거 같음!

차이점- 다익스트라는 모든정점이 아닌 최단경로만 계산!

           프림은 모든 정접을 지나가는 경로를 계산!

 

def get_min_node(node_num):
    print("get_min_node 함수 진입했다")
    for i in range(node_num):
        if not visited[i]:
            v = i
            break
    print("아직 방문하지 않은 v: ", v)
    for i in range(node_num):
        if not visited[i] and distances[i] < distances[v]:
            print("i: ", i, "\\tv: ", v)
            print("distaces[i], distances[v]: ", distances[i], distances[v])
            v = i
            print("아직 방문 안됐고, 기존 v보다 distances값 작은 정점 발견 교체, 최종 v: ", v)

    return v

def prim(start, node_num):
    # distances 배열과 visted 배열 초기화
    for i in range(node_num):
        visited[i] = False
        distances[i] = INF

    # 시작노드의 distance 값을 0으로 초기화
    distances[start] = 0
    for i in range(node_num):
        print("--------------------")
        print("prim 메소드 내부 반복 시작, 반복 회차: ", i)
        node = get_min_node(node_num)
        visited[node] = True    # node 를 방문했다 표시
        print("\\nget_min_node 에서 선택된 노드: ", node)

        for j in range(node_num):
            if adj_mat[node][j] != INF:
                if not visited[j] and adj_mat[node][j] < distances[j]:
                    print("error")
                    distances[j] = adj_mat[node][j]

        print("distances: ", distances)
        print("--------------------")

 

 

 

크루스칼 — 가장 작은 간선부터 연결하는데 사이클이 생기지않게 계속 연결반복

---

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# union 연산
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 간선 정보 담을 리스트와 최소 신장 트리 계산 변수 정의
edges = []
total_cost = 0

# 간선 정보 주어지고 비용을 기준으로 정렬
for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))

# 간선 정보 비용 기준으로 오름차순 정렬
edges.sort()

# 간선 정보 하나씩 확인하면서 크루스칼 알고리즘 수행
for i in range(e):
    cost, a, b = edges[i]
    # find 연산 후, 부모노드 다르면 사이클 발생 X으므로 union 연산 수행 -> 최소 신장 트리에 포함!
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        total_cost += cost

최소 신장 트리 (MST, 크루스칼, 프림 알고리즘)

참고블로그!

최소 신장 트리 (MST, 크루스칼, 프림 알고리즘)

 

 

 

 

틀린점이 있다면 댓 달아주세요!