그래프는 다양한 자료구조 가운데 가장 유연한 구조를 가지고 있다. 이러한 그래프를 가지고 알고리즘을 작성 한다고 한다면 대표적인 탐색 두 가지 탐색 방법이 있다. 스택을 이용한 DFS(Depth First Search : 깊이 우선 탐색)과 큐를 이용한 BFS(Breadth First Search : 너비 우선 탐색)이 있다. 이번 블로깅을 통해서 이 두 가지 탐색 방법을 확실하게 익힐 것이다. DFS와 BFS는 주어진 상황에 맞게 선택적으로 사용할 수 있어야 한다.

DFS와 BFS를 적절하게 사용하지 못한다면 위 그림과 같은 상황이 발생할 수 있다. 각 방식이 어떻게 적재적소에 적용되는지 다음 문제를 두 가지 방법을 모두 사용해서 풀어보자.

Question

무향이 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 connectedVertices함수를 작성하세요.

//ex1
const result = connectedVertices([
	[0, 1],
	[2, 3],
	[4, 5],
]);
console.log(result); // 3
//ex2
const result = connectedVertices([
	[0, 1],
	[2, 3],
	[3, 4],
	[3, 5],
]);
console.log(result); // 2

위 문제를 해결하기 위해서는 일단 기본적인 코드가 필요하다

function connectedVertices(edges){
  //최대 버텍스를 찾습니다.(최대값을 이용해서 인접행렬 혹은 인접리스트를 만들기 위함)
  let max = 0;
  for(let i = 0; i < edges.length; i++) {
    const [from, to] = edges[i];
    max = Math.max(max, from, to);
  }
  //인접 리스트를 만든다.
  let vertexList = {};
  for(let el of edges){
    if(!vertexList[el[0]]){
      vertexList[el[0]] = [el[1]];
    }else{
      vertexList[el[0]].push(el[1]);
    }
    if(!vertexList[el[1]]){
      vertexList[el[1]] = [el[0]];
    }else{
      vertexList[el[1]].push(el[0]);
    }
  }
  //인접 행렬을 만든다.
  //const vertexMatrix = Array(max+1).fill(0).map(row => Array(max +1).fill(0));

  //방문한 노드를 담을 seen객체를 선언, 컴포넌트의 갯수를 카운트할 cnt선언
  const seen = {};
  let cnt = 0;
  
  //그래프에 있는 노드를 전부 순회합니다.
  for(let node = 0; node <= max; node++){
    if(!seen[node]){ //노드가 방문한 객체가 아니면 실시
      //dfs or bfs(vertexList, node, seen) //컴포넌트 검사 실시
      cnt++;
    }
  }
  return cnt;
}

위 코드가 기본적인 문제 해결문이다 여기서 마지막 if문 안에 있는 함수를 dfs 혹은 bfs로 바꿔줌에 따라 다른 방식의 검사가 진행될 것이다.

DFS

먼저 DFS의 방식을 적어보겠다.

function dfs(vertexList, node, seen) {
	// 먼저 해당 노드는 일단 방문했기에 먼저 방문했다는 표시를 해준다.
	seen[node] = true;
	// 해당 노드의 모든 간선들을 전부 순회합니다.
	for (let i = 0; i < vertexList[node].length; i++) { //해당 노드와 인접한 노드 갯수만큼 실시
		// 만약 node와 이어진 다른 노드(vertexList[node][i])를 방문하지 않았다면
		if (!seen[vertexList[node][i]]) {
			// dfs를 호출해(재귀) 방문합니다.
			dfs(vertexList, vertexList[node][i], seen);
		}
		// 모든 방문이 종료되면 다음 노드 확인합니다.
		// 재귀가 종료되면(한 정점에서 이어진 모든 간선들을 확인했다면) dfs 함수를 종료하고 카운트를 셉니다. 
	}
}

BFS

다음은 BFS의 방식이다.

function bfs(vertexList, node, seen) {
	// bfs는 가장 가까운 정점부터 탐색하기 때문에 queue를 사용합니다.
	// queue에 node가 담습니다.
	const queue = [node];
	// 해당 버텍스를 방문했기 때문에 seen 담아 주고, 방문했다는 표시인 true를 할당합니다.
	seen[node] = true;
  // queue의 길이가 0일 때까지 순환합니다.
	while (queue.length > 0) {
		// node 변수에 정점을 할당합니다.
		// queue는 선입선출이기 때문에 shift 메소드를 사용하여 버텍스를 가져옵니다.
		const node = queue.shift();

		// 그래프의 node에 인접한 노드 전부 순회합니다.
		for (let i = 0; i < vertexList[node].length; i++) {
			// 만약, 해당 노드를 방문하지 않았다면 queue에 삽입합니다.
			// 방문했다는 표시로 visited에 해당 노드를 삽입하고 true를 할당합니다.
			if (!seen[vertexList[node][i]]) {
				queue.push(vertexList[node][i]);
				seen[vertexList[node][i]] = true;
			}
			// queue에 다음으로 방문할 노드가 있기 때문에 while은 멈추지 않습니다.
			// 만약, queue가 비어 있다면 더 이상 갈 곳이 없는 것이기 때문에 bfs 함수를 종료하고 카운트를 셉니다.
		}
	}
}

결론

코드의 길이만 보더라도 DFS가 훨씬 간결하고 보기가 쉽다. DFS는 구현이 쉽고 연결된 부모 노드와 현재 노드만 저장하면 되기 때문에 메모리도 적게 사용한다. 하지만 BFS는 각 확인 단계마다 인접 노드 전부를 저장해야 한다. 노드의 수가 천문학적이게 된다면 사용에 부적절 하다.
하지만 확인 해야할 데이터가 적고 어느 정도의 깊이가 예상이 된다면 BFS를 사용하는게 현명하다. 하지만 그럴 일은 자주 없다고 한다. 일단은 확실하게 DFS를 구현하는 것이 우선이다. 그리고 인접 리스트와 인접 행렬또한 행렬은 모든 노드의 간선을 확인해야해서 비용이 많이 필요할지 모르지만 이 또한 리스트에 비해 육안으로 확인이 쉽고 효율적이라고 생각된다.

최대한 'DFS'와 '인접행렬' 사용법을 숙달해야겠다.