그래프 알고리즘 정리

Doyeon·2023년 6월 14일
다익스트라벨만 포드위상정렬유니온파인드최소신장트리플로이드 워셜
0
post-thumbnail

유니온 파인드

  • union 연산 : 특정 2개의 노드를 연결해 1개의 집합으로 합친다.
  • find 연산 : 두 노드가 같은 집합에 속해 있는지 확인한다. 특정 노드 a가 속한 집합의 대표 노드를 반환한다.

언제 사용하는가?

  • 유니온 파인드로 각 노드의 대표 노드를 정리할 수 있고, 정리된 배열을 통해 두 노드가 연결되어 있는지 쉽게 확인할 수 있다.

원리 이해 및 구현

  1. 대표노드를 저장하는 1차원 배열을 선언한다. 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 된다. 

    int[] parent = new int[N+1];
for (int i = 1; i <= N; i++) {
    parent[i] = i;
}

  2. 2개의 노드를 선택하고 각각의 대표 노드를 찾아 연결하는 union 연산을 수행한다.

    private static void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
    }
}

  3. 선택한 노드가 속한 집합의 대표 노드를 찾는 find 연산을 수행한다.

    1. 대상 노드 배열에 index 값과 value 값이 동일한지 확인한다.
    2. 동일하지 않다면 value값이 가리키는 index 위치로 이동한다.
    3. 이동 위치의 index 값과 value 값이 같을 때까지 a, b를 반복한다. (재귀 함수 구현)
    4. 대표 노드에 도달하면 재귀함수를 빠져나오면서 거치는 모든 노드 값을 루트 노드 값으로 변경한다.
    private static int find(int x) {
    if (x == parent[x])
        return x;
    else {
        return parent[x] = find(parent[x]);
    }
}

위상정렬

  • 기능 : 노드 간의 순서를 결정
  • 특징 : 사이클이 없는 방향 그래프에서 사용
  • 시간 복잡도 : O(V+E)

언제 사용하는가?

  • 노드의 순서를 정할 때
  • 출발점에서 도착점까지 임계 경로값을 구할 때
  • 엣지 뒤집기로 임계값에 해당하는 경로를 구할 수 있다.

원리 이해 및 구현

  1. ArrayList로 그래프를 표현한다. 이 때 진입차수(in-degree) 값을 함께 계산한다.

    int N = scan.nextInt();
int M = scan.nextInt();
int[] D = new int[N+1];
ArrayList<Integer>[] adj = new ArrayList[N+1];
for (int i = 1; i <= N; i++) {
    adj[i] = new ArrayList<>();
}

for (int i = 1; i <= M; i++) {
    int x = scan.nextInt();
    int y = scan.nextInt();
    adj[x].add(y);
    D[y]++;
}

  2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다. 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다. 모든 노드가 정렬될 때까지 반복한다.

    Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= N; i++) {
    if (D[i] == 0)
        queue.add(i);
}

while (!queue.isEmpty()) {
    int x = queue.poll();
    System.out.println(x);
    for (int y : adj[x]) {
        D[y]--;
        if (D[y] == 0)
            queue.add(y);
    }
}

다익스트라

  • 기능 : 출발 노드와 모든 노드 간 최단 거리 탐색
  • 특징 : 에지는 모두 양수
  • 시간 복잡도 : O(ElogV)

언제 사용하는가?

  • 출발 노드와 이외의 모든 노드 간의 최단 거리가 필요할 때
  • K번째 최단 경로 구하기
    • 최단 경로를 표현하는 배열을 우선순위 큐 배열로 변경한다.
    • K번째 경로를 찾기 위해 노드를 여러 번 쓰는 경우가 생기기 때문에 사용한 노드를 방문 배열에 표시하는 부분은 삭제한다.

원리 이해 및 구현

  1. 인접 리스트로 그래프를 구현한다. 연결한 배열의 자료형은 (노드, 가중치)와 같은 형태로 선언한다.

    class Node {
    int targetNode;
    int value;

    public Node(int targetNode, int value) {
        this.targetNode = targetNode;
        this.value = value;
    }
}
    int V = scan.nextInt();
int E = scan.nextInt();
int K = scan.nextInt();

ArrayList<Node> adj = new ArrayList[V+1];
for (int i = 1; i <= V; i++) {
    adj[i] = new ArrayList<>();
}

for (int i = 1; i <= E; i++) {
    int from = scan.nextInt();
    int to = scan.nextInt();
    int d = scan.nextInt();
    adj[from].add(new Node(to, d));
}

  2. 최단 거리 배열을 초기화한다. 출발 노드는 0, 이외의 노드는 무한(적당히 큰 값)으로 초기화한다.

    int[] dist = new int[V+1];
for (int i = 1; i <= V; i++) {
    dist[i] = 3000001;
}
dist[K] = 0;

  3. 값이 가장 작은 노드를 고른다. 값이 0인 출발 노드에서 시작한다.

    PriorityQueue<Node> pq = new PriorityQueue<>((Comparator.comparingInt(o -> o.value)));
pq.add(new Node(K, 0));

  4. 최단 거리 배열을 업데이트한다. 현재 선택된 노드에 연결된 에지들을 탐색하고 업데이트한다.

    Min(선택(출발) 노드의 최단 거리 배열의 값 + 에지 가중치, 연결(도착) 노드의 최단 거리 배열의 값)

    if (dist[now.targetNode] + next.value < dist[next.targetNode]) {
    dist[next.targetNode] = dist[now.targetNode] + next.value;
    pq.add(new Node(next.targetNode, dist[next.targetNode]));
}

  5. 과정 3~4를 반복해 최단 거리 배열을 완성한다. 과정 4에서 이미 선택했던 노드가 다시 선택되지 않도록 방문 배열을 만들어 처리하고, 모든 노드가 선택될 때까지 반복한다.

    while (!pq.isEmpty()) {
    Node now = pq.poll();
    if (visit[now.targetNode]) continue;
    visit[now.targetNode] = true;
    for (Node next : adj[now.targetNode]) {
        if (dist[now.targetNode] + next.value < dist[next.targetNode]) {
            dist[next.targetNode] = dist[now.targetNode] + next.value;
            pq.add(new Node(next.targetNode, dist[next.targetNode]));
        }
    }
}

벨만-포드

  • 기능 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
  • 특징 : 음수 가중치 에지가 있어도 수행할 수 있음. 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음.
  • 시간 복잡도 : O(VE)

언제 사용하는가?

  • 최단 거리를 구할 수 있는 그래프인지 확인(음수 사이클이 존재하는지 확인)
  • 양수 사이클이 존재하는지 확인할 때도 사용할 수 있음 → 이 때는 에지의 업데이트를 N-1 번이 아닌, 충분히 큰 수 만큼 추가로 돌려야 한다. 에지 사용 횟수가 N-1을 넘어선 이후 갱신되면 양수 사이클에 연결 되어 있다는 의미이므로 거리 배열 값을 MAX로 갱신한다.

원리 이해 및 구현

  1. 에지 리스트로 그래프를 구현하고 최단 경로 배열을 초기화한다. 최단 경로 배열의 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.

    int N = scan.nextInt();
int M = scan.nextInt();
Edge[] edgeList = new Edge[M+1];
long[] dist = new long[N+1];

for (int i = 1; i <= M; i++) {
    int A = scan.nextInt();
    int B = scan.nextInt();
    int C = scan.nextInt();
    edgeList[i] = new Edge(A, B, C);
}

dist[1] = 0;
for (int i = 2; i <= N; i++) {
    dist[i] = Integer.MAX_VALUE;
}

  2. 모든 에지를 확인하여 정답 배열을 업데이트한다. 노드 개수가 N이고, 음수 사이클이 없을 경우 특정 두 노드의 최단 거리를 구성하는 에지의 최대 개수는 N-1이므로, 최단 거리 배열 업데이트 반복 횟수는 N-1이다.

    • 업데이트 조건 : D[s] ≠ ∞ 이며, D[e] > D[s] + w 일 때, D[e] = D[s] + w 로 업데이트
    for (int i = 1; i <= N-1; i++) {
    updateDistance();
}

private static void updateDistance() {
    for (int i = 1; i <= M; i++) {
        int S = edgeList[i].start;
        int E = edgeList[i].end;
        int W = edgeList[i].weight;
        if (dist[S] != Integer.MAX_VALUE && dist[E] > dist[S] + W) {
            dist[E] = dist[S] + W;
        }
    }
}

  3. 음수 사이클 유무를 확인한다. 모든 에지를 한번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인한다. 만약 업데이트되는 노드가 있다면 음수 사이클이 있다는 뜻이며, 최단 거리를 찾을 수 없는 그래프이다.

    for (int i = 2; i <= N; i++) {
    if (lastDist[i] != dist[i]) {
        System.out.println("음수 사이클 존재"); 
        return;
    }
}

플로이드-워셜

  • 기능 : 모든 노드 간에 최단 경로 탐색
  • 특징 : 음수 가중치 에지가 있어도 수행 가능. DP를 이용해 알고리즘 접근
  • 시간 복잡도 : O(V^3)

언제 사용하는가?

  • 모든 노드 간 최단 거리를 알 수 있다. 다만, 시간 복잡도가 빠르지 않은 편이므로, 일반적으로 노드의 개수가 적을 때 사용한다.
  • A노드 → B노드로 가는 경로가 존재하는지 확인할 때
    • distance[S][K] == 1 && distance[K][E] == 1 이라면, distance[S][E] = 1

원리 이해 및 구현

  1. 최단 거리 배열을 선언하고 초기화한다. S == E 인 경우는 0, 다른 경우는 ∞로 초기화한다.

    int N = scan.nextInt();
int M = scan.nextInt();
long D = new long[N+1][N+1];

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        if (i == j) {
            D[i][j] = 0;
        } else {
            D[i][j] = Integer.MAX_VALUE;
        }
    }
}

  2. 최단 거리 배열에 그래프 데이터를 저장한다. D[S][E] = W로 에지 정보를 배열에 저장한다.

    for (int i = 1; i <= M; i++) {
    int a = scan.nextInt();
    int b = scan.nextInt();
    long c = scan.nextLong();
    if (D[a][b] > c) {
        D[a][b] = c;
    }
}

  3. 점화식을 3중 ofr 문 형태로 반복하면서 배열을 업데이트한다.

    for (int k = 1; k <= N; k++) {
    for (int s = 1; s <= N; s++) {
        for (int e = 1; e <= N; e++) {
            D[s][e] = Math.min(D[s][e], D[s][k] + D[k][e]);
        }
    }
}

최소 신장 트리

  • 최소 신장 트리 : 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치 합을 최소로 하는 트리
  • 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.
  • N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개다.

원리 이해 및 구현

  1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열을 초기화한다.

    int V = scan.nextInt();
int E = scan.nextInt();
PriorityQueue<Edge> edges = new PriorityQueue<>();

for (int i = 0; i < E; i++) {
    int s = scan.nextInt();
    int e = scan.nextInt();
    int v = scan.nextInt();
    edges.add(new Edge(s, e, v));
}

  2. 에지 리스트에 담긴 그래프 데이터를 가중치 기준 오름차순 정렬한다.

    class Edge implements Comparable<Edge>{
    int start;
    int end;
    int value;

    public Edge(int start, int end, int value) {
        this.start = start;
        this.end = end;
        this.value = value;
    }

    @Override
    public int compareTo(Edge o) {
        return this.value - o.value;
    }
}

  3. 가중치가 낮은 에지부터 순서대로 선택해 연결을 시도한다. 에지를 연결했을 때, find 연산을 이용해 사이클 형성 유무를 확인한 후, 사이클이 형성되지 않을 때만 union 연산으로 두 노드를 연결한다.

    int[] parent = new int[V+1];
for (int i = 1; i <= V; i++) {
    parent[i] = i;
}

if (find(s) != find(e)) {
    union(s, e);
    ans += edge.value;
    useEdge++;
}

private static void union(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        parent[b] = a;
    }
}

private static int find(int x) {
    if (x == parent[x]) {
        return x;
    } else {
        return parent[x] = find(parent[x]);
    }
}

  4. 전체 노드의 개수가 N개이면 연결한 에지의 개수가 N-1이 될 때까지 과정 3을 반복한다.

    int ans = 0;
int useEdge = 0;
while (useEdge < V - 1) {
    Edge edge = edges.poll();
    int s = edge.start;
    int e = edge.end;
    if (find(s) != find(e)) {
        union(s, e);
        ans += edge.value;
        useEdge++;
    }
}

  5. 에지의 개수가 N-1이 되면 완성된 최소 신장 트리의 총 에지 비용을 출력한다.

profile
Doyeon
🔥
이전 포스트

[ParkNav] 비관적락, 스핀락, 분산락 성능 테스트

다음 포스트

SpringBoot 프로젝트에서 성능 향상을 위한 Redis Cache 적용하기

0개의 댓글