10. 그래프 알고리즘

그래프에서 간선에 적혀있는 가중치가 전부 동일하지 않다면, 최단거리를 구하는 일은 생각보다 복잡합니다. 지금부터는 이러한 경우의 최단경로를 구하는 알고리즘에 대해서 소개하겠습니다.

1. 다익스트라 (Dijkstra)

특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘입니다. 예를 들어 5개의 정점(1 ~ 5번)이 있고 1번 정점에서 출발한다고 가정하면, 1번에서 2 ~ 5번으로 가는 최단거리를 구해줍니다.

양의 가중치만 있는 그래프에서만 다익스트라를 이용해 최단거리를 구할 수 있으며, 음의 가중치가 있으면 다시 골라졌던 정점에 도달하는 dist값이 더 작아질 수 있기 때문에 최단거리임을 보장할 수 없게 됩니다.

 

다익스트라의 아이디어

다른 지점까지의 거리는 모르지만, A라는 지점까지 가는 최단거리는 확실히 안다고 가정해보겠습니다. 그렇다면 A를 거쳐 다른 지점을 갈 수 있다면, 다음과 같이 추측할 수 있습니다.

특정 지점까지 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리

 

다익스트라는 이 아이디어를 기반으로 설계된 알고리즘입니다.

 

다익스트라의 동작 과정

 

1. 초기화

• 거리 배열(dist)을 아주 큰 값(INF)으로 초기화하고, 출발지의 값만 0으로 설정(출발지는 최단거리가 0)합니다.
• 모든 정점을 전부 우선순위 큐(힙)에 넣습니다.
  • 이후 거리 값 중 최솟값을 고르는 데 효과적으로 사용됩니다.

2. 반복

• 우선순위 큐에서 최솟값을 고르고, 뽑힌 노드는 우선순위 큐에서 빠지게 됩니다.
  • 최솟값이 뽑혔다는 의미는 시작점으로부터의 뽑힌 노드까지의 최단거리는 확실히 정해졌다는 뜻입니다.

• 뽑힌 노드에 연결된 노드들을 보며, dist[뽑힌 노드]에 간선에 적혀있는 값을 더했을 때 해당(인접) 노드에 적혀있는 dist값과 비교하여 더 작은 값으로 갱신해줍니다. 이때 갱신된 노드는 다시 우선순위 큐에 추가됩니다.
• 이 과정을 모든 노드가 선택될 때까지 반복합니다.
  • 우선순위 큐가 빌 때까지?

3. 종료

• 모든 노드가 선택되면 알고리즘이 종료되고, 출발 노드에서 각 노드까지의 최단 거리가 결정됩니다.

시작점인 5를 뽑고, 인접 노드를 갱신한 후의 중간 모습

function dijkstra(graph, source)              // 그래프와 시작점 정보가 주어집니다.
    set Q = Queue()                           // 우선순위 큐를 만들어줍니다.

    for each vertex in graph                  // 그래프에 있는 모든 노드들에 대해
        set dist[v] = INF                     // 초기값을 전부 아주 큰 값으로 설정해주고 
        Q.push(v)                             // 우선순위큐에 각 노드를 넣어줍니다.

    set dist[source] = 0                      // 시작점에 대해서만 dist 값을 0으로 초기화해줍니다.
    while Q is not empty                      // 우선순위 큐가 비어있지 않을 때까지 반복합니다.
        set u = vertex in Q with min dist     // 우선순위 큐에서 dist값이 가장 작은 노드를 선택합니다.
        Q.remove(u)                           // 우선순위 큐에서 해당 노드를 제거해줍니다.

        for each neighbor v of u              // u번 노드와 연결된 노드들을 전부 살펴보면서
            set alt = dist[u] + length(u, v)  // 현재 dist값에 간선 가중치를 더한 값을 계산하여
            if alt < dist[v]                  // 기존 dist값보다 더 alt값이 작다면
                set dist[v] = alt             // dist값을 갱신해줍니다.

public class Main {
    static class Node{
        int v; //간선
        int cost; //가중치

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }
    }

    static ArrayList<Node>[] graph; //각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
    static boolean[] visit; //방문한 적이 있는지 체크하는 목적의 리스트
    static int[] dist; //최단 거리 테이블

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int v = Integer.parseInt(st.nextToken()); // 정점 개수(1번 ~ n번)
        int e = Integer.parseInt(st.nextToken()); // 간선 개수
        int k = Integer.parseInt(br.readLine()); // 시작 정점

        graph = new ArrayList[v + 1];
        dist = new int[v + 1];
        visit = new boolean[v + 1];

        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE; //최대값으로 초기화, 최단거리를 찾기 위함
        }

        for (int i = 0; i < e; i++) {
            // u -> v 로 가는 가중치 w가 주어진다
            st = new StringTokenizer(br.readLine());
            int inputU = Integer.parseInt(st.nextToken());
            int inputV = Integer.parseInt(st.nextToken());
            int inputW = Integer.parseInt(st.nextToken());

            graph[inputU].add(new Node(inputV, inputW));
        }

        //다익스트라 알고리즘 수행
        dijkstra(k);
    }

    static void dijkstra(int start) {
        //우선 순위 큐 사용, 가중치를 기준으로 오름차순한다
        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        
        //시작 노드에 대해서 초기화
        q.add(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            //현재 최단 거리가 가장 짧은 노드를 꺼내서 방문 처리 한다
            Node now = q.poll();

            if (!visit[now.v]) {
                visit[now.v] = true;
            }

            for (Node next : graph[now.v]) {
                //방문하지 않았고, 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우
                if (!visit[next.v] && dist[next.v] > now.cost + next.cost) {
                    dist[next.v] = now.cost + next.cost;
                    q.add(new Node(next.v, dist[next.v]));
                }
            }
        }
    }
}

 

다익스트라의 시간복잡도

• 그래프 내의 정점의 수를 |V|, 간선의 수를 |E|라 했을 때, 각 간선을 한 번씩 보게 되고, dist값이 변하면 우선순위 큐에서의 순서가 계속 바뀌게 될 수도 있으므로, 간선의 수 * 우선순위 큐 이용 시간복잡도인 O(|E|log|V|)가 소요됩니다.
  • 다익스트라를 한 번 이용하면, 선택한 지점에서부터 모든 지점까지의 최단거리를 구할 수 있습니다. 따라서, N개의 정점에 대해 다익스트라를 모두 시행해주면, 모든 지점에서부터 다른지점까지의 최단거리를 구할 수 있고, O(|V|*|E|log|V|)시간이 소요됩니다.
• 만약 우선순위 큐를 이용하지 않고, for문을 이용해 최솟값을 찾는 식으로 코드를 구현하면, 최솟값에 해당하는 노드를 고르는 데 |V|시간이 소요되고 이 과정을 |V|번 반복해야 모든 노드를 선택하게 되므로, 시간복잡도는 O(|V|^2)이 됩니다.
  • 만약 그래프에 간선이 굉장히 많은 경우라면, E=V^2이 되므로, 이런 경우라면 우선순위 큐를 이용하지 않는 것이 더 유리합니다.

---

2. 플로이드워셜 (Floyd Warshall)

모든 쌍(i → j)에 대해 최단거리를 구해야하는 상황에서 사용하기에 좋은 알고리즘입니다. 예를 들어 3개의 정점(1 ~ 3번)이 있을 경우, 1번에서 1번, 1번에서 2번, 1번에서 3번, 2번에서 1번, 2번에서 2번, 2번에서 3번, 3번에서 1번, 3번에서 2번, 3번에서 3번으로 가는 최단거리를 구해줍니다.

 

플로이드워셜의 아이디어

다익스트라와 다소 유사한데, 경유할 점을 1번 노드부터 N번 노드로 확장해가며, 경유지를 거쳐 다른 지점으로 갔을 때의 거리가 더 짧다면 갱신해주는 방식입니다.

A → B로 가는 경로보다 A → X(경유지) → B로 가는 경로가 더 짧다면 그것으로 갱신을 해줍니다.

 

플로이드워셜은 이 아이디어를 기반으로 설계된 알고리즘입니다.

 

플로이드워셜의 동작 과정

 

1. 초기화

• V^2 크기의 배열(dist) 내에 있는 모든 값을 아주 큰 값(INF)로 초기화합니다.
  • dist[i][j]는 i → j로  가는 최단거리를 의미합니다.
• 이후 주어진 그래프에서 각 간선에 적혀있는 숫자들을 dist 배열에 적어줍니다. 단, dist[i][i]는 자기 자신으로 가는 최단거리이므로 값 0을 꼭 적어줘야만 합니다.

2. 반복

• 먼저 모든 쌍 (i, j)에 대해 노드 1을 경유하는 것이 더 좋은 경우 그 값을 갱신해줍니다. 즉, dist[i][j] > dist[i][1] + dist[1][j]를 만족하는 경우 dist[i][j]에 dist[i][1] + dist[1][j] 값을 넣어줍니다.
• 이 과정을 2번 노드를 경유하는 경우, ..., N번 노드를 경유하는 경우가 될때까지 반복합니다.

3. 종료

• 위의 반복을 N번 노드까지 전부 진행하게 되면, dist 배열에 각 쌍에 대한 최단거리가 남게 됩니다.

경유점을 처음 1로 잡고, 최단 거리를 갱신한 후의 중간 모습

function floyd(graph)
    set dist = |V|+1 * |V|+1 array initialized to INF  // 처음 dist 배열을 아주 큰 값인 INF로 초기화합니다.
    for each edge(u, v)                            // 주어진 그래프의 모든 간선에 대해
        dist[u][v] = length(u, v)                  // 각 간선의 가중치를 dist 배열에 적어줍니다.
    for k = 1 ... |V|                              // 확실하게 거쳐갈 정점을 1번부터 V번까지 순서대로 정의합니다.
        for i = 1 ... |V|                          // 고정된 k에 대해 모든 쌍 (i, j)를 살펴봅니다.
            for j = 1 ... |V|
                if dist[i][j] > dist[i][k] + dist[k][j]     // i에서 j로 가는 거리가 k를 경유해 가는 것이 더 좋다면
                    dist[i][j] = dist[i][k] + dist[k][j]    // dist[i][j]값을 갱신해줍니다.
    return dist

public class Main {

    public static final int INF = Integer.MAX_VAULE;
    public static int n; // 노드의 개수(최대 500개라고 가정)
    public static int m; // 간선의 개수
    public static int[][] dist = new int[501][501]; // 최단 거리 테이블

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        // 최단 거리 테이블을 모두 무한으로 초기화
        for (int i = 0; i < 501; i++) {
            Arrays.fill(dist[i], INF);
        }

        // 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
        for (int a = 1; a <= n; a++) {
        	dist[a][a] = 0;
        }

        // 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
        for (int i = 0; i < m; i++) {
            // A에서 B로 가는 비용은 C라고 설정
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            dist[a][b] = c;
        }

        // 점화식에 따라 플로이드 워셜 알고리즘을 수행
        for (int k = 1; k <= n; k++) {
            for (int a = 1; a <= n; a++) {
                for (int b = 1; b <= n; b++) {
                    dist[a][b] = Math.min(dist[a][b], dist[a][k] + dist[k][b]);
                }
            }
        }
    }
}

 

플로이드워셜의 시간복잡도

3중 반복문을 돌리다보니 시간복잡도가 O(V^3)이 소요되므로, 상당히 비효율적이라는 단점이 있습니다. 따라서, 정점의 수가 많지 않거나 모든 쌍에 대한 최단거리를 구해야만 할 때 사용하는 것이 좋습니다. 정점의 수가 많아진다면 필요한 지점들에 대해서만 다익스트라를 돌려서 해결하는 것이 좋습니다.

---

3. 크루스칼 (Kruskal)

최소 신장 트리(MST, Minimum Spanning Tree)를 찾기 위한 알고리즘 중 하나로, 간선 중심의 접근 방식을 사용합니다.

 

Spanning Tree란

최소한(N-1개)의 간선을 사용하여 그래프 내 모든 정점을 이어준 것입니다. 즉, N개의 정점에 N-1개의 간선이 존재하는 트리(사이클이 존재하면 x)가 됩니다. 

 

MST(Minimum Spanning Tree)란

가중치가 있을 때, 최소한의 비용을 사용한 Spanning Tree를 Minimum Spanning Tree라고 부릅니다. 또한, MST는 여러 개가 존재할 수 있습니다.

빨간색으로 선택된 것이 MST임

 

Union-Find

서로소 집합(Disjoint Set)들을 효율적으로 관리하기 위한 자료구조입니다. 각 집합은 하나의 대표자를 가지고 있으며, 이는 트리의 루트 노드입니다. 특정 원소가 어떤 집합에 속해있는지 확인하고(find), 특정 집합을 합치는(union) 연산을 빠르게 수행할 수 있습니다.

 

1. 초기화

먼저 모든 노드가 연결되어 있지 않은 상황에서 시작합니다. 그룹 번호를 뜻하는 uf 배열을 만들고, 초기값을 자기 자신으로 설정합니다. 따라서 처음에는 모든 노드가 전부 다른 그룹에 있게 됩니다.

 

2. Find 연산

• 주어진 원소가 속한 집합의 루트를 찾는 연산입니다. find(x) 함수는 x 노드가 포함된 집단의 루트 노드를 찾아줌과 동시에, 이 루트 노드가 그 집단을 대표하는 대표 번호가 됩니다.
• 이 연산을 통해, 두 원소가 같은 집합에 속해 있는지 확인할 수 있습니다.
• 최악의 경우(원소들이 나란히 연결된 형태)에는 O(N)의 시간이 소요됩니다. 경로 압축(Path Compression)을 사용하면, find 연산 수행 시 경로 상에 있는 모든 노드들이 루트 노드를 직접 가리키도록 업데이트하여, 트리의 높이를 줄이고 시간을 개선할 수 있습니다. 

// 경로 압축이 적용된 find 연산
function find(x)
  if uf[x] == x                 // x가 루트 노드라면
    return x                    // x 값을 반환합니다.
  set root_node = find(uf[x])   // x가 루트 노드가 아니라면, x의 부모인 uf[x]에서 더 탐색을 진행합니다.
  uf[x] = root_node             // 노드 x에 부모를 루트 노드로 설정해줍니다.
  return root_node              // 찾아낸 루트 노드를 반환합니다.

 

3. Union 연산

• 두 집합을 하나로 합치는 연산입니다. 두 집합의 대표자를 찾아서 하나의 집합으로 병합합니다.
• union을 이용해 두 노드를 합치게 되면 uf배열의 값은 그룹으로서의 의미 뿐만 아니라, 실제 노드가 현재 가리키고 있는 부모 노드의 번호가 됩니다.
• union 연산의 동작 과정
  • 두 노드 모두 부모 노드를 따라 올라 갈 수 있는데 까지 계속 올라갑니다. 즉, 각 노드에 대해 find를 진행하면, x와 uf[x] 값이 같아지기 전까지 계속 올라가게 됩니다.
  • 골라진 루트 노드가 X, Y였다면, uf[X]에 Y를 넣어줍니다.

function union(x, y)
  set X = find(x), Y = find(y)
  uf[X] = Y

 

Union-Find의 시간복잡도

• 경로 압축을 적용한 경우, union과 find 함수의 시간복잡도는 최악의 상황에서도 O(logN)입니다.
• 경로 압축을 적용하지 않은 경우, union과 find 함수의 시간복잡도는 최악의 경우 O(N)입니다.

 

크루스칼의 아이디어

MST는 가중치의 합을 최소로 하는 Spanning Tree이니, 가중치가 적은 간선부터 고릅니다.
단, MST는 트리이기 때문에 절대 사이클이 생겨서는 안됩니다.

 

크루스칼은 이 아이디어를 기반으로 설계된 알고리즘입니다.

 

크루스칼의 동작 과정

 

1. 간선 정렬

• 그래프의 모든 간선을 가중치의 오름차순으로 정렬합니다.

2. 집합 초기화

• 각각의 정점을 개별 집합으로 초기화합니다. 이는 Union-Find 자료구조를 사용하여 관리합니다.

3. 간선 선택

• 정렬된 간선 리스트를 순서대로 확인하면서, 현재 간선이 추가되었을 때 사이클을 형성하지 않으면 해당 간선을 최소 신장 트리(MST)에 추가합니다.
  • 사이클 형성 여부 확인을 위해, 해당 간선 양 끝에 있는 두 노드 x, y에 대해 find(x), find(y) 값을 비교하여 두 정점이 같은 집합에 속해 있는지 확인할 수 있습니다. 만약, 이 값이 일치하지 않다면 사이클을 형성하지 않은 것입니다.
• 특정 간선이 최소 신장 트리(MST)에 추가되었다면, 두 노드에 union 연산을 수행하여 같은 집합으로 만들어줍니다.
• 이 과정을 N-1개의 간선이 선택될때까지 반복합니다.

4. 종료

• 그래프에서 노드의 수를 N이라 했을 때, 최종적으로 선택된 간선의 수는 N-1개가 되며, 이 N-1개의 간선이 결국 MST를 이루게 됩니다.

빨간색으로 선택된 것이 MST임

function kruskal()
    mst = []                       // mst를 담을 배열입니다.
    sort edge[] by length          // 간선을 가중치 기준으로 오름차순 정렬합니다.
    uf = uf_init(|V|)              // uf 배열을 노드의 수 |V|만큼 초기화합니다.

    for E in edge[]                // 각각의 간선에 대해 
        u, v = E                   // 간선을 이루고 있는 두 노드 u, v를 보며
        if find(u) != find(v)      // u, v의 루트 노드가 다른 경우에만
            mst.push(E)            // mst에 해당 간선을 넣어주고
            union(u, v)            // u, v를 같은 루트 노드를 갖도록 만들어줍니다.
    
    return mst

 

Kruskal의 시간복잡도

그래프 내 간선의 수를 E라 했을 때, 간선을 정렬하는 데 O(ElogE)의 시간이 소요됩니다. 또한, 각 간선에 대해 union-find는 O(logN)이 소요됩니다. 따라서, ElogE + ElogN가 되어 총 시간복잡도는 O(ElogE)가 됩니다.

---

4. 프림 (Prim)

최소 신장 트리(MST, Minimum Spanning Tree)를 찾기 위한 알고리즘 중 하나로, 정점 중심의 접근 방식을 사용합니다.

구현은 다익스트라 알고리즘과 거의 동일합니다. (현재 노드를 u라 했을 때, 다익스트라는 dist[v]와 dist[u]+length(u,v)를 비교하여 갱신하고, 프림은 dist[v]와 length(u,v)를 비교하여 갱신합니다.)

 

프림의 아이디어

한 지점에서 시작하여 점점 트리(MST)를 확장하는 방식입니다. 매 단계에서 현재 MST에 특정 간선을 새로 추가하여 새로운 정점을 하나 붙이고, 해당 정점에 인접한 간선을 고려합니다.

현재 트리(MST)에 가장 적은 비용으로 정점을 추가하는 선택을 반복합니다.

 

프림은 이 아이디어를 기반으로 설계된 알고리즘입니다.

 

프림의 동작 과정

dist[x] 배열의 정의는 현재까지 만들어진 MST와 노드 x를 연결하기 위해 필요한 최소 비용입니다.

 

1. 초기화

• 임의로 시작 정점을 선택합니다.
  • 시작점이 달라지면, 가중치의 합은 같지만 형태가 다른 MST를 만들어낼 수도 있습니다.
• dist 배열을 아주 큰 값(INF)으로 초기화하고, 출발지의 값만 0으로 설정(처음 MST는 출발지 노드로만 이루어짐)합니다.
• 모든 정점을 전부 우선순위 큐(힙)에 넣습니다.
  • 이후 dist 내의 값들 중 최솟값을 고르는 데 효과적으로 사용됩니다.

2. 반복

• 우선순위 큐에서 최솟값을 고르고, 뽑힌 노드는 우선순위 큐에서 빠지게 됩니다.
  • 최솟값이 뽑혔다는 의미는 해당 노드와 연결하는 간선을 MST에 추가하겠다는 뜻입니다.
• 뽑힌 노드에 연결된 노드들을 보며, 간선에 적혀있는 값과 해당(인접) 노드에 적혀있는 dist값과 비교하여 더 작은 값으로 갱신해줍니다. 이때 갱신된 노드는 다시 우선순위 큐에 추가됩니다.
  
  • 이미 MST에 포함된 노드끼리 연결한다면, 간선 추가시 사이클이 발생하므로 추가하지 않습니다.
• 이 과정을 모든 노드가 선택될 때까지 반복합니다.

3. 종료

• 모든 노드가 MST에 포함되면 알고리즘이 종료되고, 최종적으로 dist 배열에 적혀있는 값들이 각 정점을 MST에 추가하기 위해 필요한 최소 비용이 됩니다.

시작점인 5를 뽑고, 인접 노드에 대한 dist를 갱신한 후의 중간 모습

function prim(graph)                          // 그래프와 시작점 정보가 주어집니다.
    set Q = Queue()                           // 우선순위 큐를 만들어줍니다.

    for each vertex in graph                  // 그래프에 있는 모든 노드들에 대해
        set dist[v] = INF                     // 초기값을 전부 아주 큰 값으로 설정해주고 
        Q.push(v)                             // 우선순위큐에 각 노드를 넣어줍니다.
    set source = |V|                          // 시작점을 임의로 마지막 노드로 설정합니다.
    set dist[source] = 0                      // 시작점 대해서만 dist 값을 0으로 초기화해줍니다.
    while Q is not empty                      // 우선순위 큐가 비어있지 않을 때까지 반복합니다.
        set u = vertex in Q with min dist     // 우선순위 큐에서 dist값이 가장 작은 노드를 선택합니다.
        Q.remove(u)                           // 우선순위 큐에서 해당 노드를 제거해줍니다.

        for each neighbor v of u              // u번 노드와 연결된 노드들을 전부 살펴보면서
            set alt = length(u, v)            // 간선 가중치를 살펴봅니다.
            if alt < dist[v]                  // 기존 dist값보다 더 alt값이 작다면
                set dist[v] = alt             // dist값을 갱신해줍니다.

 

프림의 시간복잡도

• 그래프 내의 정점의 수를 |V|, 간선의 수를 |E|라 했을 때, 각 간선을 한 번씩 보게 되고, dist값이 변하면 우선순위 큐에서의 순서가 계속 바뀌게 될 수도 있으므로, 간선의 수 * 우선순위 큐 이용 시간복잡도인 O(|E|log|V|)가 소요됩니다.
• 만약 우선순위 큐를 이용하지 않고, for문을 이용해 최솟값을 찾는 식으로 코드를 구현한다면, 최솟값에 해당하는 노드를 고르는 데 |V|시간이 소요되고 이 과정을 총 |V|번 반복해야 모든 노드를 선택하게 되므로, 시간복잡도는 O(|V|^2)이 됩니다.
  • 만약 그래프에 간선이 굉장히 많은 경우라면, E=V^2이 되므로, 이런 경우라면 우선순위 큐를 이용하지 않는 것이 더 유리합니다.

 

크루스칼 vs 프림

크루스칼	프림
배열 이용	우선순위 큐 이용
가중치가 가장 작은 간선에서 시작	아무 정점에서나 시작
사이클 만들어질 수 있으므로, 간선별로 확인 필요	사이클 만들어질 걱정 필요 없음 (MST에 포함되지 않은 정점에 대해서만 동작하기 때문)
두 알고리즘으로부터 구한 MST의 가중치 합은 동일함

 

---