Chpter 6-1 : Graph (DFS & BFS)

자료구조인 그래프를 탐색하는 방법입니다.

#define MAX_VERTICES 50
typedef struct node* node_pointer;
typedef struct node {
	int vertex;
	node_pointer link;
};
node_pointer graph[MAX_VERTICES];
int n = 0;

기본 설정입니다. 

변수 n은 현재 사용하고 있는 정점의 갯수 를 나타냅니다.

---

DFS (깊이 우선 탐색)

Root node 한개를 선택해 하나의 자식 노드를 집중적으로 계속 탐색하고 탐색이 끝나면

Root node의 다음 자식 노드를 선택해 또 탐색하는 방법입니다.

void dfs(int v) {
	node_pointer w;
	visited[v] = TRUE;
	printf("%5d", v);
	for (w = gragh[v]; w; w = w->link)
		if (!visited[w->vertex])
			dfs(w->vertex);
}

visited 배열은 탐색했던 정점을 TRUE로 만들어 주어서 중복 방문하는것을 방지해줍니다.

처음에 모든 visited 배열은 FALSE로 초기화 됩니다.

처음에 저런 모양으로 되어있습니다.

0 -> 1 -> 2 ->3 이 순서로 탐색하게 됩니다.

---

BFS (너비 우선 탐색)

인접한 Node들을 먼저 탐색하는 것입니다. 

BFS는 큐로 구현합니다.

typedef struct queue* queue_pointer;
typedef struct queue {
	int vertex;
	queue_pointer link;
};
queue_pointer front, rear;
void addq(int);
int deleteq();

다음과 같은 초기화가 필요합니다.

void bfs(int v) {
	node_pointer w;
	front = rear = NULL;
	printf("%5d", v);
	visited[v] = TRUE;
	addq(v);
	while (front) {
		v = deleteq();
		for (w = graph[v]; w; w = w->link) {
			if (!visited[w->vertex]) {
				printf("%5d", w->vertex);
				addq(w->vertex);
				visited[w->vertex] = TRUE;
			}
		}
	}
}

0 -> 1 -> 3 -> 2 이 순서로 탐색을 진행합니다.