알고리즘...105

너비 우선 탐색과 깊이 우선 탐색

그래프에서 모든 정점을 탐색하는 방법에는 레벨의 모든 노드를 방문하는 것을 우선하는 너비 우선 탐색(Breath First Search)과 루트에서부터 한 방향으로 리프 노드가 나올 때까지 진행하는 깊이 우선 탐색(Depth First Search)이 존재한다.

 

쉽게 배우는 알고리즘 그래프 그림 9-11

 

너비 우선 탐색 알고리즘

너비 우선 탐색은 먼저 방문한 노드를 먼저 처리하는 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);
		}
	}
}

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘