자료구조 3 - 1) 그래프

 

 

 

 

 

 

 

 

 

1. 그래프 관련 용어

1) 그래프 G는 (V, E) 로 표시한다.

 

- 정점(Vertices)

: '노드' 라고도 불린다.

 

- 간선(Edge)

: '링크' 이라고도 불린다.

 

 

 

 

 

2) 인접 정점 & 차수

- 인접 정점 : 간선에 의해 직접 연결된 정점이다.

ex) G1에서 정점 0의 인접 정점 = 정점 1, 정점 2, 정점 3

- 무방향 그래프의 차수 : 하나의 정점에 연결된 다른 정점의 수이다.

ex) G1에서 정점 0의 차수 = 3

- 방향 그래프의 차수 ( 모든 진입 차수, 진출 차수의 수는 간선의 수와 동일하다. )

① 진입 차수 : 외부에서 오는 간선의 수

② 진출 차수 : 외부로 향하는 간선의 수

 

 

 

 

 

2. 그래프 표현의 예

V(G1) = {0, 1, 2, 3}, E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3)}

V(G2) = {0, 1, 2}, E(G2) = {<0,1>, <1, 0>, <1, 2>}

 

() : 양방향, <> : 일방향

 

 

 

3. 그래프의 종류

1) 무방향 그래프

2) 방향 그래프

3) 가중치 그래프 : 간선에 비용이나 가중치가 할당된 그래프이다. '네트워크' 라고도 한다.

4) 부분 그래프 : 정점 집합 V(G)와 간선 집합 E(G)의 부분 집합으로 이루어진 그래프이다.

 

 

 

 

 

4. 그래프의 경로

 

1) 단순 경로 : 경로 중에서 반복되는 간선이 없는 경로이다.

2) 사이클 : 단순 경로의 시작 정점과 종료 정점이 동일한 경로이다.

 

 

 

5. 그래프의 연결 정도

 

1) 연결 그래프 : 무방향 그래프 G에 있는 모든 정점쌍에 대해 항상 경로가 존재한다.

(a) 연결 그래프, (b) 연결 그래프 아님

 

 

2) 완전 그래프

: 모든 정점이 연결되어 있는 그래프이다.

- n개의 정점을 가진 무방향 완전그래프의 간선의 수 : n (n-1) / 2

if n = 4, 간선의 수 = (4 x 3) / 2 = 6

 

 

 

 

6. 그래프 표현 방법

 

1) 인접행렬 방법

: (a), (b)와 같은 무방향 그래프의 간선의 수는 (1의 개수)/2,

(c)와 같은 방향 그래프의 간선의 개수는 (1의 개수) 이다.

 

#include <stdio.h>
#define MAX_VERTICES 50

typedef struct GraphType {
     int n;
     int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;


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 delete_edge(GraphType *g, int start, int end)
{
    if( start >= g->n || end >= g->n ){
        fprintf(stderr,"그래프 : 정점 번호 오류");
        return;
    }
     
     // ƒ⁄µÂ ª¿‘
    g->adj_mat[start][end] = 0;
    g->adj_mat[end][start] = 0;
}

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);
}

//
void write_graph(GraphType *g, char *filename)
{
     int i, j;
     FILE *fp;
     
     if (filename == NULL) fp = stdout;
     else {
          fp = fopen(filename, "wt");
         if (fp == NULL)
         {
             printf("file %s open error!\n", filename);
              return;
         }
     }
    
    fprintf(fp, "%d\n", g->n);

    // 구현: fprintf(fp, "%d\n", ...)을 사용한다
    for(i=0; i<(g->n); i++){
        for(j=0; j<(g->n); j++){
            if(g->adj_mat[i][j] && i < j)
                fprintf(fp, "%d %d\n", i, j);
        }
    }
    
     if (filename != NULL) fclose(fp);
}


int main(void)
{
    GraphType g;
    graph_init(&g);
    read_graph(&g, "input.txt");
    write_graph(&g, NULL);    // to stdout

    insert_edge(&g, 1, 3);
    write_graph(&g, NULL);    // to stdout

    delete_edge(&g, 2, 0);
    write_graph(&g, NULL);    // to stdout

    write_graph(&g, "output.txt");
}

     

 

 

 

 

 

 

2) 인접리스트 방법

: 각 정점에 인접한 정점들을 인접리스트로 표현한다.

 

 

 

 

#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;


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] = 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);
}

int main(void)
{
    GraphType g;
    graph_init(&g);

    read_graph(&g, "input.txt");
    write_graph(&g, NULL);    // to stdout

    insert_edge(&g, 1, 3);
    write_graph(&g, NULL);    // to stdout

    delete_edge(&g, 2, 0);
    write_graph(&g, NULL);    // to stdout

    write_graph(&g, "output.txt");
}

 

: g->adj_list[u] 는 링크로서 vertex가 있는 첫 번째 노드를 가리킴