[알고리즘] 최소 신장 트리

비교

• 그래프 G의 신장트리
  • 그래프 내의 모든 정점을 포함하는 트리
  • G의 정점들과 간선들로만 구성된 트리
• 그래프 G의 최소(비용) 신장트리(MST)
  • G의 신장트리들 중 간선의 합이 최소인 신장트리

최소 신장 트리

• Minimum Spanning Trees(MST)
• 간선들의 가중치 합이 최소인 신장트리
• 무방향 가중치 그래프 G = (V,E)
• 각 Edge의 가중치 w(u,v)

Quiz

• 아래의 조건을 만족하는 Edge들의 부분집합 T 찾기
  • T에 속한 Edge들에 의해 그래프의 모든 노드들이 서로 연결될 수 있다.
  • 가중치의 합이 최소가 된다.

크루스칼 알고리즘 // 작은 가중치 먼저(무방향 그래프)

• 사이클을 만들지 않는 범위에서 최소 비용 간선을하나씩 더해가면서 최소 신장 트리를 만든다.
• 현재 선택할 수 있는 가장 가중치가 작은 간선을 선택

Quiz

• 만약 MST에 사이클이 생긴다면?
  • 그 간선을 넣지 않아야 함

크로스칼의 최소비용 신장트리 알고리즘

1) 그래프의 모든 간선을 가중치에 따라 오름차순으로 정렬한다.
2) 가장 가중치가 작은 간선 e를 뽑는다.
3) e를 신장트리에 넣었을 때 사이클이 생기면 넣지 않고 2번으로 이동한다.
4) 사이클이 생기지 않으면 최소 신장트리에 삽입한다.
5) n-1개의 간선이 삽입될 때 까지 2번으로 이동한다.

사이클 검사

• 새로운 간선이 사이클을 만드는 경우?
  • 이미 다른 경로를 통해 연결된 정점들 사이의 간선인 경우
  • 해결 방안
    • 서로소 부분집합과 Union-Find 알고리즘
• find(x): 원소 x가 속한 집합 --> 보통은 "대표원소"반환
• union(x,y):원소 x와 y가 속한 집합을 하나로 뭉침
  1) S = {1,2,3,4,5,6}
  2) union(1,4)와 union(5,2) = {1,4},{5,2},{3},{6}
  3) union{4,5}와 union(3,6) = {1,4,5,2}.{3,6}

크루스칼 알고리즘 의사코드

Kruskal(G)
{
    1. T <-- ∅; // T: 신장트리
    2. 단 하나의 정점만으로 이루어진 n개의 집합을 초기화 한다; //Conected Component
    3. 간선 집합 E를 가중치가 작은 순으로 정렬한다; (내림차순도 무방)
    4. while(T의 간선 수 < n-1){
            E에서 최소비용 간선(u,v)를 제거한다;
            정점 u와 정점 v가 서로 다른 집합에 속하면 { //find(u), find(v)
                두 집합을 하나로 합친다; //union(u,v)
                T <-- T ∪ {{u,v}}; 
            }
        }
}

크루스칼 알고리즘의 구현

# Kruskal의 최소비용 신장트리

def MSTKruskal(V, adj):
    n = len(V)
    dsets = disjointSets(n)
    E = []
    for i in range(n-1):
        for j in range(i+1, n):
            E.append((i,j,adj[i][j]))

    E.sort(key = lambda e : e[2])

    ecount = 0
    for i in range(len(E)):
        e = E[i]
        yset = dsets.find(e[0])
        vset = dsets.find(e[1])

        if uset != vset:
            dsets.union(uset, vset)
            print("간선 추가 : (%s, %s, %d)" % (V[e[0]], V[e[1]], e[2]))
            ecount += 1
            if ecount == n-1:
                break

# disjointSets(서로소 집합)

class disjointSets:
    def __init__(self,n):
        self.parent = [-1]*n
        self.set_size = n

    def find(self, id):
        while (self.parent[id] >= 0):
            id = self.parent[id]
        return id

    def union(self, s1, s2):
        self.parent[s1] = s2
        self.set_size = self.set_size-1

프림 알고리즘 // 이웃에 있는 것들 중 작은 가중치

• 그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘
• 집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 (즉, S=V가 될때까지) 키워나감
• 현재까지 만들어진 MST의 인접 정점들 중에서 간선 가중치가 최소인 정점을 반복적으로 선택해 트리를 확장

Prim의 최소비용 신장트리 알고리즘

1) 그래프에서 시작 정점을 선택하여 초기 트리를 만든다
2) 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택한다.
3) 이 정점 v와 이때의 간선을 트리에 추가한다.
4) 모든 정점이 삽입될 때 까지 2번으로 이동한다.

프림 알고리즘 의사코드

Prim()
1. 그래프에서 시작 정점을 선택하여 초기 트리를 만든다.
2. 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택한다.
3. 이 정점 v와 이때의 간선을 트리에 추가한다.
4. 모든 정점이 삽입될 때 까지 2번으로 이동한다.

Prim(G, r)
{
    S <-- ∅;
    정점 r을 방문되었다고 표시하고, 집합 S에 포함시킨다.
    while(S != V){
        S에서 V-S를 연결하는 간선들 중 최소길이의 간선 (x,y)를 찾는다;
        //(x ∈ S, y ∈ V-S) 
        정점 y를 방문되었다고 표시하고, 집합 S에 포함시킨다;
    }
}

Prim(G, r)
// G = (V,E) : 주어진 그래프
// r : 시작으로 삼을 정점

{
    S <-- ∅;               // S : 정점 집합
    for each u ∈ V
        d_u <-- ∞ ;
    d_r <-- 0;
    while (S!=V){
        u <-- extractMin(V-S, d);
        S <-- S ∪ {u};
        for each v ∈      // L(u) : u로부터 연결된 정점들의 집합
            if(v ∈ V-S and w_uv < d_v) then d_v <-- w_uv;
    }
}

extraMin(Q,d)
{
    집합 Q에서 d값이 가장 작은 정점 u를 리턴한다;
}

프림 알고리즘의 구현

INF = 9999

def MSTPrim(vertex, adj):
    vsize = len(vertex)
    dist = [INF] * vsize
    dist[0] = 0
    selected = [False] * vsize

    for i in range(vsize):
        u = getMinVertex(dist, selected)
        selected[u] = True
        print(vertex[u], end=':')
        print(dist)

    for v in range(vsize):
        if(adj[u][v] != None):
            if selected[v] == False and adj[u][v] < dist[v]:
                dist[v] = adj[u][v]

def getMinVertex(dist, selected):
    minv = -1
    mindist = INF
    for v in range(len(dist)):
        if not selected[v] and dist[v] < mindist:
            mindist = dist[v]
            minv = v
    return minv

최단 경로

• 조건
  • 간선 가중치가 있는 유향 그래프
  • 무향 그래프는 각 간선에 대해 양쪽으로 유향 간선이 있는 유향 그래프로 생각할 수 있다
    • 즉, 무향 간선(u,v)는 유향 간선(u,v)와 (v,u)를 의미한다고 가정하면 된다
• 두 정점 사이의 최단 경로
  • 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로
  • 간선 가중치의 합이 음인 사이클이 있으면 문제가 정의되지 않는다
• 단일 시작점 최단경로
  • 단일 시작점으로부터 각 정점에 이르는 최단경로를 구한다
  • 다익스트라 알고리즘
    • 음의 가중치를 허용하지 않는 최단경로
  • 벨만-포드 알고리즘
    • 음의 가중치를 허용하는 최단경로
• 모든 쌍 최단경로
  • 모든 정점 쌍 사이의 최단경로를 모두 구한다
  • 플로이드-워샬 알고리즘

다익스트라 알고리즘 // 더해가며 최소 찾기(방향 그래프)

• 두 노드 사이의 최단거리를 구하는 알고리즘
• 한 정점에서 다른 모든 정점까지의 최단 경로 거리
• 최단거리가 확정된 정점들과 간선으로 직접 연결된 정점들 중에서 가장 가까운 정점을 선택
• 각 정점 w에 대해
  • u를 거쳐서 w로 가는 새로운 경로가 더 짧다면 dist[w] 갱신
    • dist[w] = dist[u] + weight[u][w]
  • 그렇지 않다면 dist[w] 유지

다익스트라 알고리즘 의사 코드

Dijkstra(G,r)
// G = (V,E) : 주어진 그래프
// r : 시작으로 삼을 정점
{
    S <-- ∅;                        // S: 정점 집합
    for each u ∈ V
        d[u] <-- ∞;
    d[r] <-- 0;
    while (S != V){                 // n회 순환된다
        u <-- extractMin(V-S, d);
        S <-- S ∪ {u};
        for each v ∈ L(u)           // L(u) : u로부터 연결된 정점들의 집합
            if(v ∈ V-S and d[u] + w[u,v] < d[v]) then{
                d[v] <-- d[u] + w[u,v];
                prev[v] <-- u;
                }
    }
}

extractMin(Q, d[])
{
    집합 Q에서 d값이 가장 작은 정점 u를 리턴한다;
}

다익스트라 알고리즘의 구현

def shortest_path_dijkstra(vtx, adj, start):
    vsize = len(vtx)
    dist = list(adj[start])
    dist[start] = 0
    path = [start] * vsize
    found = [False] * vsize
    found[start] = True

    for i in range(vsize):
        print("Step%2d: "%(i+1),dist)
        u = getMinVertex(dist, found)
        found[u] = True

        for w in range(vsize):
            if not found[w]:
                if dist[u] + adj[u][w] < dist[w]:
                    dist[w] = dist[u] + adj[u][w]
                    path[w] = u

    return path