일지
알고리즘...105
niamdank
2022. 1. 20. 17:19
너비 우선 탐색과 깊이 우선 탐색
그래프에서 모든 정점을 탐색하는 방법에는 레벨의 모든 노드를 방문하는 것을 우선하는 너비 우선 탐색(Breath First Search)과 루트에서부터 한 방향으로 리프 노드가 나올 때까지 진행하는 깊이 우선 탐색(Depth First Search)이 존재한다.
너비 우선 탐색 알고리즘
너비 우선 탐색은 먼저 방문한 노드를 먼저 처리하는 FIFO 방식이므로 Queue를 사용한다.
BFS 알고리즘
BFS(G, s)
{
for each v ∈ V - {s}
{
visited[v] ← NO;
}
visited[s] ← YES;
enqueue(Q, s);
while (Q ≠ ∮)
{
u ← dequeue(Q);
for each v ∈ L(u)
{
if (visited[v] = NO) then
{
visited[v] ← YES;
enqueue(Q, v);
}
}
}
}
깊이 우선 탐색 알고리즘
깊이 우선 탐색은 나중에 방문한 노드를 먼저 처리하는 LIFO 방식이므로 Stack을 사용한다.
DFS 알고리즘
DFS(G, s)
{
for each v ∈ V - {s}
{
visited[v] ← NO;
}
for each v ∈ V - {s}
{
if (visited[v] = NO) then
{
aDFS(v);
}
}
}
aDFS(v)
{
visited[s] ← YES;
for each v ∈ L(u)
{
if (visited[v] = NO) then
{
aDFS(v);
}
}
}