[자료구조] 그래프(Graph) 정리

유튜브 바킹독 알고리즘 강의와 자바 알고리즘 인터뷰 책을 참고하여 정리한 글입니다. 자세한 내용은 해당 자료를 보시면 도움이 될 것입니다.

---

1. 그래프 정의

1) 기본 정의

• 정점과 간선으로 이루어진 자료구조
• 차수: 각 정점에 대해 간선으로 연결된 이웃된 정점의 갯수

 

2) 방향성

• 간선의 방향성이 있으면 방향 그래프, 없으면 무방향그래프라고 한다.
• 방향그래프에서 차수는 진입차수(indegree), 진출차수(outdegree)가 있다.

3) 사이클

• 그래프 내에 사이클(순환)이 하나라도 존재하면 순환 그래프, 아예 존재하지 않으면 비순환그래프라고 한다.
• 오른쪽 그림의 경우, 순환그래프처럼 보이지만 간선의 방향성을 고려하면 사이클이 없다고 판단해야 한다.

4) 그 외

• 완전 그래프(Complete Graph) : 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프
• 연결 그래프(Connected Graph) : 임의의 두 정점 사이에 경로가 항상 존재하는 그래프

 

5) 주의

문제에서 그래프의 정의가 엄밀하게 주어지지 않는다면, 더욱 주의해야 한다.
그래프 분리, 같은 간선 여러 개, 루프 존재 등 다양한 경우의 수를 고려하여 문제를 올바르게 풀 수 있어야 한다.

 

 

• 그래프는 꼭 연결되어 있을 필요가 없다.
• 두 정점 사이의 간선이 반드시 1개 이하일 필요가 없다.
• 간선이 서로 다른 두 정점을 연결해야 할 필요도 없다.
• 자기 자신으로 간선이 연결된 경우를 루프(loop)라고 한다.
• 참고) 단순 그래프(simple graph): 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

 

2. 그래프 표현법

전제: 정점이 V, 간선이 E개

무방향그래프일 때는 양쪽 정점 모두 값을 넣어줘야하는 것을 주의하자.

1) 인접행렬

• 특정 정점 I, J 가 연결되어 있는지를 확인: O(1)
• 특정 정점과 연결되어 있는 모든 정점을 확인: O(V)
• 공간 복잡도: O(V∗V)
• 무방향 그래프일 경우, 대각선을 기준으로 대칭적으로 값이 입력된다.

2) 인접리스트

• 정점이 많고 간선이 상대적으로 적은 상황에서 인접 행렬보다 공간을 절약할 수 있다.
• V개의 리스트를 만들어 각 리스트에 자신과 연결된 정점을 넣는 방식

 

• 특정 정점 I, J 가 연결되어 있는지를 확인: O(min(degree(I),degree(J)))
  • 더 작은 연결/차수(degree)를 지닌 정점리스트 확인
• 특정 정점(X)과 연결되어 있는 모든 정점을 확인:O(degree(X))
• 공간 복잡도: O(V+E)

 

3) 정리

 

• 대부분의 알고리즘들에서는 전부 특정 정점에 연결된 모든 정점을 확인하는 작업이 반복적으로 등장하여 인접리스트 방식으로 구현하는 경우가 많다.
• 다만, 입력 자체가 인접행렬 느낌으로 주어지거나 V가 많이 작아 구현의 편의를 챙기고자 하거나, 최단경로 알고리즘 중 하나인 플로이드 알고리즘을 쓸 때에는 인접행렬로 그래프로 나타내는 경우가 있을 수 있다.

 

3. BFS

1) 정의

• 그래프에서 너비를 우선으로 방문하는 알고리즘
• 큐를 이용해 구현
• 최단 경로 알고리즘인 다익스트라에서도 유용하게 쓰인다.

2) 동작 방식과 시간복잡도

2-1) 동작 방식

이후 다룰 DFS 스택방식과 달리 큐에 넣는 순간 방문표시를 합니다!

1. 시작하는 정점을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 정점을 꺼낸 후, 그 정점과 연결된 모든 정점들에 대해 3번을 진행
   • 다차원 배열, 인접리스트 고려
3. 해당 연결 정점을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복

2-2) 시간복잡도

모든 정점이 큐에 최대 1번씩 들어가므로

• 인접리스트: O(V+E)
  • 무방향그래프: 2E, 방향그래프: E
  • ex. V = 2000개일 때, BFS 1000번 돌리는 경우)
    - E(간선의 수(는 약 2백만개(2000*(2000-1) / 2)
    - 시간복잡도: O(1000*V)가 아니라 O(1000*(V+E))이므로 시간초과가 나므로 주의해야 한다.
• 인접행렬: O(V^2)

 

3) BFS 활용

• 모든 간선의 길이가 동일한 상황(가중치가 동일)에서 두 지점 사이의 최단 경로(거리)를 구할 때 사용될 수 있다.
• 하지만 만약 모든 간선의 길이가 다르다면 플로이드 or 다익스트라같은 다른 알고리즘을 사용해야 한다.

3-1) 연결그래프에서의 순회 (인접리스트)

• vis 배열 선언 및 표시 시점 주의
  • 큐에 넣을 때 방문표시 한다.

 

3-2) 연결그래프에서 1번 정점과의 거리

• dist배열 선언
• dist배열의 초기값을 -1로 해놓으면 vis배열 별도 지정 없이도 구현 가능

3-3) 연결 그래프가 아닐 때 순회

• for문을 돌며 아직 방문하지 않은 정점을 찾아 그 정점을 시작 정점으로 하는 bfs 수행

 

 

 

 

4. DFS

1) 정의

• 그래프에서 깊이를 우선으로 방문하는 알고리즘
• 스택 혹은 재귀로 구현할 수 있다.
• 재귀로 구현할 경우, 사전식 순서로 정점을 방문하는 반면 스택으로 방문할 경우 역순으로 방문한다.
  • 스택의 경우 인접 노드에서 가장 최근에 담긴 노드, 즉 가장 마지막부터 방문하기 때문

2) 동작 방식과 시간복잡도

2-1) 재귀 

재귀 메서드

1. 현재 노드를 저장한다. (전위 순회)

2. 주변 노드를 탐색하면서 아직 방문 처리되지 않은 노드라면 재귀 호출(깊이 기반 탐색)을 한다. 

 

2-2) 스택을 이용한 반복 구조

사람마다 방문 표시 시점을 언제 하느냐가 조금씩 다른데 저는 스택에 넣을 때 말고, 스택에서 꺼냈을 때 (실제 방문했을 때) 방문표시 하는 방식을 채택하였습니다. 재귀 방식도 실제로 방문했을 때 방문 표시를 함. 

바킹독 강의 방식과 다름. 자바 알고리즘 인터뷰 책 참고함
개인적으로 이 방식을 이용하면 스택을 이용해서 재귀 방식처럼 방문 시점을 실제로 방문했을 때 기록하도록 할 수 있고, 헷갈리지 않더라. 이 방식을 이용하면 바킹독 뒷 부분 내용이 필요 없어서 생략함.

물론, 역순으로 정점을 방문하지 않게 하려면 별도로 인접 정점 인덱스를 역순으로 스택에 넣도록 해야 합니다.

1. 시작하는 정점을 스택에 넣는다. (그냥 넣기만 함)
2. 스택에서 정점을 꺼내어 이전에 방문했는지 체크
3. 꺼낸 정점이 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 주변 노드를 모두 스택에 삽입
4. 스택이 빌 때까지 2번을 반복

 

2-3) 시간복잡도

BFS와 같이 모든 정점이 스택에 최대 1번씩 들어가므로

• 인접리스트: O(V+E)
• 인접행렬: O(V^2)

 

 

3) DFS 활용

3-1) 연결 그래프에서의 순회, 재귀

• 재귀 이용
  • 스택보다 코드를 훨씬 짧고 우아하게 쓸 수 있다. 또한 백트래킹에서도 효용이 크므로 활용이 큰 편이다. 
  • 그러나 재귀를 이용할 경우 코드는 간결해지지만, 메모리의 스택 영역에 계속 데이터가 쌓인다.
  • 온라인 저지 사이트에서 스택 메모리 제한이 작게 걸린 경우 초과가 날 수 있다. (백준은 스택메모리 제한 없음)
  • 주최측에서 이를 잘 처리해주는 것이 좋지만, 시험 환경은 어떻게 될지 모르니 구현할 때 깊이가 깊어지면 문제가 있을 수 있음을 인지하자. 처음 사용하는 플랫폼에서 코딩테스트를 진행한다면 이 부분을 코딩테스트 전에 꼭 확인하자. 

 

3-2) 연결 그래프에서의 순회, 비재귀 (스택)

 

4) 주의! 재귀 DFS와 비재귀 DFS의 동작 차이

 

• 재귀적인 방식과 비재귀(스택)적인 방식을 이용할 때 방문순서가 다르다는 것을 유의하자.
  • 재귀: 사전식 
  • 비재귀(스택):  역순

• 비재귀 DFS는 순회를 잘 수행하지만 엄밀히 말해 우리가 관념적으로 생각하는 DFS와 방문순서가 다르다.
• 단순히 Flood Fill 내지는 순회를 하는 것이 아니라 DFS의 고유한 성질을 사용해 문제를 풀어야 할 경우 비재귀 코드를 그냥 이용하면 안된다. 

 

 

5. 그래프 기본 문제 풀이 

• 백준 1260 DFS와 BFS 풀이
• bfs, dfs 비재귀(방문순서는 재귀방식과 일치하게 구현), dfs 재귀로 풀어보는 기본 문제 풀이
• 정점 순서가 오름차순이어야하므로 미리 정렬을 해둔다.
• 인접리스트의 경우 리스트 초기화, 무방향일 때 양방향으로 입력 주의

package graph;

import java.io.*;
import java.util.*;

public class boj_1260_DFS와BFS {
    static int N,M,V;
    static ArrayList<Integer>[] adList;
    static StringBuilder bfsAns, dfsAns, dfsRans;
    static boolean[] vis;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        adList = new ArrayList[N+1];
        for (int i = 0; i <= N; i++) {
            adList[i] = new ArrayList<>();
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            adList[s].add(e);
            adList[e].add(s);
        } 

        // ** 번호가 작은 것부터 방문하기 위해 정렬하기
        for (int i = 1; i <= N; i++) {
            Collections.sort(adList[i]);
        }


        bfsAns = new StringBuilder();
        dfsAns = new StringBuilder();
        dfsRans = new StringBuilder();

        vis = new boolean[N+1];
        dfs(V);
        vis = new boolean[N+1];
        dfsR(V);
        vis = new boolean[N+1];
        bfs(V);

        System.out.println(dfsAns.toString());
        System.out.println(dfsRans.toString());
        System.out.println(bfsAns.toString());
        
    }

    // 재귀 방식 dfs
    private static void dfsR(int x) {
        int cur = x;
        vis[cur] = true;
        dfsRans.append(cur).append(" ");
        for(int c : adList[cur]) {
            if (vis[c]) {
                continue;
            }
            dfsR(c);
        }
    }

    // 비재귀(stack)방식 + 재귀 방문순서 유지 dfs
    private static void dfs(int x) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(x);

        // 재귀와 같은 동작방식 유지를 위해 stack에서 꺼낼 때 방문표시
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            if (vis[cur]) { 
                continue;
            }
            vis[cur] = true;
            dfsAns.append(cur).append(" ");

            // 스택의 특성상 역순으로 방문하기
            for(int i=adList[cur].size()-1; i >= 0; i--) {
                int nxt = adList[cur].get(i);
                if(vis[nxt]) {
                    continue;
                }
                stack.push(nxt);
            }
        }

    }

    // bfs 방식
    private static void bfs(int x) {
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.offer(x);
        vis[x] = true;
        bfsAns.append(x).append(" ");

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for(int c : adList[cur]) {
                if (vis[c]) {
                    continue;
                }
                queue.offer(c);
                vis[c] = true;
                bfsAns.append(c).append(" ");
            }
        }
    }
}