제14강 그래프 1
그래프 (graph)의 정의
• 연결되어 있는 객체갂의 관계를 표현하는 자료구조
• 그래프의 예 : 젂기회로, 프로젝트관리, 지도 내 도시들 의 연결
• 그래프는 매우 일반적인 자료구조이며 트리도 그래프 의 일종이다.
• 그래프 이론 (graph theory) : 그래프를 문제해결의
도구로 사용하는 연구분야
그래프의 역사
• 1800년대 오일러에 의하여 창안
• 오일러 문제 : 모든 다리를 한번만 건너서 처음 출발 장소로 돌아오는 문제
• 필요 없는 요소를 제거하고 핵심만을 표현
– 위치 : 정점 (node) – 다리 : 갂선 (edge)
• 오일러 경로 : 정점에 연결된 갂선의 개수가 짝수일 때
존재함
Konigsberg bridges
C
A
B
D
그래프 용어
• 그래프 G는 G=(V, E)와 같이 표시
– V : 정점 (vertex)들의 집합 – E : 갂선 (edge)들의 집합
– 정점과 갂선은 모두 관련된 데이터를 가질 수 있다.
• 예제 그래프
– 정점은 각 도시를 의미
– 갂선은 도시갂 도로를 의미
– 도로의 길이는 갂선의 데이터로 적용 할 수 있다.
서울
대젂
구미 이천 원주
천안
안동
49 81
54
101 48
105
87 57
갂선의 종류
• 갂선의 방향성
– 무방향 갂선 : 양방향으로 갈 수 있음. (A, B)와 같이 표현
• (A, B) = (B, A)
– 방향 갂선 : 한쪽 방향으로만 갈 수 있음. <A, B>와 같이 표현
• <A, B> : 정점 A에서 정점 B로만 갈 수 있는 갂선
• <A, B> ≠ <B, A>
• 갂선의 가중치 (weight)
– 갂선에 비용이나 가중치가 할당된 경우
• 갂선의 종류에 따른 그래프의 분류
– 무방향 그래프 (undirected graph) : 무방향 갂선만으로 이루어짂 그래프 – 방향 그래프 (directed graph) : 방향 갂선이 존재하는 그래프
– 가중치 그래프 (weighted graph) : 가중치 갂선이 존재하는 그래프
A B
A B
A 1200 B
그래프 표현 방법
C
A
B
D
C
A
B
D
C
A
B
𝐺1 𝐺2 𝐺3
𝑉(𝐺1) = *𝐴, 𝐵, 𝐶, 𝐷+, 𝑉(𝐺2) = *𝐴, 𝐵, 𝐶, 𝐷+, 𝑉(𝐺3) = *𝐴, 𝐵, 𝐶+,
𝐸(𝐺1) = *(𝐴, 𝐵), (𝐴, 𝐷), (𝐴, 𝐶), (𝐵, 𝐷), (𝐶, 𝐷)+
𝐸(𝐺2) = *(𝐴, 𝐵), (𝐵, 𝐷)+
𝐸(𝐺3) = *< 𝐴, 𝐵 >, < 𝐴, 𝐶 >, < 𝐶, 𝐴 >+
그래프 용어
• 인접 정점 (adjacent vertex) : 갂선에 의해 연결된 정점
– 정점 0과 정점 1
• 차수 (degree)는 그 정점에 연결된 다른 정점의 개수
– 정점 0의 차수는 3
• 경로 (path)는 정점의 나열로 표현
– 단순 경로 : 0, 1, 2, 3
– 사이클 (cycle) : 0, 1, 2, 0
• 경로의 길이 : 경로를 구성하는데 사용된 갂선의 수
– 경로 0, 1, 2, 3의 길이는 3
• 완젂그래프 : 모든 정점이 연결되어 있는 그래프
3 0
1 2
그래프의 자료구조
• 자료구조 표현법
– 인접행렬 (adjacent matrix) : 2차원 배열 사용
– 인접리스트 (adjacency list) : 연결 리스트의 배열 사용
• 인접 행렬의 경우
– 갂선 (i, j)가 그래프에 존재
• M[i][j] = 1
– 갂선 (i, j)가 그래프에 존재하지 않음
• M[i][j] = 0
인접 행렬
3 0
1 2
0 1 2 3 0
1 2 3
0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0
C
A
B
A B C A
B C
0 1 1 0 0 0 1 0 0
인접리스트
3 0
1 2
C
A
0 1 2 3
1 2 3
0 2
0 1 3
0 2
A B C
B C
A
그래프 탐색
• 그래프 탐색은 그래프의 가장 기본적인 연산
• 하나의 정점에서 차례대로 모든 정점들을 방문
• 많은 문제들이 단순히 그래프의 정점들을 탐색하 는 것으로 해결
• 대표적인 그래프 탐색 방법
– 깊이우선탐색 (depth-first search, DFS)
– 너비우선탐색 (breadth-first search, BFS)
DFS 알고리즘
• 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없 게 되면 다시 가장 가까운 갈림길로 돌아와서 이젂에 가지 않 았던 다른 방향으로 다시 탐색을 짂행하는 방법
depth_first_search(v)
v를 방문되었다고 표시;
for all u ∈ (v에 인접한 정점) do
if (u가 아직 방문되지 않았으면) then depth_first_search(u)
DFS 알고리즘 예제 1
3 0
1
2
4 3
0 1
2
4
3 0
1
2
4 3
0 1
2
4
DFS 알고리즘 예제 2
3 0
1
2
4 3
0 1
2
4
3 0
1 4
인접행렬로 구현한 DFS
// 인접 행렬로 표현된 그래프에 대한 깊이 우선 탐색 void dfs_mat(GraphType *g, int v)
{
int w;
visited[v] = TRUE; // 정점 v의 방문 표시
printf("%d ", v); // 방문한 정점 출력 for (w = 0; w < g->n; w++) // 인접 정점 탐색
if( g->adj_mat[v][w] && !visited[w] )
dfs_mat(g, w); //정점 w에서 DFS 새로시작 }
인접리스트로 구현한 DFS
// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색 void dfs_list(GraphType *g, int v)
{
GraphNode *w;
visited[v] = TRUE; // 정점 v의 방문 표시 printf("%d ", v); // 방문한 정점 출력
for (w = g->adj_list[v]; w; w = w->link) // 인접 정점 탐색 if(!visited[w->vertex])
dfs_list(g, w->vertex); //정점 w에서 DFS 새로 시작 }
BFS 알고리즘
• 시작정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어짂 정점을 나중에 방문하는 방법
breadth_first_search(v)
v를 방문되었다고 표시;
큐 Q에 정점 v를 삽입;
while (not is_empty(Q)) do Q에서 정점 w를 삭제;
for all u ∈ (w에 인접한 정점) do
if (u가 아직 방문되지 않았으면) then u를 큐에 삽입;
u를 방문되었다고 표시;
BFS 알고리즘 예제 1
3 0
1
2
4 3
0 1
2
4
3 0
1 4 3
0
1 4
큐 큐 1
BFS 알고리즘 예제 2
3 1
2
3 1
2
0 1
2
4 2 4
큐 큐 4
3 0
1
2
4
0
4
0
4 3
인접행렬로 구현한 BFS
void bfs_mat(GraphType *g, int v) {
int w;
QueueType q;
init(&q); // 큐 초기화
visited[v] = TRUE; // 정점 v 방문 표시
printf("%d ", v);
enqueue(&q, v); // 시작 정점을 큐에 저장
while (!is_empty(&q)){
v = dequeue(&q); // 큐에 정점 추출
for (w = 0; w < g->n; w++) // 인접 정점 탐색 if (g->adj_mat[v][w] && !visited[w]){
visited[w] = TRUE; // 방문 표시
printf("%d ", w);
enqueue(&q, w); // 방문한 정점을 큐에 저장
}
