[알고리즘] 깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS)

그래프를 탐색하는 알고리즘

 

[깊이 우선 탐색(DFS)] 

이름처럼 한길만 깊이 파고드는 알고리즘이다 (depth)

 

<특징>

1. 하나의 정점에서 다른 하나의 정점만 탐색한다(한 사람에게만 연락한다)

2. 스택을 이용하여 경로를 되돌아간다★

3. 처음 탐색을 시작한 정점의 위치에서 탐색은 끝이 난다

 

 

▶ DFS의 구현

 

<주요 장치>

 

• 스택 : 경로 정보의 추적을 목적 (내가 이미 탐색을 완료해서 탐색할 기회를 다른 정점에게 넘긴 애들만 들어옴)
• 배열 : 방문 정보의 기록을 목적

 

그래프 구현한 내용에서 DFS 탐색 기능(스택+연결리스트)만 추가

<실제 구현>

 

• 정점의 이름

// 정점의 이름들을 상수화
enum {A, B, C, D, E, F, G, H, I, J};

 

 

• 그래프를 표현한 구조체 (탐색이 완료된 정점의 정보 추가 by 배열)

typedef struct _ual
{
	int numV;   // 정점의 수
	int numE;   // 간선의 수
	List * adjList;   // 간선의 정보
	int * visitInfo; //탐색이 완료된 정점의 정보(배열로 할당됨)
} ALGraph;

 

 

• 정점의 방문을 진행하는 함수 (이미 방문 했는지(FALSE) 안했는지(TRUE) 구분함)

int VisitVertex(ALGraph * pg, int visitV)
{
	if(pg->visitInfo[visitV] == 0)
	{
		pg->visitInfo[visitV] = 1;
		printf("%c ", visitV + 65);     // 방문 정점 출력
		return TRUE; //방문 안했으면 TRUE 반환
	}
	
	return FALSE; //방문 했으면 FALSE 반환
}

 

 

 

• 실제 DFS의 구현 !!

void DFShowGraphVertex(ALGraph * pg, int startV)
{
	Stack stack;
	int visitV = startV;
	int nextV;

	// DFS를 위한 스택의 초기화
	StackInit(&stack);

	VisitVertex(pg, visitV);    // 시작 정점 방문
	SPush(&stack, visitV);

	while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE)
	{
		int visitFlag = FALSE;

		if(VisitVertex(pg, nextV) == TRUE)//첫번째 노드가 탐색이 이뤄질수 있음
		{
			SPush(&stack, visitV);
			visitV = nextV;
			visitFlag = TRUE;
		}
		else //첫번째 노드가 탐색이 안돼서 다음 탐색 안한 노드를 찾아야 함
		{
			while(LNext(&(pg->adjList[visitV]), &nextV) == TRUE)
			{
				if(VisitVertex(pg, nextV) == TRUE)
				{
					SPush(&stack, visitV);
					visitV = nextV;
					visitFlag = TRUE;
					break;
				}
			}
		}
		
		if(visitFlag == FALSE) //지금 있는 노드 주변은 다 탐색을 함
		{
			if(SIsEmpty(&stack) == TRUE)    // 스택이 비면 DFS종료
				break;
			else	// 스택이 안비어 있으면 이전으로 돌아감
				visitV = SPop(&stack);	
		}
	}

	// 탐색 정보 초기화
	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

 

이 모형을 떠올리면서 위 구현을 이해

 

562~563P에 야무지게 정리해 놓음

 

 

 

 

[너비 우선 탐색(BFS)]

 자신에게 연결된 모든 정점을 탐색하는 방식 (breadth)

 

<특징>

1. 자신과 연결된 모든 정점을 탐색한다 (폭을 우선시하는 방식)

2. 큐를 이용하여 폭 넓히는 탐색을 진행할 정점의 순서를 정한다★

3. 큐가 비고 정점을 더 탐색할수 없으면 탐색은 끝이 난다

 

 

 

 

▶ BFS의 구현

 

<주요 장치>

 

• 큐 : 방문 차례의 기록 목적
• 배열 : 방문 정보의 기록을 목적

 

 

그래프에서 DFS 구현한 내용에서 BFS 탐색 기능(큐+연결리스트)만 추가

 

<실제 구현> 

 

• 정점의 이름

// 정점의 이름들을 상수화
enum {A, B, C, D, E, F, G, H, I, J};

 

 

• 그래프를 표현한 구조체 (탐색이 완료된 정점의 정보 추가 by 배열)

typedef struct _ual
{
	int numV;   // 정점의 수
	int numE;   // 간선의 수
	List * adjList;   // 간선의 정보
	int * visitInfo; //탐색이 완료된 정점의 정보(배열로 할당됨)
} ALGraph;

 

 

• 정점의 방문을 진행하는 함수 (이미 방문 했는지(FALSE) 안했는지(TRUE) 구분함)

int VisitVertex(ALGraph * pg, int visitV)
{
	if(pg->visitInfo[visitV] == 0)
	{
		pg->visitInfo[visitV] = 1;
		printf("%c ", visitV + 65);     // 방문 정점 출력
		return TRUE; //방문 안했으면 TRUE 반환
	}
	
	return FALSE; //방문 했으면 FALSE 반환
}

 

• 실제 BFS의 구현 !!

void BFShowGraphVertex(ALGraph * pg, int startV)
{
	Queue queue;
	int visitV = startV;
	int nextV;

	// BFS를 위한 큐의 초기화
	QueueInit(&queue);

	// 시작 정점 탐색
	VisitVertex(pg, visitV);

	while(LFirst(&(pg->adjList[visitV]), &nextV) == TRUE)
	{
		if(VisitVertex(pg, nextV) == TRUE) //리스트의 첫번째 노드가 처음 방문이면 큐에 삽입 
			Enqueue(&queue, nextV);

		while(LNext(&(pg->adjList[visitV]), &nextV) == TRUE)
        //한 리스트의 모든 노드를 방문하고 처음 방문이면 큐에 삽입
		{
			if(VisitVertex(pg, nextV) == TRUE)
				Enqueue(&queue, nextV);
		}

		if(QIsEmpty(&queue) == TRUE)    // 큐가 비면 BFS 종료
			break;
		else 
        // 하나의 리스트를 다 탐색(=하나의 정점에서 모든 연결된 정점을 탐색)하면 
        //가장 먼저 큐에 들어간 리스트를 visitV로 설정
			visitV = Dequeue(&queue);	
	}

	// 탐색 정보 초기화
	memset(pg->visitInfo, 0, sizeof(int) * pg->numV);
}

 

 

이 모형을 떠올리면서 위 구현을 이해