- choose any vertex, mark it as visited and push it onto queue.
- While the queue is not empty:
- Pop a vertex v from the queue
- for each vertex adjacent to v that has not been visited
const bfs = (graph, start) => {
// 방문하지 않은 vertex들을 담을 Queue 생성
const queue = new Queue();
// 방문했는지 여부를 체크할 visited set 생성하면 start를 방문의 시작
const visited = new Set([start]);
// 시작vertex를 queue에 담고.
queue.enqueue(start);
//queue가 빌 때까지 반복.
while(queue.length) {
//인접한 노드들을 담고
const neighbors = graph.neighbors(queue.dequeue());
// 인접한 vertex들을 방문히지 않는 경우엔 queue에 담고 방문 체크하며 반복.
for(const neighbor of neighbors) {
if(!visited.has(neighbor)) {
queue.enqueue(neighbor);
visited.add(neighbor);
}
}
}
return visited;
}
- Choose any vertex, mark is as visitied and push it onto stack
- While the stack is not empty:
- pop a vertex v from the stack
- for each vettex adjacente to v that has not been visited:
- mark is visited, and
- push it onto the stack
const dfs = (graph, start) => {
// 방문하지 않은 vertex들을 담을 Queue 생성
const array = new Array();
// 방문했는지 여부를 체크할 visited set 생성하면 start를 방문의 시작
const visited = new Set([start]);
// 시작vertex를 queue에 담고.
array.push(start);
// stack이 빌 때까지 반복.
while(array.length) {
//인접한 노드들을 담고
const neighbors = graph.neighbors(array.pop());
// 인접한 vertex들을 방문히지 않는 경우엔 queue에 담고 방문 체크하며 반복.
for(const neighbor of neighbors) {
if(!visited.has(neighbor)) {
array.push(neighbor);
visited.add(neighbor);
}
}
}
return visited;
}
참고: 그래프 탐색: DFS와 BFS