BFS(Breadth First Search)

BFS는 '너비 우선 탐색'으로 트리 구조 탐색 방식 중 하나이다.

아래 코드는 방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 구현한 코드이다. 이 알고리즘은 인접 리스트와 인접 행렬의 두 가지 방식으로 구현할 수 있다.

인접 리스트(레퍼런스)

function connectedVertices(edges) {

	// 최대 버텍스를 찾는다.
	const maxVertex = edges.reduce((a, c) => {
		const bigger = Math.max(...c);
		if (bigger > a) return bigger;
		return a;
	}, 0);

	const adjList = {};

  // 인접 리스트에 최대 버텍스 크기만큼 반복해 버텍스를 만들어 준다.
	for (let i = 0; i <= maxVertex; i++) {
		adjList[i] = [];
	}

  // edges를 순회하며, (무향 그래프이므로 쌍방으로) 간선을 추가한다.
	for (let i = 0; i < edges.length; i++) {
		adjList[edges[i][0]].push(edges[i][1]);
		adjList[edges[i][1]].push(edges[i][0]);
	}

  // 방문한 버텍스를 담을 객체 선언
	const visited = {};
	// 컴포넌트가 몇 개인지 카운트할 변수 선언
	let count = 0;

  // 그래프에 있는 버텍스를 전부 순회한다.
	for (let vertex = 0; vertex <= maxVertex; vertex++) {

		// 만약 i 번째 버텍스를 방문하지 않았다면 bfs로 해당 버텍스와, 버텍스와 연결된(간선) 모든 버텍스를 방문한다.
		// BFS로 갈 수 있는 모든 정점들을 방문하며 visited에 담기 때문에, 방문한 버텍스는 bfs를 돌지 않는다.
		// 컴포넌트 확인
		if (!visited[vertex]) { // 아직 방문하지 않은 버텍스라면?
			// 그래프와 버텍스, 방문했는지 확인할 visited를 bfs 함수에 인자로 넘겨주어 실행한다.
			bfs(adjList, vertex, visited);

			// bfs 함수 실행이 끝나면 카운트
			count++;
		}
	}

  // 카운트를 반환
	return count;
}


// bfs 함수
function bfs(adjList, vertex, visited) {

	// bfs는 가장 가까운 정점부터 탐색하기 때문에 queue를 사용(인접 행렬 길찾기 로직과 같음)
	// queue에 vertex를 담는다.
	const queue = [vertex];
	// 해당 버텍스를 방문했기 때문에 visited에 담아 주고, 방문했다는 표시로 true를 할당한다.
	visited[vertex] = true;

  // queue의 길이가 0일 때까지(queue가 빌 때까지) 순회한다.
	while (queue.length > 0) {

		// cur 변수에 정점을 할당
		// queue는 선입선출이기 때문에 shift 메소드를 사용하여 버텍스를 추출한다.
		const cur = queue.shift();

		// 그래프의 cur 정점에 있는 간선들을 전부 순회한다.
		for (let i = 0; i < adjList[cur].length; i++) {

			// 만약, 해당 버텍스를 방문하지 않았다면 queue에 삽입한다.
			if (!visited[adjList[cur][i]]) {
				queue.push(adjList[cur][i]);
              		// 방문했다는 표시로 visited에 해당 버텍스를 삽입하고 true를 할당한다.
				visited[adjList[cur][i]] = true;
			}

			// queue에 다음으로 방문할 버텍스가 있기 때문에 while은 멈추지 않는다.
			// 만약, queue가 비어 있다면 더 이상 갈 곳이 없는 것이기 때문에 bfs 함수를 종료하고 카운트를 센다.
		}
	}
}

위의 인접 리스트 레퍼런스를 참고하여 인접 행렬로도 구현해볼 수 있었다. 리스트와 코드가 매우 유사하나 세부적인 코드들에서 차이를 보이는 것을 알 수 있다.

인접 행렬

function connectedVertices(edges) {
    // TODO: 여기에 코드를 작성합니다.
    // 인풋값의 정보를 받아서 matrix의 뼈대를 만들고 그 뼈대에 간선도 추가
    // 1. 매트릭스를 만든다
      // 가장 큰 정점을 구함
    let max = Math.max(...edges.flat());
    let matrix = new Array(max+1).fill(0).map(el => new Array(max+1).fill(0));
    
      // 2. 간선 추가
    edges.forEach((el) => {
    const [row, col] = el;
    matrix[row][col] = 1;
    matrix[col][row] = 1;
    });
    
      // 3. count 세기
    const visited = {};
    let count = 0;
    for(let vertex = 0; vertex <= max; vertex++) {
    if(!visited[vertex] /*visited[vertex] === false */) {
        dfs(matrix, vertex, visited);
        count++;
        }
    }
    return count;
};
    
    // bfs 함수
function bfs(matrix, vertex, visited) {
    const enqueue = (q) => queue.push(q);
    const dequeue = () => queue.shift();
    
    let queue = [vertex];
    visited[vertex] = true;

    while(queue.length > 0) {
    let now = dequeue();
    for(let next = 0; next < matrix.length; next++) {
    if(next === now) continue;

    else if(matrix[now][next] === 1 && !visited[next]) {
        visited[next] = true;
        enqueue(next);
            }
        }
    }   
};

DFS(Depth First Search)

DFS는 '깊이 우선 탐색'으로 역시 트리 구조 탐색 방식 중 하나이다. BFS와는 반대되는 개념으로 볼 수 있다.

DFS 방법을 사용하여 위 알고리즘 문제를 동일하게 풀 수 있다. 우선 인접 리스트와 인접 행렬 각각의 케이스에서의 dfs 함수를 살펴보면 다음과 같다.

인접 리스트

// dfs 함수
// 컴포넌트를 세는 로직은 위에 작성한 코드와 동일하므로 생략, bfs 함수 대신 dfs 함수를 호출하면 동일한 결과를 얻을 수 있음.
function dfs(adjList, vertex, visited) {
	// 해당 버텍스에 방문했다는 표시로 visited key에 vertex를 담고 값에 true를 할당
	visited[vertex] = true;

	// 해당 버텍스의 모든 간선들을 전부 순회
	for (let i = 0; i < adjList[vertex].length; i++) {

		// 만약 i번째 간선과 이어진 버텍스를 방문하지 않았다면
		if (!visited[adjList[vertex][i]]) {
			// dfs를 호출해(재귀) 방문한다.
			dfs(adjList, adjList[vertex][i], visited);
		}
		// 모든 방문이 종료되면 다음 버텍스를 확인
		// 재귀가 종료되면(한 정점에 이어진 모든 간선들을 확인했다면) dfs 함수를 종료하고 카운트 한다.
	}
}

여기서 중요하게 뽑을 포인트는 재귀함수를 사용하여 dfs를 구현했다는 점이다. bfs와 다르게 수직 아래로 파고들며 정점들을 탐색해야 하기 때문에 재귀 호출로 이를 구현할 수 있음을 알 수 있다.

인접 행렬

function dfs(matrix, vertex, visited) {
    visited[vertex] = true;

    for(let next = 0; next < matrix.length; next++) {
    if(matrix[vertex][next] === 1 && !visited[next]) {
        dfs(matrix, next, visited);
        }
    }
};

dfs도 bfs와 마찬가지로 인접 리스트 구현과 인접 행렬 구현 코드에서 세부적인 코드의 차이만 존재할 뿐 큰 틀은 같다는 것을 알 수 있다.

BFS vs. DFS