DFS (깊이 우선 탐색)

1. 먼저 v를 방문한 다음
2. v에 인접한 정점 중에 아직 방문하지 않은 정점 w를 찾아서 w에 대한 DFS를 재귀적으로 수행한다.

(방문: 재귀 호출해서 헤드 노드 접근, visited 원소 값=1)

adjacency list Version (인접 리스트 버전)

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

typedef struct GraphNode {
	int vertex;
	struct GraphNode* link;
}GraphNode;

#define MAX_VERTICES 50

typedef struct GraphType {
	int n; // 정점의 개수
	GraphNode* adj_list[MAX_VERTICES];
}GraphType;

// 그래프 초기화
void init(GraphType* g) {
	int v;
	g->n = 0;
	for (v = 0; v < MAX_VERTICES; v++)
		g->adj_list[v] = NULL;
}

// 정점 삽입 연산
void insert_vertex(GraphType* g, int v) {
	if ((g->n) + 1 > MAX_VERTICES) {
		fprintf(stderr, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType* g, int u, int v) {
	GraphNode* node;
	if (u >= g->n || v >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	if (g->adj_list[u] == NULL) { // insert_first
		node = (GraphNode*)malloc(sizeof(GraphNode));
		node->vertex = v;
		node->link = g->adj_list[u];
		g->adj_list[u] = node;
	}
	else { //insert_last
		node = g->adj_list[u];
		while (node->link != NULL)
			node = node->link;
		node->link = (GraphNode*)malloc(sizeof(GraphNode));
		node->link->vertex = v;
		node->link->link = NULL;
	}
}

void print_adj_list(GraphType* g) {
	for (int i = 0; i < g->n; i++) {
		GraphNode* p = g->adj_list[i];
		printf("정정 %d의 인접 리스트", i);
		while (p != NULL) {
			printf("-> %d", p->vertex);
			p = p->link;
		}
		printf("\n");
	}
}

// 깊이 우선 탐색 (DFS)
int visited[MAX_VERTICES];
void DFS(GraphType* g, int v) {
	GraphNode* w;
	visited[v] = 1; // TRUE 
	printf("정점%d -> ", v);
	for (w = g->adj_list[v]; w; w = w->link) {
		if (!visited[w->vertex])
			DFS(g, w->vertex);
	}
}

int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	// 정점 삽입 
	for (int i = 0; i <= 7; i++)
		insert_vertex(g, i);

	// 에지 삽입 
	// 인접 리스트는 오름차순으로 정렬한다. insert_edge(g,u정점,u랑 인접한 v정점), (v가 작은 순서대로 삽입) 
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 1, 0);
	insert_edge(g, 1, 3);
	insert_edge(g, 1, 4);
	insert_edge(g, 2, 0);
	insert_edge(g, 2, 5);
	insert_edge(g, 2, 6);
	insert_edge(g, 3, 1);
	insert_edge(g, 3, 7);
	insert_edge(g, 4, 1);
	insert_edge(g, 4, 7);
	insert_edge(g, 5, 2);
	insert_edge(g, 5, 7);
	insert_edge(g, 6, 2);
	insert_edge(g, 6, 7);
	insert_edge(g, 7, 3);
	insert_edge(g, 7, 4);
	insert_edge(g, 7, 5);
	insert_edge(g, 7, 6);

	print_adj_list(g);

	printf("\n깊이 우선 탐색\n");
	DFS(g, 0);
	printf("end\n");
	free(g);
	return 0;
}

adjacency matrix Version (인접 행렬 버전)

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

#define MAX_VERTICES 50
typedef struct GraphType {
	int n; // 정점의 개수
	int adj_mat[MAX_VERTICES][MAX_VERTICES];
}GraphType;

// 그래프 초기화
void init(GraphType* g) {
	int r, c;
	g->n = 0;
	for (r = 0; r < MAX_VERTICES; r++) {
		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, "그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge(GraphType* g, int start, int end) {
	if (start >= g->n || end >= g->n) {
		fprintf(stderr, "그래프: 정점 번호 오류");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1;
}

void print_adj_list(GraphType* g) {
	for (int i = 0; i < g->n; i++) {
		for (int j = 0; j < g->n; j++) {
			printf("%2d ", g->adj_mat[i][j]);
		}
		printf("\n");
	}
}

// 깊이 우선 탐색 (DFS)
int visited[MAX_VERTICES];
void DFS(GraphType* g, int v) {
	int w;
	visited[v] = 1; // TRUE 
	printf("정점%d -> ", v);
	for (w = 0; w < g->n; w++) {
		if (g->adj_mat[v][w] && !visited[w])
			DFS(g, w);
	}
}

int main() {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	init(g);
	// 정점 삽입 
	for (int i = 0; i <= 7; i++)
		insert_vertex(g, i);

	// 에지가 있으면 인접 행렬에 삽입  
	insert_edge(g, 0, 1);
	insert_edge(g, 0, 2);
	insert_edge(g, 1, 3);
	insert_edge(g, 1, 4);
	insert_edge(g, 3, 7);
	insert_edge(g, 4, 7);
	insert_edge(g, 7, 5);
	insert_edge(g, 5, 2);
	insert_edge(g, 2, 6);
	insert_edge(g, 7, 6);

	print_adj_list(g);

	printf("\n깊이 우선 탐색\n");
	DFS(g, 0);
	printf("end\n");
	free(g);
	return 0;
}