10.1 그래프란?
그래프의 소개
- 그래프: 객체 사이의 연결 관계를 표현할 수 있는 자료 구조
그래프의 역사
- Konigsberg의 다리 문제 (오일러 문제): 임의의 지역에서 출발하여 모든 다리를 단 한번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가?
- 'A, B, C, D의 위치가 어떠한 관계로 연결되었는가?'
- 지역 = 정점(vertex)
- 다리 = 간선(edge)
- 오일러 경로: 그래프에 존재하는 모든 간선(edge)를 한번만 통과하면서 처음 정점(node)로 되돌아오는 경로
- 오일러 정리: 모든 정점(node)에 연결된 간선(edge)의 개수가 짝수일 때만 오일러 경로가 존재한다.
그래프로 표현할 수 있는 것들
: 도로, 미로, 선수과목
10.2 그래프의 정의와 용어
그래프의 정의
▶ G = (V, E)
: 정점(vertex)와 간선(edge)들의 유한집합
- V(G): 그래프 G의 정점(vertex)들의 집합 --> |V| = 총 정점의 개수
- E(G): 그래프 G의 간선(edge)들의 집합 --> |E| = 총 간선의 개수
무방향 그래프(undirected graph) vs. 방향 그래프(directed graph)
- 간선의 종류에 따라:
가중치 그래프 (weighted graph)
: 간선에 가중치(weight)가 할당된 그래프
부분 그래프 (subgraph)
: 어떤 그래프의 정점(vertex)의 일부와 간선(edge)의 일부로 이루어진 그래프
그래프 기본 용어
- 인접 정점(adjacent vertex): 하나의 정점(vertex)에서 간선(edge)에 의해 직접 연결된 정점
▶ 정점의 차수(degree)
- 무방향 그래프: 그 정점에 인접한 정점의 수
--> 모든 정점의 차수 = 2*간선 수 (하나의 간선이 두 개의 정점에 인접하기 때문) - 방향 그래프
- 진입 차수(in-degree): 외부에서 오는 간선의 개수
- 진출 차수(out-degree): 외부로 향하는 간선의 개수
경로 (path)
: 하나의 정점으로부터 다른 정점까지의 경로 - 정점의 나열
- 단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경로
- 사이클(cycle): 시작 정점과 종료 정점이 동일한 경로
- 단순 사이클(simple cycle): 반복되는 정점이 없고, 시작 정점과 종료 정점이 동일한 경로 (단순 경로 + 사이클)
※ 대표적인 사이클 문제
- 오일러 사이클: 모든 edge를 한번씩만 거쳐서 제자리로 돌아오는 사이클 (not a simple cycle)
- 헤밀턴 사이클: 모든 vertex를 한번씩만 거쳐서 제재리로 돌아오는 사이클 (simple cycle)
그래프의 연결 정도
▶ 연결 그래프(connected graph)
- 연결 그래프(connected graph): 무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재한다.
- 비연결 그래프(unconnected graph)
Cf) bridge: 없어지면 G2와 같이 그래프의 연결이 끊겨서 비연결 그래프가 되는 간선
☆ 특정 그래프를 input으로 두고, bridge에 해당하는 간선이 있는지 없는지 판단하는 알고리즘 ☆
그래프 추상 데이터 타입
10.3 그래프의 표현 방법
- 인접행렬(adjacent matrix) 방법
- 인접 리스트(adjacent list) 방법
1) 인접 행렬 (adjacent matrix)
: n x n의 2차원 배열
- 무방향 그래프의 경우 대칭 행렬이기 때문에, 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있다.
- n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 n^2개의 메모리 공간이 필요하다. 이에 따라 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우에는 적합하나, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(sparse graph)의 경우에는 메모리의 낭비가 심하므로 적합하지 않다.
- 인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1) 시간 안에 즉시 알 수 있는 장점이 있다. 즉, 정점 u와 정점 v를 연결하는 정점이 있는지를 알려면 M[u][v]의 값을 조사하면 바로 알 수 있다.
- 또한 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(n)의 연산에 의해 알 수 있다.
- 반면에 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로, n^2번의 조사가 필요하게 되어 O(n^2)의 시간이 요구된다.
인접 행렬을 이용한 그래프 추상 데이터 타입의 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50 // vertex 50개까지로 한정
typedef struct GraphType
{
int n; // 나의 정점의 개수
int adj_max[MAX_VERTICES][MAX_VERTICES];
} GraphType;
// 그래프 초기화
void 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_max[r][c] = 0; // 2차원 배열을 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_max[start][end] = 1; // 무방향 그래프의 경우
g->adj_max[end][start];
}
2) 인접 리스트 (adjacency list)
: 정점에 인접한 정점들을 연결 리스트로 표시한 것
인접 리스트를 이용한 그래프 추상 데이터 타입의 구현
출처: 이화여자대학교 이숙영교수님 자료구조, C언어로 쉽게 풀어쓴 자료구조
'자료구조' 카테고리의 다른 글
| [자료구조] 1110 (0) | 2023.11.11 |
|---|---|
| [자료구조] 1107 (1) | 2023.11.10 |
| [자료구조] 3. 배열, 구조체, 포인터 (0) | 2023.10.26 |
| [자료구조] 2. 순환 (0) | 2023.10.26 |
| [자료구조] 1. 자료구조와 알고리즘 (0) | 2023.10.26 |
