[자료구조] 그래프(Graph)

-그래프

: 트리와 같은 비선형 자료구조 이며 각각의 노드 (객체) 를 연결한 자료구조

 연결한 객체를 정점 이라고 부르고 연결 선은 간선 이라고 부른다. 

그래프의 예시

번호가 새겨진 원을 보통 노드 라고 하고 그 노드를 연결하는 파란 선을 간선 이라고 표시합니다. 

- 그래프와 관련된 용어

정점 : 각각의 노드

간선 : 노드를 연결하는 선

크기 : 정점의 개수

인접 : 두개의 정점을 연결하는 간선이 있을 때, 두 정점은 인접하다

경로 : 정점 V1에서 Vn의 시퀀스

경로의 길이 : 간선의 개수 n

사이클 : 임의의 노드에서 자기 자신으로 돌아오는 경로

단순 사이클 : 처음과 마자막 정점이 같은 사이클

비순환 그래프 : 사이클이 없는 (ex 트리) 그래프

- 그래프의 구현 방법

그래프를 구현하는데는 크게 두가지 방법이 있습니다. 

1. 행렬을 이용한 그래프

	1	2	3	4	5
1	false	false	true	false	true
2	false	false	true	true	false
3	true	true	false	false	true
4	false	true	false	false	false
5	true	false	true	false	false

행렬로 표현한 그래프

2. 연결리스트를 이용한 그래프

연결리스트를 이용한 그래프

- 그래프의 탐색

1. 너비 우선 탐색 (BFS)

시작 정점의 인접한 정점을 모두 탐색하고 이후에 탐색했던 정점들의 인접한 정점으로 탐색을 이어나간다

시작 정점이 1 이라고 한다면 1과 인접한 정점 2, 5을 먼저 방문

이후 첫 번째 인접한 정점인 2와 인접한 정점 3을 방문, 

정점의 인접한 정점을 모두 방문했다면 다른 인접했던 정점 5로 돌아가서 5와 인접한 정점 6을 방문 

다시 3정점으로 돌아와서 인접한 정점 4, 8을 방문 

6으로 돌아와서 인접한 정점 7 방문 

탐색 순서 : 1->2->5->3->6->4->8->7

Queue를 이용하여 구현 가능하다

2. 깊이 우선 탐색 (DFS)

시작 정점에서 인접한 정점을 탐색하고, 인접한 정점의 또 다른 인접한 정점을 탐색하면서

더이성 인접한 정점이 없을 때 돌아가서 방문했던 노드들의 다른 인접한 정점을 방문

시작정점이 1이라고 한다면 1과 인접한 2 방문

2와 인접한 3 방문, 3과 인접한 4 방문, 4와 인접한 8 방문 후에

3으로 돌아가서 남아있는 인접정점이 없는지확인하고 2, 1로 돌아가서 1의 다른 인접한 정점 5 방문

5의 인접한 정점 6방문, 6과 인접한 7 방문

탐색 순서 : 1->2->3->4->8->5->6->7

Stack을 이용하여 구현 가능하다

- 가중치 그래프

: 간선에 가중치가 있는 그래프 

가중치 그래프에서 최단 경로를 알아내는 알고리즘들이 많다. (ex Dijkstra)

- 다이 그래프

: 방향 그래프 라고도 하며 간선이 하나의 '방향'을 가지고 있다