자료구조 - Chapter 14

그래프 이해와 종류

그래프(Graph)

그래프는 정점과 간선의 집합이다.

정점(vertext)은 연결의 대상이되는 개체 또는 위치를 의미한다.

간선(edge)은 정점 사이의 연결을 의미한다.

 

무방향 그래프(undirected graph)

연결 관계에 있어서 방향성이 없는 그래프

무방향 그래프

방향 그래프(directed graph)

간선에 방향 정보가 포함된 그래프 = 다이 그래프(digraph)

방향 그래프

이러한 무방향 그래프와 방향 그래프는 간선의 연결 형태에 따라서 완전그래프(complete graph)로 구분된다.

완전 그래프란 각각의 정점에서 다른 모든 정점을 연결한 그래프를 뜻한다. 때문에 정점의 수가 동일한

완전 그래프라 하더라도, 방향 그래프의 간선의 수는 무방향 그래프의 간선의 수에 두배가 된다.

 

가중치 그래프(weight graph)

가중치 그래프는 간선에 가중치 정보를 두어 구성한 그래프를 의미한다.

가중치는 두 정점사이의 거리라던가 두 정점을 이동하는데 걸리는 시간과 같은 정보가 될 수 있다.

 

부분 그래프

원 그래프를 구성하는 정점과 간선의 일부로 이뤄진 그래프

 

그래프 집합 표현

• 그래프 G의 정점 집합 - V(G)로 표시함
• 그래프 G의 간선 집합 - E(G)로 표시함

무방향 그래프

• V(G) = {A, B, C, D}
• E(G) = { (A, B), (A, C), (A, D), (B, C), (C, D)}

방향 그래프

• V(G) = {A, B, C, D}
• E(G) = { <A, B>, <A, C>, <D, A> }

그래프를 구현하는 2가지 방법

1. 인접 행렬(adjacent matrix) 기반 그래프 - 정방 행렬을 활용
2. 인접 리스트(adjacent list) 기반 그래프 - 연결 리스트를 활용

인접 리스트 기반 그래프 구현

예제 : 인접 리스트 기반 무방향 그래프 구현하기

연결 리스트를 사용하여 인접 리스트를 구현한다.

 

인접 리스트 기반 무방향 그래프

ALGraph.c

0.00MB

ALGraph.h

0.00MB

DLinkedList.c

0.00MB

DLinkedList.h

0.00MB

ex14-1 Graph.c

0.00MB

그래프의 탐색

그래프는 정점의 구성뿐만 아니라, 간선의 연결에도 규칙이 존재하지 않는다. 따라서 2가지 알고리즘 방법으로

그래프를 탐색한다.

• 깊이 우선 탐색 : Depth First Search : DFS
• 너비 우선 탐색 : Breadth First Search : BFS

깊이 우선 탐색 (Depth First Search : DFS)

DFS의 탐색 방법은 한길을 깊이 파고드는 것.

한노드를 시작으로 연결되어 있는 노드가 없다면 다에게 연결해온 상위 노드에게 이를 알린다.

마지막으로 처음 시작한 노드에서 끝이난다.

 

너비 우선 탐색 (Breadth First Search : BFS)

BFS 방법은 한 노드에서 연결되어있는 모든 노드로 가지를 그려간다고 생각하면 된다.

 

예제 : 깊이 우선 탐색 DFS 구현하기

• 스택 : 경로 정보의 추적을 목적으로 한다.
• 배열 : 방문 정보의 기록을 목적으로 한다.

첫 시작 노드에서 연결되면 노드에 추가하고, 더이상 연결할 노드가 없으면 POP과정을 통해서 

상위의 노드를 찾아간다. 다시 연결할 노드가 발생하면 연결하고 PUSH한다.

 

깊이 우선 탐색

ALGraphDFS.c

0.00MB

ALGraphDFS.h

0.00MB

ArrayBaseStack.c

0.00MB

ArrayBaseStack.h

0.00MB

DLinkedList.c

0.00MB

DLinkedList.h

0.00MB

ex14-2 DFS_Search.c

0.00MB

예제 : 넓이 우선 탐색 BFS 구현하기

• 큐 : 방문 차례의 기록을 목적으로 한다.
• 배열 : 방문 정보의 기록을 목적으로 한다.

시작 노드의 연결된 노드를 큐에 집어 넣고 빼내는 과정에서 빼내는 노드에 연결된 노드를 다시 큐에 넣는다.

이렇게 과정을 큐가 공백이 될 때 까지 반복한다.

 

넓이 우선 탐색

ALGraphBFS.c

0.00MB

ALGraphBFS.h

0.00MB

CircularQueue.c

0.00MB

CircularQueue.h

0.00MB

DLinkedList.c

0.00MB

DLinkedList.h

0.00MB

ex14-3 BFS_Search.c

0.00MB

최소 비용 신장 트리

경로(Path)

두 개의 정점을 잇는 간선을 순서대로 나열한 것.

단순 경로(Simple Path)

동일한 간선을 중복하여 포함하지 않는 경로

 

사이클(cycle)

단순 경로이면서 시작과 끝이 같은 경로

 

신장 트리(Spanning Tree)

사이클을 형성하지 않는 그래프

신장 트리의 모든 간선의 합이 최소인 그래프를 가리켜 '최소 비용 신장트리' = '최소 신장 트리' 라 한다.

 

신장트리 두가지 특징

• 그래프의 모든 정점이 간선에 의해서 하나로 연결되어 있다.
• 그래프 내에서 사이클을 형성하지 않는다.

최소 비용 신장 트리 구성 알고리즘

• 크루스칼(Kruskal) 알고리즘 : mst가 될 때까지 간선을 하나씩 또는 선택해서 삭제하는 방식
• 프림(Prim) 알고리즘 : 하나의 정점을 시작으로 mst가 될 때 까지 트리를 확장해 가는 방식

크루스칼(Kruskal) 알고리즘 핵심

• 가중치를 기준으로 간선을 오름차순 정렬한다.
• 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가한다.
• 사이클을 형성하는 간선은 추가하지 않는다
• 간선의 수가 정점의 수보다 하나 적을 때, MST는 완성된다.

예제 : 크루스칼(Kruskal) 알고리즘 구현하기

크루스칼 알고리즘 구현하기

ALEdge.h

0.00MB

ALGraphKruskal.h

0.00MB

ArrayBaseStack.h

0.00MB

DLinkedList.h

0.00MB

PriorityQueue.h

0.00MB

UsefulHeap.h

0.00MB

ALGraphKruskal.c

0.01MB

ArrayBaseStack.c

0.00MB

DLinkedList.c

0.00MB

ex14-4 Kruskal.c

0.00MB

PriorityQueue.c

0.00MB

UsefulHeap.c

0.00MB