비선형 자료구조 Graph

그래프란,

객체의 일부 쌍(Pair)들이 '연관되어' 있는 객체 집합 구조를 말한다.

그래프 이론에서 ‘그래프’는 수학적 구조를 의미하며, 이는 객체 간의 관계를 나타내는 도구다.

 

• 그래프는 두 가지 주요 구성 요소로 이루어져 있다.
  • 정점 (Vertices): 그래프의 기본 단위. 각 정점은 그래프에서 고유한 객체나 노드를 나타낸다.
  • 간선 (Edges): 정점 간의 연결을 나타낸다. 간선은 두 정점을 연결하여 그들 간의 관계를 나타낸다.

• 그래프는 여러 종류로 나뉘며, 각각의 종류는 특정한 특성과 용도를 가진다
  • 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프다.
    예를 들어, 두 정점 A와 B를 연결하는 간선이 있다면, A에서 B로 또는 B에서 A로 이동할 수 있다.
  • 방향 그래프 (Directed Graph, Digraph): 간선에 방향이 있는 그래프다. 
    예를 들어, A에서 B로 향하는 간선이 있다면, B에서 A로 이동할 수 없다.
  • 가중치 그래프 (Weighted Graph): 간선에 가중치 또는 비용이 할당된 그래프다.
    예를 들어, 도로 네트워크에서 도로의 길이나 비용을 나타낼 수 있다.
  • 부분 그래프 (Subgraph): 주어진 그래프의 일부 정점과 간선으로 구성된 그래프다.

• 그래프의 표현
  • 인접 행렬 (Adjacency Matrix): 정점 간의 연결 관계를 행렬 형태로 표현한다.
    행렬의 행과 열은 정점을 나타내며, 특정한 위치의 값은 해당 정점 간의 간선을 나타낸다.
  • 인접 리스트 (Adjacency List): 각 정점에 대한 연결된 정점들의 리스트로 그래프를 표현합니다. 이는 일반적으로 메모리 효율적인 방식입니다.

 

인접 행렬과 인접 리스트의 예시

다음과 같은 무방향 그래프가 있다면,
    A
   / \
  B---C
   \ / 
    D

'인접행렬'을 아래와 같이 표현할 수 있다.

'
   A B C D
A [0 1 1 0]
B [1 0 1 1]
C [1 1 0 1]
D [0 1 1 0]
'

 이는 그래프의 정점간의 연결 관계를 2차원 배열(행렬)로 나타낸 것이다.
각 행과 열은 그래프의 정점을 나타낸다. 
특정 정점 간의 간선이 존재하면 해당 위치에 1(또는 가중치)로 표시하고, 
존재하지 않으면 0으로 표시한다.


위 그래프를 '인접 리스트'로 표현하면 아래와 같다.
'
A: B, C
B: A, C, D
C: A, B, D
D: B, C
'

 

 

그래프 순회

 그래프 순회(Graph Traversal)란 그래프 탐색(Grapgh Search)이라고도 하며 그래프의 각 정점을 방문하는 과정을 말한다. 방문 과정에는 크게 깊이 우선 탐색(Depth-First Search, DFS)과 너비 우선 탐색(Breadth-First Search, BFS) 두가지 알고리즘이 있다.

 

DFS

 깊이 우선 탐색(Depth-First Search, DFS)은 그래프나 트리 자료 구조를 탐색하는 데 사용되는 알고리즘이다. DFS는 가능한 한 깊게 탐색한 후, 더 이상 깊게 탐색할 수 없으면 이전 노드로 돌아가서 다시 깊게 탐색을 진행하는 방식으로 작동한다.

• 시작 노드에서 출발: 탐색은 시작 노드에서 시작합니다. (트리에서는 일반적으로 root 노드에서 탐색을 시작한다.)
  
  • 아래와 같은 트리가 있다면, 0이 root가 된다.
          0
         /  \
       1     2
      /   \     \
    3     4    5
    DFS를 통해 '0 -> 1 -> 3 -> 4 -> 2 -> 5' 와 같이 탐색할 수 있다.
    
    
  • 아래와 같은 그래프가 있다면, DFS를 어느 노드에서든 시작할 수 있다. 그래프는 사이클이 있을 수도 있고, 방향성이 있을 수도 있다.
    0 --- 1 --- 3
     |        |
    2       4
    여기서 0 노드에서 DFS를 시작하면 다음과 같이 탐색할 수 있다.
    '0 -> 1 -> 3 -> 4 -> 2'
    또 다른 예로, 2 노드에서 DFS를 시작하면 다음과 같이 탐색할 수 있다.
    '2 -> 0 -> 1 -> 3 -> 4'
    
    
• 방문 표시: 각 노드를 방문할 때마다 방문했음을 표시한다.
• 깊이 탐색: 현재 노드에서 갈 수 있는 노드 중 하나를 선택하여 탐색을 계속 진행한다.
• 백트래킹: 더 이상 방문할 노드가 없으면, 이전 노드로 돌아가서 다른 경로를 탐색한다.
• 반복: 모든 노드를 방문할 때까지 위 과정을 반복한다.

 

재귀적 DFS 구현
출력 결과는 '0 1 3 4 2 5 '가 된다.

import java.util.*;

public class RecursiveDFS {
    private Map<Integer, List<Integer>> graph = new HashMap<>();
    private Set<Integer> visited = new HashSet<>();

    public void dfs(int node) {
        visited.add(node);
        System.out.print(node + " ");

        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor);
            }
        }
    }

    public static void main(String[] args) {
        RecursiveDFS dfs = new RecursiveDFS();
        dfs.graph.put(0, Arrays.asList(1, 2));
        dfs.graph.put(1, Arrays.asList(3, 4));
        dfs.graph.put(2, Arrays.asList(5));
        dfs.graph.put(3, Arrays.asList());
        dfs.graph.put(4, Arrays.asList());
        dfs.graph.put(5, Arrays.asList());

        System.out.println("DFS Start");
        dfs.dfs(0);
    }
}

• 그래프 및 방문한 노드 집합
  • graph는 인접 리스트를 저장하기 위한 Map이다. 각 키는 노드이며, 값은 해당 노드에 연결된 인접 노드의 리스트이다.
  • visited는 방문한 노드를 추적하는 Set이다.

 

• DFS 메소드
  • dfs(int node): 현재 노드를 방문하고 인접한 노드들을 재귀적으로 탐색한다.
  • 현재 노드를 방문한 것으로 표시하고, visited에 추가한다.
  • 인접 노드 리스트를 순회하면서, 아직 방문하지 않은 인접 노드에 대해 재귀적으로 dfs를 호출한다.

 

• 메인 메소드
  • 그래프를 초기화합니다. 각 노드와 그에 인접한 노드를 graph에 추가한다.
  • DFS 탐색을 시작. 노드 0에서 탐색을 시작.

 

DFS는 그래프 탐색에서 중요한 알고리즘으로, 경로 찾기, 사이클 검출, 위상 정렬 등의 다양한 응용에서 사용된다.

 

 

BFS

 너비 우선 탐색은 그래프 탐색 알고리즘으로, 시작 노드에서부터 인접한 노드를 모두 방문한 후, 그 다음 레벨의 노드를 방문하는 방식이다.
BFS는 주로 최단 경로 문제를 해결하는데 사용된다.

 

BFS의 특징

1. 계층적 탐색: 현재 노드와 인접한 모든 노드를 먼저 방문하고, 그 다음 레벨로 넘어갑니다.
2. 큐(Queue)를 사용: 방문할 노드들을 저장하고, FIFO(First-In-First-Out) 방식으로 처리합니다.
3. 최단 경로 보장: BFS는 무방향 그래프나 가중치가 동일한 그래프에서 최단 경로를 보장합니다.

 

BFS의 동작 방식

1. 시작 노드를 큐에 추가: 시작 노드를 방문했다고 표시하고, 큐에 추가합니다.
2. 큐가 비어있지 않으면 반복
   1. 큐에서 노드를 하나 꺼냅니다.
   2. 해당 노드와 인접한 노드들 중 방문하지 않은 노드들을 모두 큐에 추가하고, 방문했다고 표시합니다.
3. 모든 노드를 방문할 때까지 반복.

 

BFS의 구현

import java.util.*;

public class BFS {
    private Map<Integer, List<Integer>> graph = new HashMap<>();
    private Set<Integer> visited = new HashSet<>();

    public void bfs(int startNode) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startNode);
        visited.add(startNode);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        BFS bfs = new BFS();
        bfs.graph.put(0, Arrays.asList(1, 2));
        bfs.graph.put(1, Arrays.asList(3, 4));
        bfs.graph.put(2, Arrays.asList(5));
        bfs.graph.put(3, Arrays.asList());
        bfs.graph.put(4, Arrays.asList());
        bfs.graph.put(5, Arrays.asList());

        System.out.println("BFS 시작:");
        bfs.bfs(0); // 노드 0에서 BFS 시작
    }
}

그래프 및 방문한 노드 집합

• graph: 각 노드와 그에 인접한 노드를 저장하는 Map.
• visited: 방문한 노드를 추적하는 Set.

 

BFS 메소드

• bfs(int startNode): 시작 노드에서 BFS 탐색을 시작합니다.
• queue: 다음에 방문할 노드를 저장하는 큐.
• 시작 노드를 큐에 추가하고, 방문한 것으로 표시합니다.
• 큐가 비어 있지 않은 동안
  • 큐에서 노드를 꺼내서 출력.
  • 인접한 노드들 중 방문하지 않은 노드를 큐에 추가하고 방문한 것으로 표시.

 

메인 메소드

• 그래프를 초기화하고, 각 노드와 그에 인접한 노드를 graph에 추가합니다.
• BFS 탐색을 시작합니다. 여기서는 노드 0에서 탐색을 시작합니다.

 

 

- NP: nondeterministic polynomial time, 비결정론적 다항식 시간

- 오일러 경로

 1735년 오일러는 모든 정점이 짝수 개의 차수(Degree)를 갖는다면 모든 다리를 한 번씩만 건너서 도달하는 것이 성립한다고 말했다.

이후 1873년 독일의 수학자 칼히어홀저(Carl Hierholzer)가 수학적으로 증명해낸다. 이를 오일러의 정리(Euler's Theorem)라 한다.

아울러 모든 간선을 한 번씩 방문하는 유한 그래프(Finite Graph)를 일컬어 오일러 경로(Eulerian Trail / Eulerian Path)라 부른다.

 

- 해밀턴 경로

 해밀턴 경로는 각 정점을 한 번씩 방문하는 방향이 없는 또는 방향이 있는 그래프 경로를 말한다. 오일러 경로가 간선을 기준으로 한다면 해밀턴 경로는 정점을 기준으로 한다. 오일러 경로와 달리 해밀턴 경로는 최적 알고리즘이 없는 NP-완전(NP-Complete) 문제로 대표적인 난제 중 하나다. NP 문제중 NP-난해(NP-Hard)인 문제를 NP-완전 문제라 한다.

 

해밀턴 경로 중에서도 원래의 출발점으로 돌아오는 경로를 해밀턴 순환(Hamiltonian Cycle)이라 하는데, 이 중에서도 최단 거리를 찾는 문제는 알고리즘 분야에서는 외판원 문제(Travelling Salesman Problem, 약어: TSP)로 유명하다.

 

- 외판원 문제

 외판원 문제는 다이나믹 프로그래밍 기법을 활용하면 좀 더 최적화할 수 있다.

이 경우 O(n^2*2^n)으로 최적화 할  수 있는데, n!(약 240경, Brute force풀이)에 비해 적은 값인 419,430,400의 값이 나올 수 있다.

 

- DFS 재귀적 구현과 스택을 사용한 구현의 장단점 비교

재귀적 구현

장점

• 간결하고 직관적: 재귀적 DFS는 코드가 간결하다.
• 그래프 탐색의 논리를 그대로 표현하기 때문에 이해하기 쉽다.
• 자연스러운 함수 호출 스택 이용: 재귀 호출은 함수 호출 스택을 이용해 스택 자료 구조를 암묵적으로 사용한다

 

단점

• 스택 오버플로우 위험: 깊이가 매우 깊은 그래프를 탐색할 경우 재귀 호출이 너무 많이 일어나 스택 오버플로우가 발생할 수 있다.
• 디버깅 어려움: 재귀 호출이 많아질 경우 디버깅이 어려울 수 있다.

 

스택을 이용한 구현

장점

• 스택 오버플로우 위험 없음: 명시적으로 스택을 사용하기 때문에, 스택의 크기를 제어할 수 있다.
• 메모리 사용량 조절 가능: 스택의 크기를 제어할 수 있어 메모리 사용량을 조절할 수 있습니다.
• 반복적 구조로 디버깅 용이: 반복적 구조로 구현되어 디버깅이 상대적으로 쉽습니다.

 

단점

• 코드가 길어짐: 재귀적 구현보다 코드가 길고 복잡할 수 있습니다.
• 명시적 스택 관리 필요: 스택을 직접 관리해야 하므로 코드가 다소 복잡해질 수 있습니다.