1. 깊이 우선 탐색(DFS : Depth-First Search)
: 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없으면
가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행한다.
: 되돌아가기 위해서는 스택이 필요하다.(재귀함수로 묵시적인 스택 활용 가능)
1) 핵심 코드 - 인접행렬 이용
void dfs_mat(GraphType *g, int v)
{
int w;
visited[v] = 1;
for (w = 0; w < g->n; w++)
if ((g->adj_mat[v][w] == 1) && (visited[w] == 0)) {
printf("<%d %d>\n", v, w);
dfs_mat(g, w);
}
}
- visited[] 배열에 해당 정점을 방문했다고 표시한다.
- 해당 정점에 연결되어 있고, 아직 방문하지 않은 정점을 차례로 방문한다.
2) 전체 코드 - 인접행렬 이용
#include <stdio.h>
#define MAX_VERTICES 50
typedef struct GraphType {
int n;
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES] = {0};
void graph_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_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 read_graph(GraphType *g, char *filename)
{
int number, u, v;
FILE *fp;
fp = fopen(filename, "rt");
if (fp == NULL)
{
printf("file %s open error!\n", filename);
return;
}
fscanf(fp, "%d\n", &number);
g->n = number;
// 구현: while (fscanf(fp, "%d\n", &n) != EOF) {...} 을 사용한다.
while(fscanf(fp, "%d\n", &u) != EOF && fscanf(fp, "%d\n", &v) != EOF){
insert_edge(g, u, v);
}
fclose(fp);
}
void dfs_mat(GraphType *g, int v)
{
int w;
visited[v] = 1;
for (w = 0; w < g->n; w++)
if ((g->adj_mat[v][w] == 1) && (visited[w] == 0)) {
printf("<%d %d>\n", v, w);
dfs_mat(g, w);
}
}
int main(void)
{
GraphType graph;
int v;
graph_init(&graph);
read_graph(&graph, "infile.txt");
//read_graph(&graph, "infile2.txt");
printf("Enter 정점:");
scanf("%d", &v);
dfs_mat(&graph, v);
}
3) 핵심 코드 - 인접리스트 이용
void dfs_list(GraphType *g, int v){
GraphNode *w;
visited[v] = 1;
for(w=g->adj_list[v]; w; w=w->link){
if(!visited[w->vertex]){
printf("<%d %d>\n", v, w->vertex);
dfs_list(g, w->vertex);
}
}
}
4) 전체 코드 - 인접리스트 이용
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
typedef int element;
typedef struct GraphNode
{
int vertex;
struct GraphNode *link;
} GraphNode;
typedef struct GraphType {
int n; // 정점의 개수
GraphNode *adj_list[MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES] = {0};
void graph_init(GraphType *g)
{
int v;
g->n=0;
for(v=0;v<MAX_VERTICES;v++){
g->adj_list[v]=NULL; }
}
void insert_edge(GraphType *g, int u, int v)
{
GraphNode *node_u, *node_v;
if( u >= g->n || v >= g->n ){
fprintf(stderr, "그래프 : 정점 번호 오류");
return;
}
node_u = (GraphNode *)malloc(sizeof(GraphNode));
if (node_u == NULL) {
fprintf(stderr, "malloc 오류"); return;
}
node_u->vertex = v;
node_u->link = g->adj_list[u]; // g->adj_list[u] 는 링크로서 vertex가 있는 첫 번째 노드를 가리킴
g->adj_list[u] = node_u;
node_v = (GraphNode *)malloc(sizeof(GraphNode));
if (node_v == NULL) {
fprintf(stderr, "malloc 오류"); return;
}
node_v->vertex = u;
node_v->link = g->adj_list[v];
g->adj_list[v] = node_v;
}
void remove_node(GraphNode **phead, element item) { // 포인터에 대한 포인터를 꼭 써야하는 경우 !
GraphNode *p, *prevp;
if (*phead == NULL)
printf("그래프가 비었습니다\n");
else if ((*phead)->vertex == item) {
p = *phead;
*phead = (*phead)->link;
free(p);
}
else {
p = *phead;
do {
prevp = p;
p = p->link;
}while (p != NULL && p->vertex != item);
if (p != NULL) {
prevp->link = p->link;
free(p);
}
else
printf("삭제하려는 %d 값이 없습니다\n", item);
}
}
void delete_edge(GraphType *g, int u, int v)
{
if( u >= g->n || v >= g->n ){
fprintf(stderr, "그래프 : 정점 번호 오류");
return;
}
remove_node(&g->adj_list[u], v);
remove_node(&g->adj_list[v], u);
}
void read_graph(GraphType *g, char *filename)
{
int number, u, v;
FILE *fp;
fp = fopen(filename, "rt");
if (fp == NULL)
{
printf("file open error!\n");
return;
}
fscanf(fp, "%d\n", &number);
g->n = number;
// 구현: while (fscanf(fp, "%d\n", &n) != EOF) {...} 을 사용한다.
while(fscanf(fp, "%d\n", &u) != EOF && fscanf(fp, "%d\n", &v) != EOF){
insert_edge(g, u, v);
}
fclose(fp);
}
void write_graph(GraphType *g, char *filename)
{
int u;
FILE *fp;
GraphNode *ptr;
if (filename == NULL) fp = stdout;
else {
fp = fopen(filename, "w");
if (fp == NULL)
{
printf("file %s open error!\n", filename);
return;
}
}
fprintf(fp, "%d\n", g->n);
for(u=0; u<(g->n); u++){
ptr = g->adj_list[u];
while (ptr != NULL){
if(u < ptr->vertex)
fprintf(fp, "%d %d\n", u, ptr->vertex);
ptr = ptr->link;
}
}
if (filename != NULL) fclose(fp);
}
void dfs_list(GraphType *g, int v){
GraphNode *w;
visited[v] = 1;
for(w=g->adj_list[v]; w; w=w->link){
if(!visited[w->vertex]){
printf("<%d %d>\n", v, w->vertex);
dfs_list(g, w->vertex);
}
}
}
int main(void)
{
GraphType g;
int v;
graph_init(&g);
read_graph(&g, "input.txt");
printf("Enter 정점:");
scanf("%d", &v);
dfs_list(&g, v);
}
2. 넓이 우선 탐색(BFS : Breadth - First Search)
: 시작 정점으로부터 가까운 정점을 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
: 큐를 사용하여 구현한다.
1) 핵심 코드 - 인접행렬 이용
void bfs_mat(GraphType *g, int v)
{
int w;
QueueType q;
init(&q);
visited[v] = 1;
enqueue(&q, v);
while(!is_empty(&q)){
v = dequeue(&q);
for(w=0; w<g->n; w++){
if (g->adj_mat[v][w] == 1 && visited[w] == 0) {
visited[w] = 1;
enqueue(&q, w);
printf("<%d %d>\n", v, w);
}
}
}
}
2) 전체 코드 - 인접행렬 이용
#include <stdio.h>
#include <stdlib.h>
#include "queue.h" // <------
#define MAX_VERTICES 50
typedef struct GraphType {
int n;
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES] = {0};
void graph_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_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 read_graph(GraphType *g, char *filename)
{
int number, u, v;
FILE *fp;
fp = fopen(filename, "rt");
if (fp == NULL)
{
printf("file %s open error!\n", filename);
return;
}
fscanf(fp, "%d\n", &number);
g->n = number;
// 구현: while (fscanf(fp, "%d\n", &n) != EOF) {...} 을 사용한다.
while(fscanf(fp, "%d\n", &u) != EOF && fscanf(fp, "%d\n", &v) != EOF){
insert_edge(g, u, v);
}
fclose(fp);
}
int visited[MAX_VERTICES];
void init(QueueType *q);
void enqueue(QueueType *q, element item);
element dequeue(QueueType *q);
int is_empty(QueueType *q);
void bfs_mat(GraphType *g, int v)
{
int w;
QueueType q;
init(&q);
visited[v] = 1;
enqueue(&q, v);
while(!is_empty(&q)){
v = dequeue(&q);
for(w=0; w<g->n; w++){
if (g->adj_mat[v][w] == 1 && visited[w] == 0) {
visited[w] = 1;
enqueue(&q, w);
printf("<%d %d>\n", v, w);
}
}
}
}
int main(void)
{
GraphType graph;
int v;
graph_init(&graph);
read_graph(&graph, "infile.txt");
//read_graph(&graph, "infile2.txt");
printf("Enter 정점:");
scanf("%d", &v);
bfs_mat(&graph, v);
}
3) 핵심 코드 - 인접리스트 이용
void bfs_list(GraphType *g, int v)
{
GraphNode *w;
QueueType q;
init(&q);
visited[v] = TRUE;
enqueue(&q, v);
while(!is_empty(&q)){
v = dequeue(&q); // 빼고
for(w=g->adj_list[v]; w; w = w->link)
if(!visited[w->vertex]){
printf("<%d %d>\n", v, w->vertex);
visited[w->vertex] = TRUE;
enqueue(&q, w->vertex); // 넣고
}
}
}
4) 전체 코드 - 인접리스트 이용
#include <stdio.h>
#include <stdlib.h>
#include "queue.h" // <------
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
typedef struct GraphNode
{
int vertex;
struct GraphNode *link;
} GraphNode;
typedef struct GraphType {
int n;
GraphNode *adj_list[MAX_VERTICES];
} GraphType;
void graph_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++;
}
void insert_edge(GraphType *g, int u, int v)
{
GraphNode *node;
if(u >= g->n || v >= g->n){
fprintf(stderr, "그래프 : 정점 번호 오류");
return;
}
node = (GraphNode *)malloc(sizeof(GraphNode));
node->vertex = v;
node->link = g->adj_list[u];
g->adj_list[u] = node;
node = (GraphNode *)malloc(sizeof(GraphNode));
node->vertex = u;
node->link = g->adj_list[v];
g->adj_list[v] = node;
}
int visited[MAX_VERTICES];
void init(QueueType *q);
void enqueue(QueueType *q, element item);
element dequeue(QueueType *q);
int is_empty(QueueType *q);
void bfs_list(GraphType *g, int v)
{
GraphNode *w;
QueueType q;
init(&q);
visited[v] = TRUE;
enqueue(&q, v);
while(!is_empty(&q)){
v = dequeue(&q); // 빼고
for(w=g->adj_list[v]; w; w = w->link)
if(!visited[w->vertex]){
printf("<%d %d>\n", v, w->vertex);
visited[w->vertex] = TRUE;
enqueue(&q, w->vertex); // 넣고
}
}
}
void read_graph(GraphType *g, char *filename)
{
int number, u, v;
FILE *fp;
fp = fopen(filename, "rt");
if (fp == NULL)
{
printf("file %s open error!\n", filename);
return;
}
fscanf(fp, "%d\n", &number);
g->n = number;
// 구현: while (fscanf(fp, "%d\n", &n) != EOF) {...} 을 사용한다.
while(fscanf(fp, "%d %d\n", &u, &v) != EOF){
insert_edge(g, u, v);
}
fclose(fp);
}
int main(void)
{
GraphType graph;
int v;
graph_init(&graph);
read_graph(&graph, "infile.txt");
printf("Enter 정점:");
scanf("%d", &v);
bfs_list(&graph, v);
}
3. 시간복잡도 분석
1) 인접행렬 이용 - O(n^2)
2) 인접리스트 이용 - O(n+e)
