그래프 - 깊이우선탐색

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

 

깊이우선 탐색 Depth First Search: DFS

시작 정점에서 한 방향으로 직진하다가
더 이상 갈 수 없게 되면
다시 가장 가까운 갈림길로 돌아와서
다른 방향으로 다시 탐색을 진행하는 것

 

0. 알고리즘

• 그래프의 시작 정점에서 출발 ==> 시작정점 = v
• 정점 v 방문했다고 표시
• 정점 v의 인접정점 집합에 대해서 ( u ∈ 인접정점 집합 )
• 정점 u를 아직 방문안했으면
• 시작정점을 u로 설정해서 위의 과정 다시 수행
• 만약 인접정점 집합이 공집합이면 리턴

depth_first_search(v):
	v를 방문했다고 표시
	for all u in (v의 인접정점) do
    		if (u 아직 방문 안했으면)
        			then depth_first_search(u)

 

1. 인접행렬을 이용해 dfs 순서 알아내기

# c언어로 구현

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

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50

// 방문한 정점을 저장할 배열
int visited[MAX_VERTICES];

typedef struct GraphType {
	int n; //정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES]; //인접행렬
} GraphType;

//그래프 초기화
void init(GraphType* g)
{
	int r, c;
	g->n = 0; //정점의 개수는 0으로 초기화
	for (r = 0; r < MAX_VERTICES; r++) // 인접행렬의 모든 원소들 0으로 초기화
	{
		for (c = 0; c < MAX_VERTICES; c++)
			g->adj_mat[r][c] = 0;
	}
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
	if ((g->n) + 1 > MAX_VERTICES)
	{
		fprintf(stderr, "그래프: 정점의 개수 초과\n");
		return;
	}
	g->n++; // 정점을 삽입하는 것은 실질적으로 행렬에 영향을 주지 않음
	// 그저 정점의 개수만 증가시켜 주면 된다.
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
	if (start >= g->n || end >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류\n");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
	// 정점을 우선 삽입한 뒤에 
	// 해당 정점 번호를 이용해 간선을 삽입하기
}
// 깊이우선탐색 함수
void dfs_mat(GraphType* g, int v)
{
	int u;
	// 1. 시작정점 v 방문했음 표시 및 출력
	visited[v] = TRUE;
	printf("정점 %2d -> ", v);
	// 2. 정점 v의 인접정점 중에서
	for (u = 0; u < g->n; u++) {
		// 3. 아직 방문 안했고, 정점 v랑 연결된 정점이 있으면
		if ((visited[u] == FALSE) && (g->adj_mat[v][u])) {
			// 4. 그 정점에 대해 위의 과정 수행
			dfs_mat(g, u);
		}
		// 5. 만약 위의 조건을 만족하는 정점이 없으면 그 전 함수 호출로 리턴.
	}
}
int main()
{
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	for (int i = 0; i < 4; i++) {
		insert_vertex(g, i);
	}
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 0, 3);
	insert_edge(g, 1, 2);
	insert_edge(g, 2, 3);
	
	printf("깊이 우선 탐색\n");
	dfs_mat(g, 0);
	printf("\n");

	free(g);
	return 0;
}

# 결과

# 그림으로 이해하기

 

2. 인접리스트를 이용해 dfs 순서 알아내기

# 코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICE 50
#define TRUE 1
#define FALSE 0

// 각 정점마다 하나의 연결리스트가 필요하다
// 정점의 개수만큼의 포인터 배열(헤더노드)이 필요하다
// 하나의 노드 ==> GraphNode
// 포인터 배열의 이름 ==> adj_list

typedef struct GraphNode {		// 하나의 노드
	int vertex;					// 데이터 필드: 정점의 값을 저장할 곳
	struct GraphNode* link;		// 링크 필드: 인접정점을 가리킬 포인터 
	// 가리킬 변수의 타입이 하나의 정점이기 때문에 GraphNode 타입으로 선언해야 한다.
} GraphNode;

typedef struct GraphType {		// 그래프 전체
	int n;						// 해당 그래프의 정점의 개수
	GraphNode* adj_list[MAX_VERTICE]; // 헤더노드 집합; 각 연결 리스트의 첫번째 노드를 가리킴.
} GraphType;

int visited[MAX_VERTICE];

// 그래프 초기화
void init_adjList(GraphType* g) 
{
	int v;
	g->n = 0; //그래프 정점의 개수 0으로 초기화
	for (v = 0; v < MAX_VERTICE; v++) 
	{
		g->adj_list[v] = NULL;
	}
}
// 정점 삽입 연산: 값이 v인 정점을 삽입한다.
void insert_vertex_adjList(GraphType* g, int v) 
{ // v: 삽입합 노드의 값
	if ((g->n) + 1 > MAX_VERTICE) 
	{
		fprintf(stderr, "그래프: 정점의 개수 초과\n");
		return;
	}
	g->n++;
}
// 간선 삽입 연산: 정점 u와 v를 연결한다 : 정점 u에 간선 (u,v)를 맨 처음에 삽입
void insert_edge_adjList(GraphType* g, int u, int v) 
{
	if (u >= g->n || v >= g->n) 
	{
		fprintf(stderr, "그래프: 정점 번호 오류\n");
		return;
	}
	GraphNode* node = (GraphNode*)malloc(sizeof(GraphNode));
	if (node == NULL) {
		printf("malloc 오류: 할당 안됨\n");
		return;
	}
	node->vertex = v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node;	// adj_list의 한 원소는 GraphNode를 가리키는 포인터 타입이니까 할당 가능
}
// 깊이우선탐색 연결리스트로 구현
void dfs_list(GraphType* g, int v)
{
	GraphNode* u;
	// 1. 시작정점 v 방문했음 표시 및 출력
	visited[v] = TRUE;
	printf("정점 %2d -> ", v);
	// 2. 정점 v의 인접정점 중에서
	for (u = g->adj_list[v]; u != NULL; u = u->link) 
	{
		// 3. 아직 방문 안했으면 (간선이 존재하는지 확인 안함)
		if ((visited[u->vertex] == FALSE)) 
		{
			// 4. 그 정점에 대해 위의 과정 수행
			dfs_list(g, u->vertex);
		}
		// 5. 만약 위의 조건을 만족하는 정점이 없으면 그 전 함수 호출로 리턴.
	}
}
int main()
{
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init_adjList(g);
	for (int i = 0; i < 4; i++) {
		insert_vertex_adjList(g, i);
	}
	insert_edge_adjList(g, 0, 1);
	insert_edge_adjList(g, 0, 2);
	insert_edge_adjList(g, 0, 3);
	insert_edge_adjList(g, 1, 2);
	insert_edge_adjList(g, 2, 3);

	printf("깊이 우선 탐색\n");
	dfs_list(g, 0);
	printf("\n");

	free(g);
	return 0;
}

# 결과

# 그림으로 이해하기

 

3. 스택 stack을 이용해 dfs 순서 알아내기

# 알고리즘

dfs_iterative(graph, v):
	스택 stack을 생성한다
	stack.push(v) 
	while(not is empty(stack)) do
		v = s.pop()
		if( v 아직 방문 안했으면)
			v를 방문했다고 표시
			for all u in (v의 인접정점) do
				if (u 아직 방문 안했으면)
					stack.push(u)

# 그림으로 이해하기

그림1

위의 그림1 의 그래프에 대해 다음과 같이 깊이우선 탐색이 실시됩니다.