[DFS / BFS] 연결된 정점들

function connectedVertices(edges) {
const graph = {};
for (let [from, to] of edges) {
if (!graph[from]) graph[from] = [];
if (!graph[to]) graph[to] = [];
graph[from].push(to);
graph[to].push(from);
}

const visited = {};
let count = 0;

const dfs = (node) => {
visited[node] = true;
for (let neighbor of graph[node]) {
if (!visited[neighbor]) {
dfs(neighbor);
}
}
};
//인자로 받은 node에서 시작하여 DFS 탐색을 수행하고, 방문한 정점을 visited 객체에 기록

for (let node in graph) {
if (!visited[node]) {
dfs(node);
count++;
}
}
//모든 정점을 순회하면서 방문하지 않은 정점에서 DFS 탐색을 시작
//이때, 탐색을 시작한 정점이 연결 요소의 한 부분
return count;
}

ex)

[0, 1],
[2, 3],
[4, 5],

graph 객체

{
  0: [1],
  1: [0],
  2: [3],
  3: [2],
  4: [5],
  5: [4]
}

dfs(0)이 호출

visited[0]은 true로 설정

graph[0]는 1로 1이 방문되지 않는 정점으로

dfs(1)이 호출

dfs(1)에서 visited[1]는 true로 설정

 

dfs(0)으로 돌아와 graph[0]의 모든 정점을 방문했으므로 다음 정점인 2로 넘어간다.

 

dfs(2)가 호출

visited[2]는 true로 설정

graph[2]는 3로 3이 방문되지 않은 정점이므로

dfs(3)이 호출

dfs(3)에서 visited[3]은 true로 설정

 

dfs(2)으로 돌아와 graph[2]의 모든 정점을 방문했으므로 다음 정점인 4로 넘어간다.

 

dfs(4)가 호출

dfs(4)에서 visited[4]는 true로 설정

graph[4]에서 5이 방문되지 않은 정점이므로

dfs(5)이 호출

dfs(5)에서 visited[5]은 true로 설정

 

count는 3이 된다.