1. 그래프 순회

그래프 순회(traversal)은 모든 정점(Node)를 방문하는 작업을 말합니다.
대표적으로 깊이 우선 탐색(DFS: Depth First Search)와 너비 우선 탐색(BFS: Breath First Search)방식이 있는데요. 둘 다 그래프에서 최단 경로를 찾는 노드 기반 알고리즘 입니다.

2. 깊이 우선 탐색 (DFS)

말 그대로 깊은 곳부터 탐색을 진행하는 방식입니다.

트리의 전위순회와 유사한 방식을 따릅니다.

1. 특정 노드에서 시작하여 간선을 따라 자식 노드를 방문합니다.
2. 더 이상 탐색할 자식 노드가 없으면 역추적을 통해 이전 노드로 이동하면서 탐색하지 않은 간선이 있는지 확인합니다.
3. 탐색 가능한 간선이 있다면 다시 간선을 따라 다음 노드로 이동합니다.
4. 모든 노드를 방문할 때까지 이를 반복합니다.

재귀 알고리즘이나 인접 리스트와 스택을 활용하여 쉽게 구현할 수 있습니다.

1) 재귀(Recursive) 알고리즘

public static void dfs(int start) {
        visited[start] = true;

        // 필요하다면 오름차순 정렬
        // graph[start].sort(Comparator.naturalOrder());
        
        for (int node : graph[start]) {
            if(!visited[node]) { // 인접 노드를 방문한 적 없다면 DFS 진행
                dfs(node);
            }
        }
}

2) Stack 자료구조 사용

1. 시작 노드를 스택에 push합니다.
2. 스택을 pop해서 맨 위에 있는 노드를 방문 처리합니다. (visited 배열을 활용)
3. 그 노드에서 방문하지 않은 인접 노드를 스택에 push합니다.
4. 스택이 빌 때까지 이를 반복합니다.

public static void dfs(int start) {
		Stack<Integer> stack = new Stack<>();
        
		stack.push(start);
        visited[start] = true;
        
        while (!stack.isEmpty()) { // 스택이 빌 때까지 반복
        	int node = stack.pop();
            for (int neighbor : graph[node]) {
            	if(!visited[neighbor]) { // 인접 노드를 방문한 적 없다면 Stack에 push
                   stack.push(neighbor);
                   visited[neighbor] = true;
                }
            }
        }
}           

이때 시간 복잡도는 V가 노드의 수, E가 간선의 수 일 때 O(V + E) 입니다.

3. 너비 우선 탐색 (BFS)

말 그대로 같은 레벨에 있는 노드를 따라 옆으로 탐색을 진행하는 방식입니다.

레벨은 시작 정점에서의 거리를 의미합니다.

1. 레벨 0에 있는 한 노드에서 시작합니다.
2. 먼저 레벨 1에 있는 모든 노드를 방문합니다.
3. 이어서 다음 레벨에 있는 모든 노드를 방문합니다.
4. 모든 노드를 방문할 때까지 이를 반복합니다.

이는 큐(Queue) 자료구조를 활용하여 쉽게 구현할 수 있습니다.

1) Queue 자료구조 활용

1. 모든 노드를 방문하지 않은 상태로 설정합니다. (visited 배열을 활용)
2. 시작 노드를 방문하여 방문 처리한 뒤 큐에 삽입합니다.
3. 큐에서 첫 번째 노드를 제거하고 그 정점에서 방문하지 않은 인접한 정점을 방문하여 방문 처리한 뒤 큐에 삽입합니다.
4. 인접한 정점이 없는 경우 큐에서 첫 번째 정점을 빼옵니다.
5. 큐가 빌 때까지 이를 반복합니다.

 public static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        
        visited[start] = true;
        q.add(start);

        while (!q.isEmpty()) {
            int node = q.poll();
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.add(neighbor);
                }
            }
        }
 }

이때 시간 복잡도는 V가 노드의 수, E가 간선의 수 일 때 O(V + E) 입니다.

사진 출처: DFS vs BFS Algorithms for Graph Traversal