[C언어로 쉽게 풀어쓴 자료구조] Chapter10. 그래프 I (1)

10.1 그래프란?

● 그래프: 객체 사이의 연결 관계를 표현할 수 있는 자료구조

- ex) 지하철 노선도, 전기 회로 그래프, 운영체제의 프로세스 및 자원들의 연결 관계 그래프

- 선형리스트나 트리의 구조로는 표현하기 어려운 복잡한 문제들을 표현할 수 있다. (트리도 일종의 그래프)

- 인접 행렬이나 인접 리스트로 메모리에 표현되고 처리될 수 있다.

- 문제 해결을 위한 도구로서 많은 이론과 응용이 존재

 

● 그래프의 역사

수학자 오일러의 konigsbert bridge 문제는

'각 지역에서 출발하여 7개의 모든 다리를 단 한 번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가'라는 문제다.

오일러는 이 문제에 대해 '각 지역에 연결된 다리의 개수가 모두 짝수여야함'을 증명하였다.

 

- A, B, C, D 지역을 정점(node)으로, 1, 2, 3.. 같은 다리는 간선(edge)으로 표현하여 단순한 그래프로 만들 수 있다.

 

● 그래프로 표현할 수 있는 것들

도로, 미로, 선수과목

도로, 미로, 선수과목들은 정점과 간선을 이용해서 효과적으로 나타낼 수 있다.

 

10.2 그래프의 정의와 용어

● 그래프의 정의: 정점(vertex)과 간선(edge)들의 유한 집합으로, G = (V, E)로 표시한다.

- 정점: 여러 가지 특성을 가질 수 있는 객체, node라고도 불린다.

- 간선: 정점들간의 관계, link라고도 불린다.

 

● 그래프의 종류

- 무방향 그래프: 간선을 통해서 양방향의 노드로 갈 수 있음을 나타내며 (A, B)로 나타낸다. 즉 (A, B)와 (B, A)는 같은 간선이다.

- 방향 그래프: 간선에 방향성이 존재하는 그래프이며 <A, B>로 나타낸다. 이 간선은 노드 A에서 B로만 갈 수 있는 간선이다. 

 

- 네트워크: 간선에 가중치를 할당하면 두 정점간의 연결 강도까지 나타낼 수 있다.

이렇듯 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프 또는 네트워크라고 한다.

 

- 부분 그래프: 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 부분 그래프(subgraph)라 한다.

그래프 G의 부분 그래프 S는 다음과 같은 수식을 만족시킨다. V(S) ⊆ V(G) , E(S) ⊆ E(G)

 

- 연결 그래프: 무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다면 G는 '연결됨'

*트리는 사이클을 가지지 않는 연결 그래프

- 완전 그래프: 그래프에 속한 모든 정점이 서로 연결되어 있는 그래프.

*정점 수가 n이면 하나의 정점은 n-1개의 다른 정점과 연결되므로 간선의 수는 n(n-1)/2가 된다.

 

- 정점의 차수: 무방향 그래프에서 정점의 차수 = 그 정점에 인접한 정점의 수

*인접 정점: 간선에 의해 직접 연결된 정점

*모든 정점의 차수를 합하면 간선 수의 2배

*방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수, 외부로 향하여 나가는 간선의 개수를 진출 차수라 한다.

- 경로: 정점 s에서 e까지의 경로는 정점의 나열 s, v1, v2,..., vk, e로서, 나열된 정점들 간에는 반드시 간선이 존재해야 한다.

*경로 중에 반복되는 간선이 없을 경우 단순 경로, 단순경로의 시작 정점과 종료 정점이 동일하다면 이 경로는 사이클이라 한다.

 

♠ 369p Quiz

01 V(G) = { 0, 1, 2, 3, 4}   E(G)={ (0,1), (0,2), (0,3), (1,2), (2,3), (1,4), (3,4) }

02 V(G) = { 0, 2, 3, 4}       E(G)={ <0,4>, <4,2>, <2,3>, <2,4>, <2,2> }

 

10.3 그래프의 표현 방법

그래프를 표현하는 두 가지 방법

인접행렬(adjacency matrix): 2차원 배열을 사용하여 그래프를 표현

인접 리스트(adjacency list): 연결 리스트를 사용하는 그래프를 표현

 

● 인접행렬

정점수가 n일 때 nxn의 2차원 배열인 인접 행렬 M의 각 원소를 다음의 규칙에 의해 할당한다.

if( 간선 (i, j)가 그래프에 존재) M[i][j] = 1;

other                                    M[i][j] = 0;

*자체 간선(0,0), (1,1) 등은 허용되지 않으므로 인접 행렬의 대각선 성분은 모두 0

*무방향 그래프에서의 인접행렬은 (i,j) = (j,i)에 의해 대칭행렬이므로 배열의 하위 삼각만 저장하면 전체 배열을 앎.

 

n개의 정점을 가지는 그래프를 인접 행렬로 표현하려면 n^2개의 메모리 공간이 필요하고,

간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하기엔 적합하나, 간선이 적은 희소 그래프(sparse garph)에는 부적합.

 

간선의 존재 여부는 M[u][v]의 값을 조사해서 O(1) 시간 안에 알 수 있다

정점 i에 대한 차수는 degree(i) = n-1∑k=0 M[i][k] , 즉 인접 배열의 i번째 행에 있는 값을 모두 더하여 O(n)의 연산에 알 수 있다.

* 모든 간선의 수를 알려면 n^2번의 조사가 필요하여 O(n^2)의 시간이 필요

 

● 인접행렬을 이용한 그래프 추상 데이터 타입의 구현

정점을 삽입하는 연산은 n을 하나 증가

간선을 삽입하는 연산은 무방향 그래프일 경우 adj_mat[start][end]와 adj_met[end][start]에 1삽입

                                        방향 그래프일 경우 adj_mat[start][end]에만 1을 삽입

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,"정점 번호 오류");
	}
	g->adj_mat[start][end]=1;
	g->adj_mat[end][start]=1;
}

 

● 인접 리스트

각각의 정점에 인접한 정점들을 연결리스트로 표시.

각 연결 리스트들의 노드들은 인접 정점을 저장, 각 연결 리스트의 헤더 노드들은 하나의 배열로 구성.

정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결 리스트에 쉽게 접근

*무방향 그래프의 경우 간선 (i,j)는 i의 연결리스트에 인접 정점 j로서 한번, j의 연결리스트에 인접 정점 i로서 다시 한번 표현

*그래프 표현의 일관성을 위해 인접 리스트가 정점의 오름차순으로 연결된다고 가정

 

정점의 수가 n이고 간선의 수가 e인 무방향 그래프는 n개의 연결 리스트 및 n개의 헤더 노드와 2e개의 노드가 필요

 

간선의 존재 여부 및 정점 i의 차수를 알기 위해서는 인접 리스트에서의 정점 i의 연결 리스트를 탐색해야 하므로

연결 리스트에 있는 노드의 수만큼, 즉 정점차수만큼의 시간이 필요.

n개 정점과 e개 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 모든 인접 리스트를 조사해야 하므로 O(n+e)

 

● 인접리스트를 이용한 그래프 추상 데이터 타입의 구현

 

typedef struct GraphNode{
	int vertex;
	struct GraphNode* link;
}GraphNode;

typedef struct GraphType{
	int n;
	GraphNode* adj_list[MAX_VERTICES];
}GraphType;

그래프에 존재하는 정점의 개수 n을 담고 각 정점마다 하나의 연결 리스트를 가질 수 있게 노드 구조체를 만든다.

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 = (GraphNode*)malloc(sizeof(GraphNode));
	if(u >= g->n || v>=g->n){
		fprintf(stderr,"정점 번호 오류");
	}
	node->vertex =v;
	node->link = g->adj_list[u];
	g->adj_list[u] = node; // 리스트의 처음에 삽입
	
}

 

♠ 377p Quiz

01 02 

03

int get_degree(GraphType *g,int v){
	int count=0;
	for(int j=0;j<g->n;j++){
		if(g->adj_mat[v][j]==1){
			count++;
		}
	}
	return count;
}

int get_degree(GraphType* g, int v){
	GraphNode *n = g->adj_list[v];
	int count=0;
	while(n!=NULL){
		count++;
		n = n->link;
	}
	return count;
}