열혈 자료구조 - 14.3 그래프의 탐색(2)

깊이 우선 탐색의 구현 모델

- 깊이 우선 탐색에서는 정점 하나씩 탐색하면서 더이상 주변 탐색할 대상이 없다면 되돌아 간다는 점이 포인트

- 되돌아 가려는 정점을 스택을 이용하여 처리

- 스택에 저장하는 시점은 정점에서 탐색 후 다른 정점으로 이동했을 때 스택에 저장

- 그리고 탐색한 정점에 대한 정보를 따로 저장

- E에서 더이상 탐색 대상이 없을 경우 스택에서 POP하면서 정점에 탐색 대상이 있는지 확인

- 다시 C는 F를 탐색하고 C는 스택에 저장

- 다시 F는 탐색 대상이 없으므로 스택에서 POP하면서 탐색 대상을 찾음

- 모든 대상을 탐색하면 스택이 모두 비게 되면서 경로 추적이 끝났다고 판단

 

깊이 우선 탐색의 구현

- 구조체

    -> 탐색이 진행된 정보를 담는 포인터 변수 추가

    -> 초기화 및 리소스 해제 시 malloc, free

typedef struct _ual
{
	int numV;   
	int numE;   
	List* adjList;  
	int* visitInfo;		// 탐색이 된 정점 정보
} ALGraph;

- 탐색했는지 확인하는 함수

    -> 탐색한 정점을 인자로 넘겨 해당 인덱스를 체크

int VisitVertex(ALGraph * pg, int visitV)
{
	if(pg->visitInfo[visitV] == false)
	{
		pg->visitInfo[visitV] = true;	// 해당 인덱스를 true로 설정
		printf("%c ", visitV + 65);     // 탐색 정점 출력
		return true;
	}
	
	return false;
}

- 깊이 우선 탐색

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

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

	VisitVertex(pg, visitV);    // 시작 정점 탐색
	SPush(&stack, visitV);		// 탐색한 정점 push

	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);
}

 

너비 우선 탐색의 구현 모델

- 연결된 정점의 탐색할 차례를 기록하기 위해 큐를 사용

- 깊이 우선 탐색과 마찬가지로 탐색한 정점에 대한 정보를 따로 저장

- 큐에 탐색할 정점을 enqueue

- 큐에서 정점의 정보를 dequeue하고 그 정점은 다음 정점을 다시 enqueue함

- 정점이 탐색되었다면 enqueue되지 않음

- enqueue 없이 dequeue 만 하다보면 큐는 비워지게 되게 되면서 탐색이 끝남

 

너비 우선 탐색의 구현

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

	// DFS를 위한 큐의 초기화
	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 = Dequeue(&queue);	// 큐에서 꺼내서 위 과정 반복
        	}
	}

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