6장 - 기초적인 그래프 연산들

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)
• 연결 요소(Connected Components)
• 신장 트리(Spanning Trees)
• 이중 결합 요소와 단절점

---

Depth First Search (DFS)

include <stdio.h>
#include <stdlib.h>

#define FALSE 0
#define TRUE 1
#define MAX_VERTICES 10

short int visited[MAX_VERTICES];//방문표시할 리스트

node graph[MAX_VERTICES];

struct node{
	int vertex;
	node* link;
};


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

인접리스트를 이용한 dfs이다.

 

---

Breadth First Search

큐를 이용한다.

void bfs(int v)
{
	node* w;
	struct queue* front = NULL, * rear = NULL;

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

코드는 나중에 직접 짜보겠다.

---

Connected Components

연결된 덩어리가 총 몇개인지 알 수 있다.

void connected(void)
{
	int i;
	for (i = 0; i < n; i++) {
		if (!visited[i]) {
			dfs(i);
			printf("\n");
		}
	}
}

bfs, dfs 모두 사용가능하다.

dfs나 bfs를 한번 수행하면 연결된 한 덩어리는 모두 visited 처리되기때문에

다음 덩어리로 가서 dfs/bfs를 실행한다.

 

---

Spanning Trees

신장트리.

그래프 G에 포함된 edge들로 구성되며, G의 모든 vertex들을 포함하는 트리.

모든 정점이 연결되어있어야 하고, 사이클이 존재해선 안 된다.

하나의 그래프에 대해 여러개의 신장트리가 존재할 수 있다.