자료구조 3 - 2) 그래프 BFS, DFS

 

 

 

 

 

 

 

 

 

 

 

 

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)