그래프(Graph)

그래프: 하나 이상의 정점(혹은 노드)을 포함하는 집합 정점(v)와 두 정점의 쌍으로 구성되는 간선을 포함하는 집합 E를 가진다. 정점간의 관계를 표현하는 자료구조이다.

- 쾨니히스베르크 다리 문제 -

등장 배경

- 수학자 오일러가 쾨니히스베르크 다리 문제를 해결하기 위해 그래프를 고안

* 쾨니히스베르크 다리 문제: 모든 다리를 단 한 번씩 지나 다시 출발점으로 되돌아 올 수 있는가?

 

- 육지를 점으로 다리를 선으로 표현하여 문제를 추상화함

- 육지의 건물이나 다리 같은 불필요한 요소는 다 버리고 육지와 다리의 '관계'만을 점과 선으로 나타낸 것이 그래프의 시초 

그래프 표기법

G = (V, E)

 1. G: 그래프(Graph)

 2. V: 노드 또는 정점(Vertex)

 3. E: 간선(Edge)

그래프의 용어 

 1. 정점: 간선이 연결되는 점

 2. 간선: 두 정점을 연결하는 선

 3. 무방향 그래프: {}으로 표시, 방향을 가지지 않는 그래프, 실선을 사용함

 4. 방향 그래프: ()으로 표시, 방향을 가지는 그래프, 화살표를 사용함

 5. 다중 그래프: 두 정점 사이에 한 개 이상의 간선을 허용 

 6. 가중 그래프: 간선이 가중치(비용)를 갖는 그래프 

 7. 독립 정점: 어떤 정점과도 인접하지 않는 정점

 8. 진입 차수: 정점으로 향하는 간선의 개수 

 9. 진출 차수: 정점에서 시작하는 간선의 개수 

 10. 루프(Loop): 간선의 시작점과 끝점이 같은 정점

 11. 트리: 사이클이 없는 그래프 (즉, 트리도 그래프의 일종이다.)

그래프 탐색 종류 

- DFS vs BFS -

 1. 깊이 우선 탐색(DFS)

  가. 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

  나. 탐색할 때 계속 깊이 들어가다가 더 이상 갈 수 없게 되었을 때 다시 가장 가까운 갈림길도 돌아와서 다른 방향으로 탐색을 진행

  다. 모든 노드를 방문하고자 할 때 DFS를 선택 

  라. 검색 속도는 넓이 우선 탐색(BFS)보다 느림

  마. 넓이 우선 탐색(BFS)보다 조금 더 간단함

  바. 재귀적 특성을 지님. 

 

 2. 넓이 우선 탐색(BFS)

  가. 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법 

  나. 두 노드사이에서 최단 경로 혹은 임의의 경로를 찾고 싶을 때 적합한 방법

  다. 자료구조 큐(Queue)를 사용함 -> 방문한 노드들을 차례로 저장한 후 꺼낼 수 있게 하기 위하여 

  라. 시작 정점으로부터 가까운 정점에 먼저 방문 -> 멀리 떨어져 있는 정점은 나중에 방문 

  마. 검색 속도는 깊이 우선 탐색(DFS)보다 빠름

  바. 비 재귀적 특성을 지님

 

< 참고자료 >

 

[도서] 자료구조  - 정광식 지음-

 

<Data structures> chapter 6,  그래프(Graph) end

---