[C 자료구조] 인접 리스트 그래프 탐색 ( DFS, BFS )

[C 자료구조] 그래프 ADT 구현 : 인접행렬 / 인접리스트

지난 포스팅에서 인접 행렬과 인접 리스트로 그래프를 구현해보았죠. 오늘은 그렇게 구현한 그래프의 탐색 연산을 구현하는 방법에 대해 알아보겠습니다. 그래프의 탐색은 가장 기본적인 연산으로 하나의 정점으로부터 시작해서 차례대로 모든 정점들을 한 번씩 방문하는 것 입니다.  그래프의 탐색 방법은 2 가지가 있습니다.

• 깊이 우선 탐색 ( DFS : Depth First Search )
• 너비 우선 탐색 ( BFS : Breath First Search )

DFS 와 BFS 는 알고리즘 카테고리에서도 다뤘던 정말 중요한 탐색 알고리즘입니다. 따라서 오늘의 그래프를 통해 DFS와 BFS를 이해하고 나중에 다른 언어로도 이를 자유롭게 구현하고 사용할 줄 알아야 합니다.

DFS 란 트리에서 생각해보면 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 매우 유사합니다. 즉 DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법입니다. DFS 는 스택을 사용해 구현합니다. BFS 는 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 기법입니다. BFS는 큐를 사용해 구현합니다.

 

아래의 동작과 구현에서 확인하겠지만, DFS의 시간 복잡도는 모든 간선을 조사하므로 정점의 수가 n 이고 간선의 수가 e인 그래프인 경우, 그래프가 인접 행렬로 표시되어 있다면 O(n^2), 인접 리스트로 표현되어 있는 경우는 O(n+e) 가 됩니다. 따라서 희소 그래프인 경우는 DFS는 인접 리스트의 사용이 인접 행렬보다 시간적으로 유리합니다.

 

[알고리즘] DFS (깊이 우선 탐색) - 스택 구현 / 재귀 구현

 

[알고리즘] BFS (너비 우선 탐색)

위 2개의 게시물에서 인접 행렬로 표현된 그래프에 대한 DFS와 BFS를 구현해보았고, 이번 포스팅은 인접 리스트로 표현된 그래프에 대한 DFS를 구현합니다. 동작 원리에 대한 설명도 위 포스팅 2개를 참고해주시면 됩니다.

---

 인접 리스트 DFS

 

인접 리스트로 표현된 그래프의 경우 다른 부분은 탐색을 진행할 때의 for 조건과 방문조건을 체크하는 경우입니다. 자동으로 for문 내에서 NULL 포인터가 나오는 경우, 즉 인접 리스트의 끝에 도달한 경우 for 문이 종료되기 때문에 if 문 안에서는 이 정점이 방문한 정점인지, 아닌지만 체크하는 visited 배열 체크 조건만 들어갑니다.

int visited[MAX_VERTICES];

// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType* g, int v)
{
	GraphNode* w;
	visited[v] = TRUE;   		// 정점 v의 방문 표시 
	printf("정점 %d -> ", v);		// 방문한 정점 출력
	for (w = g->adj_list[v]; w; w = w->link)// 인접 정점 탐색 
		if (!visited[w->vertex])
			dfs_list(g, w->vertex); //정점 w에서 DFS 새로 시작
}

 

 

 인접 리스트 BFS

void bfs_list(GraphType* g, int v)
{
	GraphNode* w;
	QueueType q;

	init(&q);    				// 큐 초기 화 
	visited[v] = TRUE;      // 정점 v 방문 표시 
	printf("%d 방문 -> ", v);
	enqueue(&q, v);			// 시작정점을 큐에 저장 
	while (!is_empty(&q)) {
		v = dequeue(&q);		// 큐에 저장된 정점 선택 
		for (w = g->adj_list[v]; w; w = w->link) //인접 정점 탐색
			if (!visited[w->vertex]) {	// 미방문 정점 탐색 
				visited[w->vertex] = TRUE;   // 방문 표시
				printf("%d 방문 -> ", w->vextex);
				enqueue(&q, w->vertex);	//정점을 큐에 삽입
			}
	}
}

인접 행렬로 구현한 BFS와 다른 점은 탐색의 순서? 과정을 결정하는 for 문과 if문 조건 체크입니다. DFS와 동일하게 for문은 인접 행렬을 전부 검사하는 것이 아닌 인접리스트를 따라가면서 NULL 포인터를 만날때까지 이를 반복합니다. 즉 모든 정점에 대해서 BFS를 수행합니다. 

 

이 개념이 헷갈린다면 DFS와 BFS 게시글에서 인접 행렬로 구현한 함수과 비교해서 확인해보고, 그래도 이해되지 않는다면 아래 게시글을 참고해주시면 됩니다. 감사합니다.

[C 자료구조] 그래프(Graph)의 종류 : 인접 행렬(Adjacent matrix) vs 인접 리스트(Adjacent list)