[알고리즘] 그래프 순회(DFS, BFS)

 

그래프 순회는 하나의 정점에서 시작해 그래프의 모든 정점을 한 번씩 방문하는 작업을 말한다.

 

그래프의 정점들을 순회하는 체계적인 방법에는 깊이 우선 탐색과 너비 우선 탐색이 있다.

 

# 깊이 우선 탐색(DFS: Depth First Search)

시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없으면 가장 가까운 갈림길로 다시 돌아와 다른 방향을 다시 탐색한다.

이것은 이진 트리의 전위순회와 비슷한데, 위 그림처럼 A-B-D-E-C-F의 순서대로 탐색이 진행된다.

 

# 깊이 우선 탐색 진행 방법

시작 정점에서 한 방향으로 갈 수 있는 곳까지 깊이 탐색을 진행하다가,

더 이상 갈 곳이 없으면 가장 최근에 만났던 갈림길 정점으로 되돌아온다.

갈림길로 돌아와서는 가 보지 않은 다른 방향의 간선으로 탐색을 다시 진행하고,

이 과정을 반복해 결국 모든 정점을 방문하는 방법이다.

탐색 과정에서 여러 갈림길을 만나지만 그중에서 가장 최근에 만났던 갈림길로 되돌아와야 하기 때문에,

후입선출 구조의 스택에 저장한다!!

 

시작정점 U에서 깊이 우선 탐색으로 모든 정점을 방문하는 과정을 알아보자!!

 

 

# 깊이 우선 탐색 알고리즘 구현(인접 리스트 방식)

const dfs = (graph, v, visited) => {
    //1. 탐색 시작 노드 방문 처리
    visited[v] = true;
    console.log(v);

    //2. 탐색 노드의 인접 노드 확인
    for (const cur of graph[v]) {
        if (!visited[cur]) {
            dfs(graph, cur, visited);
        }
    }
};

let graph = [ [], [2,3,4], [1,4], [1,4], [1,2,3] ]
let visited = [...Array(n + 1).fill(false)]; // 방문 확인을 위한 변수, 길이는 정점+1

dfs(graph, 1, visited); // 1번 노드부터 탐색

 

 

# 깊이 우선 탐색 알고리즘 구현(인접행렬 방식)

let vtx = ['U', 'V', 'W', 'X', 'Y'];
let edge = [
    [0, 1, 1, 0, 0],
    [1, 0, 1, 1, 0],
    [1, 1, 0, 0, 1],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
];

let visited = [...Array(edge.length).fill(false)];

function DFS(vtx, edge, s, visited) {
    console.log(vtx[s]);
    visited[s] = true;

    for (let i = 0; i < vtx.length; i++) {
        if (edge[s][i] != 0) {
            if (visited[i] == false) {
                DFS(vtx, edge, i, visited);
            }
        }
    }
}

DFS(vtx, edge, 0, visited);

 

 

 

# 너비 우선 탐색(BFS: Breadth First Search)

시작 정점에서 가까운 정점을 먼저 방문하고 먼 정점을 나중에 방문한다.

이것은 이진 트리의 레벨순회와 비슷한데, 위 그림처럼 A-B-C-D-E-F의 순서로 탐색이 진행된다.

 

 

 

 

# 너비 우선 탐색 진행 방법

너비 우선 탐색은 '가까운 정점부터 꼼꼼하게 살피고 먼 정점을 찾아가는' 전략이다.

즉, 거리가 0인 시작 정점으로부터 거리가 1인 모든 정점을 방문하고,

거리가 2인 정점들, 거리가 3인 정점들의 순서로 방문을 진행하는데,

이것은 이진 트리의 레벨 순회와 동작이 비슷하다.

BFS에서는 가까운 거리에 있는 정점들을 차례로 저장하고, 들어간 순서대로 꺼낼 수 있는 자료구조가 필요하기 때문에

큐(Queue)를 사용한다.

BFS는 큐에서 정점을 꺼낼 때마다 아직 방문하지 않은 모든 인접 정점들을 방문하고 큐에 삽입한다.

이러한 탐색 과정은 큐가 공백 상태가 될 때까지 계속된다.

맨 처음 큐에는 시작 정점만이 저장되는데, BFS 탐색 진행 방법을 알아보자!

 

 

# 너비 우선 탐색 알고리즘 구현(인접 리스트 방식)

let vtx = ['U', 'V', 'W', 'X', 'Y'];
let aList = [[1, 2], [0, 1, 3], [0, 1, 4], [1], [2]];

function BFS(vtx, aList, s) {
    let n = vtx.length; // 그래프 정점 수
    let visited = [...Array(n).fill(false)]; // 방문 확인을 위한 리스트
    // console.log(visited);
    let queue = []; // queue를 만든다.
    queue.push(s); // 맨 처음에 시작 정점 s만 queue에 넣는다.
    visited[s] = true; // s는 방문했다고 표시한다.

    //queue가 공백일때까지
    while (queue.length !== 0) {
        s = queue.shift(); // 큐에서 정점 s를 꺼내고
        console.log(vtx[s]);

        aList[s].forEach((neighbor) => {
            // s의 인접 정점에 대해 아직 방문하지 않았다면
            if (!visited[neighbor]) {
                queue.push(neighbor); // 큐에 추가
                visited[neighbor] = true; // 방문했다고 표시
            }
        });
    }
}
BFS(vtx, aList, 0);