�ݺ�ߣ

Graph?
 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조이다.
 수학자 오일러에 의해 처음 창안되었다.
 Vertex(정점), Edge(간선)들의 집합으로 구성된다.
 그래프의 종류
 Directed Graph : 모든 edge가 방향이 있다.
 Undirected Graph : 방향이 있는 edge가 없다.
 가중치 그래프/네트워크 : 간선에 가중치를 할당하게 된 그래프, 연결 유무와 연결강도까지 나
타낼 수 있다.

Undirected Graph
2
1
4
5
3
6
7

가중치 그래프
2
1
4
5
3
6
7
3
5
7
1
2
4

Complete Undirected Graph
Edge가 모든 Vertex를 지날 수 있다.

Edge의 수 : Undirected Graph
 각 edge는 (u, v) 형식이다. u!=v
 vertex가 n개인 그래프에서의 edge의 쌍 개수는 n(n-1)개이다.
 edge (u, v) = edge (v, u)일 경우, complete undirected graph에서 edge 개수는 n(n-
1)/2이다.
 undirected graph에서 edge의 수 <=n(n-1)/2 이다.

Edge의 수 : Directed Graph
 각 edge는 (u , v) 형식이다. u!=v
 vertex가 n인 그래프에서 각 쌍의 개수는 n(n-1) 이다.
 (u, v) != (v, u) 이므로 complete directed graph에서 edge의 개수는 n(n-1)이다.
 Directed graph에서 edge의 수 <= n(n-1) 이다.

Vertex Degree
2
1
4
5
3
6
7
• Vertex에 연결되어있는 edge 개수
• Degree(2) = 2, Degree(6) = 1

In-Degree/Out-Degree of Vertex
2
1
4
5
3
6
7
• In-Degree
• 점에 들어가는 방향의 개수
• Out-Degree
• 점에서 나가는 방향 개수
• Indegree(3)=2, Indegree(2)=0
• Outdegree(1)=1, Outdegree(3)=2

그래프에서 다루는 문제들
 Path Finding
 Connectedness 문제
 Spanning tree 문제

Connected Graph
 Undirected graph 이다.
 각 vertex의 쌍 사이에 path가 존재한다.
2
1
4
5
3
6
7
2
1
4
5
3
6
7
Not Connected Connected

Spanning Tree
 Subgraph가 원 그래프의 모든 vertex를 가지고 있다.
 Subgraph는 트리이다.
 원 그래프가 n개의 vertex를 가졌다면, spanning tree는 n개의 vertex와 n-1개의 edge를 가진
다.
2
1
4
5
3
6
7
3
5
7
1
2
4
3
Spanning tree cost = 18

Adjacency Matrix : Undirected Graph
 n x n 행렬 (n !=0)
 그래프 (i , j)에 edge가 있으면 행렬 A(i , j) = 1이다.
 인접 행렬은 undirected Graph일 경우 대각선을 기준으로 대칭적이다.
2
1
4
5
3
1 2 3 4 5
1 0 1 0 1 0
2 1 0 0 0 1
3 0 0 0 0 1
4 1 0 0 0 1
5 0 1 1 1 0

Adjacency Matrix : Directed Graph
 대각선 요소 부분은 모두 0 이다.
 Directed Graph의 인접행렬은 대각선을 기준으로 대칭일 필요가 없다.
2
1
4
5
3
1 2 3 4 5
1 0 0 0 1 0
2 1 0 0 0 1
3 0 0 0 0 0
4 0 0 0 0 1
5 0 1 1 0 0

Adjacency List
 인접 리스트는 vertex i가 i에 대해 인접한 점들에 대한 선형 리스트를 일컫는다.
 배열 길이 = n
2
1
4
5
3
aList[1] = (2,4)
aList[2] = (1,5)
aList[3] = (5)
aList[4] = (1,5)
aList[5] = (2,3,4)
1
2
3
4
5
2 4
1
5
5
2
5
2
4 3

Graph Search Method
 Tree의 Treversal과 비슷한 개념.
 대표적인 탐색 방법
 Depth-first search
 Breadth-first search

Depth-first Search (DFS)
 깊이 우선탐색
 일반적으로 구현할 때는 Stack을 이용하고, 트리/그래프 같은 자료구조에서 데이터를
탐색할 대 사용하는 알고리즘이다.
 더 이상 나아갈 길이 보이지 않을 만큼 깊이 찾아가면서 탐색한다.
 만약, 나아갈 길이 존재하지 않으면 이전의 위치로 돌아와 찾아가지 않은 다른 길로 뻗
어 나가면서 탐색한다.

Breadth-First Search (BFS)
 너비 우선 탐색
 DFS와 달리 FIFO queue를 이용하고, 트리/그래프 탐색에 사용되는 알고리즘이다.
 탐색 순서는 가까운 정점부터 시작하여 가장 먼 정점까지 방문한다. 방문한 정점의 위
치를 기억하기 위해 큐를 사용.
 데이터를 찾거나 더 이상 방문할 곳이 존재하지 않으면 탐색을 마친다.

�ݺ�ߣ

자료구조 그래프

More Related Content

자료구조 그래프