[자료구조] 그래프

그래프란?

: 그래프(graph)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다. 그래프는 정점과 간선들의 집합이라고 할 수 있습니다. 그래프는 보통 지도에서 자주 사용하는 자료구조인데, 예를 들어 인천에서 서울까지의 최단거리, 최소비용 등을 구하는 데 사용합니다.

 

필요한 개념 및 용어

1. 정점(vertex) 와 간선(edge)

• 정점은 그래프의 위치, 간선은 정점들 간의 관계를 의미합니다.

2. 무방향 그래프(undirected graph) 와 방향 그래프(directed graph)

• 무방향 그래프는 간선을 통해 양 방향 이동이 가능하다. 
• 방향 그래프는 간선을 통해 단 방향 이동이 가능하다.

         무방향 그래프                                         방향 그래프                         

3. 가중치 그래프(weight graph)

• 간선에 연결 강도를 표시할 수 있는 그래프 (ex 통행료, 간선의 길이 등)

4. 인접 정점(adjacent vertex) 와 차수(dgree)

• 인접 정점(adjacent vertex)이란 간선에 의해 직접 연결된 정점을 의미한다.
• 차수는 무방향 그래프인 경우와 방향 그래프인 경우로 나뉜다.

< 무방향 그래프 >
차수 : 하나의 정점에 인접한 정점의 수를 의미한다.

< 방향 그래프 >
진입 차수(내차수) : 현재 정점으로 들어오는 간선의 수를 의미한다.
진출 차수(외차수) : 현재 정점에서 외부로 향하는 간선의 수를 의미한다.

 

 

5. 경로(path)

• 경로 길이(path length) : 경로를 구성하는 데 사용된 간선의 수를 의미한다.
• 단순 경로(simple path) : 경로 중에서 반복되는 간선이 없는 경우를 의미한다.
• 사이클(cycle) : 경로의 시작과 끝이 같은 경우를 의미한다.

 

 

6. 연결 그래프(connected graph)

• 연결 그래프(connected graph) : 모든 정점 쌍에 대하여 항상 경로가 존재하는 그래프.
• 비연결 그래프(unconnected graph) : 간선이 없는 정점을 갖는 그래프.
• 완전 그래프(complete graph) : 모든 정점이 서로 연결되어 있는 그래프.

 

 

그래프 표현

지금까지 보여주었던 사진, 그림 자료들은 이해를 돕기 위한 것들 일 뿐입니다. 프로그램으로 배열이나 리스트를 선언하여 
특정 관계를 만들어 주는 것뿐이지, 저런 그래픽적인 작업은 하지 않습니다.

 

 

1. 인접 행렬(adjacency matrix)

 : 그래프의 관계를 메모리에 표현하는 방법으로 2차원 배열을 사용한다. 배열의 특성상 항상 N^2 의 크기를 만들 수밖에 없다. 인접 행렬 방식의 그래프 구현은 밀집 그래프(dense graph)를 표현하는 경우 적합하다. 반면에 적은 간선을 가지는 희소 그래프(sparse graph)의 경우 메모리 낭비가 크므로 부적합하다.

 

코드구현

 

 

#include <iostream>

//인접행렬로 구현한 그래프 알고리즘은 간선이 많은경우에
//사용하는 것이 적합하다. 희소 그래프에 사용한다면
//불필요한 메모리 소비가 커진다.

#include <stdio.h>

#define MAX_VERTICES 50
typedef struct GraphType {
	int n;  // n^2  행렬구조
	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; //모든 데이터를 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){
		//간선이 n * n 행렬 크기 안에 존재안하는 경우
		fprintf(stderr, "그래프 : 정점 번호 오류");
		return;
	}
	g->adj_mat[start][end] = 1;
	g->adj_mat[end][start] = 1; 
	// 무방향 그래프로 양방향 간선 추가
}

 

2. 인접 리스트(adjacency list)

 : 각각의 정점에 인접한 정점들을 연결 리스트로 구현한 것이다. 인접 리스트로 구현하는 경우 필요한 간선들만 구현하는 것이 가능하기 때문에 희소 그래프에 적합하다.