Graph(그래프) - 1

1. 그래프란

 - 그래프(graph)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조다.

 - 트리도 그래프의 하나의 특수한 종류로 볼 수 있다.

 - 그래프는 수학자 오일러(Euler)에 의해 처음 창안되었다. (모든 다리를 한 번만 건너서 출발했던 장소로 돌아올 수 있는가?)

 - 위치는 정점(vertex), 위치간의 관계인 다리는 간선(edge)로 표현

 - 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로를 오일러 경로(Eulerian tour)라 정의하고 모든 정점에 연결된 간선의 개수가 짝수일 때만 오일러 경로가 존재한다는 오일러 정의를 증명하였다.

 

 1) 그래프의 용어

  - 그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다.

  - 정점은 노드(node)라고도 불리며, 간선은 링크(link)라고도 불린다.

  - 그래프는 오직 정점과 간선의 집합일 뿐이며 그래프의 시각적 표현은 이해를 돕는 역할만을 함에 주의해야 한다.

  - 간선의 종류에 따라 무방향 그래프(undirected graph)와 방향 그래프(directed graph)로 구분된다.

  - 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(weighted graph) 또는 네트워크(network)라 한다.

  - 네트워크는 도로의 길이, 회로 소자의 용량, 통신망의 사용료 등을 표현할 수 있다.

  - 인접 정점(adjacent vertex)이란 간선에 의해 직접 연결된 정점

  - 차수(degree)는 하나의 정점에 인접한 정점의 수

  - 방향 그래프에서는 외부에서 오는 간선의 수를 진입 차수(in-degree), 외부로 향하는 간선의 수를 진출 차수(out-degree)

  - 경로 길이(path length)란 경로를 구성하는 데 사용된 간선의 수, 경로 중에서 반복되는 간선이 없을 경우에 단순 경로(simple path), 시작 정점과 종료 정점이 동일하다면 사이클(cycle)

  - 무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 연결되었다고 하며, 이러한 무방향 그래프를 연결 그래프(connected graph)라 부른다.

  - 트리는 그래프의 특수한 형태로서 사이클을 가지지 않는 연결 그래프이다.

  - 그래프에 속해 있는 모든 정점이 서로 연결되어 있는 그래프를 완전 그래프(complete graph)라 한다.

 

2. 그래프 추상 데이터 타입

 - 객체 : 정점의 집합과 간선의 집합

 - 연산 :

•  create_graph()
•  init(g)
•  insert_vertex(g, v) - 그래프 g에 정점 v를 삽입한다.
•  insert_edge(g, u, v) - 그래프 g에 간선 (u, v)를 삽입한다.
•  delete_vertex(g, v) - 그래프 g의 정점 v를 삭제한다.
•  delete_edge(g, u, v) - 그래프 g의 간선 (u, v)를 삭제한다.
•  is_empty(g) - 그래프 g가 공백 상태인지 확인한다.
•  adjacent(v) - 정점 v에 인접한 정점들의 리스트를 반환한다.
•  destroy_graph(g) - 그래프 g를 제거한다.

 

3. 그래프의 표현 방법

 - 2차원 배열을 사용하는 인접 행렬(adjacency matrix)과 연결 리스트를 사용하는 인접 리스트(adjacency list)의 두 가지 방법이 있다.

 

 1) 인접 행렬

  - 무방향 그래프의 인접 행렬은 대칭 행렬이 된다.

  - 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있다.

  - 밀집 그래프(dense graph)를 표현하는 경우에는 적합하나 희소 그래프(sparse graph)의 경우에는 메모리의 낭비가 크므로 적합하지 않다

  - 모든 간선의 수를 알아내려면 n2번의 조사가 필요하게 되어 O(n2)의 시간이 요구된다.

#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_vertex(GraphType *g, int v)
{
	if( ((g->n)+1) > MAX_VERTICES ){ 
		fprintf(stderr,"그래프: 정점의 개수 초과");
		return;
	}
	g->n++;
}
// 간선 삽입 연산
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;
}

 

 2) 인접 리스트

  - 헤드 포인터들은 하나의 배열로 구성되어 있다.

  - 정점의 수가 n개이고 간선의 수가 e개인 무방향 그래프를 표시하기 위해서는 n개의 헤드 포인터와 2e개의 노드가 필요하다. 따라서 인접 리스트 표현은 희소 그래프의 표현에 적합하다.

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

// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
// 매번 리스트의 젤 앞에 삽입
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;
}

 

 

[Reference]

• 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년