(191117) 자료구조 - Graph

 

graph.jpg

Graph 자료구조

연결되어 있는 데이터들의 관계를 표현할 수 있는 자료구조

정점(vertex)과 간선(edge)의 집합, root 노드 개념이 없음, 부모-자식 노드 개념이 없음

 

Graph 용어

정점(vertex) : 위치 (node 라고도 부름)

 

간선(edge) : 노드를 연결하는 선을 말함

 

무향 그래프 와 유향 그래프

- 정점과 간선의 연결 관계에 있어서 방향이 없는 것  / 있는 것

 

정점의 차수(degree) : 각 정점에 연결된 간선의 갯수 (무향 기준)

  - Indegree : 유향에서 정점에 들어오는 간선의 갯수

  - Outdegree : 유향에서 정점에서 나가는 간선의 갯수

 

가중치 그래프

- 간선에 가중치 정보를 두어서 구성한 그래프 (네트워크)

 

연결 그래프 와 비연결 그래프

- 무향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우 / 특정 정점쌍 사이에 경로가 없음!!

  -> ex) Tree 자료구조 (사이클이 없는 연결 그래프!!)

 

사이클 과 비순환 그래프

- 경로 중에 반복되는 정점이 없고 시작 정점과 종료 정점이 동일한 경우 / 사이클이 없는 그래프

 

Graph의 구현 방법 2가지

1. 인접 행렬

인접 행렬은 정점의 수를 N이라고 했을 때 N^2 헁렬을 만들어 정점과 정점 사이에 간선의 유무를 표현한 것

 

장점

  - 어떤 두 정점 사이에 간선 존재 여부(boolean)을 바로 알 수 있다. O(1)

  - 정점의 차수(degree)를 O(N)안에 알 수 있다 (행 또는 열을 모두 더하면 되므로)

 

단점

  - 어떤 정점에 인접한 정점을 찾으려면 모든 정점을 전부 순회해야한다.

  - 그래프에 존재하는 모든 간선의 수는 O(N^2) 안에 알 수 있다. 정점의 리스트에 실제 간선 갯수 만큼 들어가 있으므로

 

간선이 많이 존재하는 밀집 그래프(dense graph) 표현할 때 좋다 / 정점 갯수가 작을 때 좋다

 

2. 인접 리스트

모든 정점을 인접 리스트에 저장 (각 정점에 인접한 정점들을 리스트로 표시)

 

장점

  - 어떤 노드에 인접한 노드를 쉽게 찾을 수 있다.

  - 그래프에 존재하는 모든 간선의 수는 O(N+E) 안에 알 수 있다.

 

단점

  - 어떤 두 정점 사이가 연결 되어있는지 확인하는데 오래 걸린다. O(N)

 

간선이 많이 없는 희소 그래프(sparse graph) 표현할 때 좋다 / 정점 갯수가 많을 때 좋다 -> 대부분 인접 리스트 사용하여 구현

 

Graph 탐색 방법 2가지 ( O(V+E) )

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

어떤 한 정점에서 (루트 노드 또는 임의의 노드, 시작 노드)에서 인접한 한 노드를 탐색하고, 다시 그 노드에서 또 인접한 노드를 탐색하는 식으로 계속 탐색하다가 인접한 정점이 없으면 이전 노드로 돌아가서 다시 다른 인접한 노드를 탐색하는 방식

-> 모든 노드를 방문 하고자 하는 경우에 선택

-> stack 을 사용하여 구현!

 

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

어떤 한 정점에서 (루트 노드, 임의노드, 시작 노드)에서 인접한 모든 노드들을 먼저 탐색을 다하고 그 다음 그 인접한 노드들의 또 인접한 모든 노드를 탐색하는 방식

-> 두 노드 사이에 최단 경로를 찾고 싶을때 선택

-> queue를 사용하여 구현!