자료구조 :: 그래프(1) 정의, 그래프의 구현

# 그래프(graph)

그래프는 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조다. 그래프는 수학자 오일러(Euler)에 의해
처음 창안되었다.

■ 그래프의 용어 

그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다.
정점은 여러가지 특성을 가질 수 있는 객체를 의미하고, 간선을 이러한 정점들 간의 관계를 의미한다.
간선의 종류에 따라 그래프는 무방향 그래프와 방향 그래프로 구분된다. 무방향 그래프의 간선은 간선을 통해서
양방향으로 갈수 있음을 나타내며 정점 A와 정점 B를 연결하는 간선은 (A,B)와 같이 정점의 쌍으로 표현한다.
(A,B)와 (B,A)는 동일한 간선이 된다. 방향 그래프는 간선에 방향성이 존재하는 그래프로서 도로의 일방통행길과
마찬가지로 간선을 통하여 한쪽 방향으로만 갈수 있음을 나타낸다. 정점 A에서 정점 B로만 갈 수 있는 간선은
<A,B>로 표시한다. 방향 그래프에서 <A,B>와 <B,A>는 서로 다른 간선이다.
간선에 가중치를 할당하게 되면, 간선의 역햘이 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수
있으므로 보다 복잡한 관계를 표현할 수 있게 된다. 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프
또는 네트워크라고 한다.

그래프에서 인접 정점이란 간선에 의해 직접 연결된 정점을 뜻한다. 무방향 그래프에서 정점의 차수는 그 정점에
인접한 정점의 수를 말한다.  무방향 그래프에 존재하는 정점의 모든 차수를 합하면 그래프의 간선 수의 2배가
된다. 이는 하나의 간선이 두개의 정점에 인접하기 때문이다. 방향 그래프에서는 외부에서 오는 간선의 수를
진입 차수라 하고 외부로 향하는 간선의 수를 진출 차수라 한다.

경로의 길이란 경로를 구성하는데 사용된 간선의 수를 의미한다. 경로 중에서 반복되는 간선이 없을 경우에
이러한 경로를 단순 경로라 한다. 만약에 단순 경로의 시작 정점과 종료 정점이 동일 하다면 이러한 경로를 싸이클
이라 한다.

그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프를 완전 그래프라고 하며 무방향 완전 그래프의 정점
수를 n이라고 할때, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n*(n-1)/2가 된다.


■ 그래프의 표현 방법

그래프를 메모리 표현하는 방법으로 2차원 배열을 사용하는 인접 행렬과 연결리스트를 사용하는 인접 리스트의
두 가지 방법이 있다. 그래프 문제의 특성에 따라 두 가지 표현 방법은 각각 메모리 사용량과 처리 시간 등에서
장단점을 가지므로, 문제에 적합한 표현 방법을 선택해야 한다.

GraphType.cpp

[인접행렬, 인접리스트의 구현]

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

#define MAX_VERTEX 10

#if1

/* 배열로 구현한 그래프 */

typedefstruct{ 
int n; // 정점의 갯수
int adj_mat[MAX_VERTEX][MAX_VERTEX]; 
}GraphType; 

void InitGraph(GraphType *g) 
{ 
int i,j; 

    g->n=0; 

for(i=0;i<MAX_VERTEX;i++) 
for(j=0;j<MAX_VERTEX;j++) 
            g->adj_mat[i][j]=0; 
} 

void InsertVertex(GraphType *g,int v) 
{ 
if((g->n)+1 > MAX_VERTEX) 
    { 
        printf("정점 갯수 초과\n"); 
        exit(-1); 
    } 

    g->n++; 
} 

void InsertEdge(GraphType *g,int start,int end) 
{ 
if(start >= g->n || end >= g->n) 
    { 
        printf("잘못된 정점 입력\n"); 
        exit(-1); 
    } 

    g->adj_mat[start][end]=1;  
    g->adj_mat[end][start]=1; 
} 

#else

/* 연결리스트로 구현한 그래프 */

typedefstruct GraphNode 
{ 
int vertex; 
    GraphNode *link; 
}GraphNode; 

typedefstruct GraphType 
{ 
int n; // 정점의 갯수
    GraphNode *adj_list[MAX_VERTEX]; 
}GraphType; 

void InitGraph(GraphType *g) 
{ 
int v; 
    g->n=0; 
for(v=0;v<MAX_VERTEX;v++) 
        g->adj_list[v]=NULL; 
} 

void InsertVertex(GraphType *g,int v) 
{ 
if((g->n)+1 > MAX_VERTEX) 
    { 
        printf("정점 갯수 초과\n"); 
        exit(-1); 
    } 

    g->n++; 
} 

void InsertEdge(GraphType *g,int u,int v) 
{ 
    GraphNode *node; 
if(u >= g->n || v >= g->n) 
    {         
        printf("잘못된 정점 입력\n"); 
        exit(-1); 
    } 

    node=(GraphNode*)malloc(sizeof(GraphNode)); 
    node->vertex=v; 
    node->link = g->adj_list[u]; 

    g->adj_list[u]=node; 
} 

#endif

int main() 
{ 
    GraphType graph; 
int i; 

    InitGraph(&graph); 

for(i=0;i<MAX_VERTEX;i++) 
        InsertVertex(&graph,i); 

    InsertEdge(&graph,1,5); 
    InsertEdge(&graph,2,6); 
    InsertEdge(&graph,4,7); 
    InsertEdge(&graph,5,2); 
    InsertEdge(&graph,6,3); 

return0; 
}