C언어 그래프에서 DFS와 BFS 구현 (탐색)

이전 글에서는 matrix 와 연결리스트로 그래프를 구현하는 방법에 대해 알아봤다.

C언어 행렬과 연결리스트로 그래프 구현하기

 

이번에는 그래프에서 탐색을 어떻게 C언어로 구현하는지 써보려고 한다.
이전 글에서도 말했지만 DFS, BFS는 search이지만 실제로는 travarsal, 즉 순회를 설명할 것이다..

깊이 우선 탐색 Depth-first

matrix로 구현된 그래프에서 깊이 우선으로 탐색하는 방법
단순히 그래프를 구현하는 방법은 이전 글에서 작성하였기에 따로 작성하지 않으려 한다.

이전에 작성한 그래프 코드를 바탕으로 깊이 우선 탐색을 하는 함수를 알아보려고 한다.
재귀를 이용해 구현할 것이다.

void dfs_mat(GraphType* g, int v)
{
	int w;
	visited[v] = TRUE;		// ???? v?? ??? ??? 
	printf("vertex %d -> ", v);		// ????? ???? ???
	for (w = 0; w<g->n; w++) 		// ???? ???? ???
		if (g->adj_mat[v][w] && !visited[w])
			dfs_mat(g, w);	//???? w???? DFS ???? ????
}

입력으로 받은 행 v에서 열 0에서 n까지 반복을 수행한다.

방문하지 않았다면 해당 vertex에서 다시 함수를 호출한다.

2) stack을 이용한 구현

int stack[100];
int top = -1;

void push(int num) {
    top++;
    stack[top] = num;
}
int is_empty() {
    return (top == -1);
}
int pop() {
    return stack[top--];
}
void dfs_mat(GraphType* g, int v) {
    push(v);
    
    while (!is_empty()) {
        int v = pop();  // 스택에서 노드 하나를 꺼냄
        if(visited[v]==0){// 방문하지 않은 노드라면
			visited[v]=1;
			printf("vertex %d -> ",v);
			for (int u = 0; u < g->n; u++) {
				if (g->adj_mat[v][u] == 1 && !visited[u]) {  // 연결된 노드 중 방문하지 않은 노드를 찾음
					push(u);  // 스택에 추가
				}
			}
		}
    }
}

 

너비 우선 탐색 Breadth-first

1) matrix로 구현된 그래프에서

먼저 행렬로 구현된 그래프이다.
큐를 이용해 구현할 것이다

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

	queue_init(&q);     
	visited[v] = TRUE;     
	printf("%d  visit -> ", v);
	enqueue(&q, v);			
	while (!is_empty(&q)) {
		v = dequeue(&q);		
		for (w = 0; w<g->n; w++)	
			if (g->adj_mat[v][w] && !visited[w]) {
				visited[w] = TRUE;   
				printf("%d visit -> ", w);
				enqueue(&q, w); 	
			}
	}
}

 

먼저 시작 노드를 큐에 넣을 것이다.
차례대로 방문할 것인데 방문한 노드는 dequeue하고 인접 노드를 다시 enqueue할 것이다.
그리고 dequeue하고 큐가 빌 때까지 반복한다.

 

2) 연결리스트로 구현된 그래프에서

다음은 연결리스트로 구현된 그래프이다.
마찬가지로 큐로 구현할 것이다.

 

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);	//정점을 큐에 삽입
			}
	}
}

연결리스트로 바뀌었다는 것 외에 방식은 동일하다. 행렬은 한 행에서 인접 노드를 찾았다면 연결리스트는 다음 링크, 다음 링크... 로 넘어가며 찾는 것이 다를 뿐이다.