알고리즘 - DFS, BFS

DFS, BFS

---

DFS, BFS

• 그래프의 탐색 방법이다.

• 시간복잡도는 노드, 엣지의 개수에 영향을 받으며 DFS, BFS 동일하다.
  • 인접 리스트로 구현시 -> O(|v|+|e|)
  • 인접 노드로 구현시 -> O(v^2)

 

DFS - 깊이 우선 탐색

• 재귀적으로 구현한다.

• 모든 노드를 다 탐색해야 최단 거리를 알 수 있으므로 최대 길이, 최대값 등을 찾을때 적합하다. 

• 시작 노드로 부터 한 방향으로 계속 탐색을 진행하다가 더 이상 갈 곳이 없을때 되돌아와서 다른 방향으로 다시 탐색한다.

• 트리의 순회에서 중순위 탐색한 결과와 같다. 

• 구현 with 자바

static void dfs(int[][] node, boolean[] memo, int num) {
    memo[num] = true;
        
    for(int i = 1; i < node.length; i++)    {
        if(node[num][i] == 1 && memo[i] == false) {
            dfs(node, memo, i);
        }
    }
}

 

BFS - 너비 우선 탐색

• 시작 노드로 부터 도착 노드까지의 최단 거리, 최소값 등을 찾을때 적합하다.
• 시작 노드로 부터 가까운 정점을 먼저 방문하고 멀리있는 정점을 나중에 방문하는 방법이다.
• 레벨 순회 하므로 도착노드를 발견하면 해당 거리가 최단 거리이며 더 이상 탐색하지 않아도 된다.
• 트리의 순회에서 레벨 순회 결과와 같다.
• 구현 with 자바

static void bfs(int[][] node, boolean[] memo, int num)    {
    Queue<Integer> queue = new LinkedList<>();
    memo[num] = true;
        
    queue.offer(num);
    while(!queue.isEmpty()) {
        int temp = queue.poll();
            
        for(int i = 1; i < node.length; i++) {
            if(node[temp][i] == 1 && memo[i] == false) {
                memo[i] = true;
                queue.offer(i);
            }
        }
    }
}

트리 구조 순회 이미지

 

 

reference