13. 그래프의 표현과 활용(Expression and Use of Graphs)

 

13. 1. 그래프의 표현(Graph Representation)

 

- 인접행렬(Adjacency Matrix): Node의 개수가 n인 Graph를 n X n Matrix로 표현하는 방법.

 

  1) 두 Node에 근접하는 Edge가 있으면 행렬에 해당하는 원소의 값을 1로 표현, 없으면 0으로 표현.

 

  2) Multi Graph이면 Edge의 개수를 적는다.

 

  3) Directed Graph는 Undirected Graph와 달리 방향에 주의해야 한다.

 

 

 

- 인접리스트(Adjacency List): Graph에서 Node를 Head로 지정하고, Node에 연결되어 있는 Edge를 각 Head에 연결시켜 자료구조의 연결리스트 형태로 표현한 것.

 

 

---

 

13. 2. 오일러와 해밀턴(Eulerian & Hamiltonian)

 

- 오일러 경로(Eulerian Path): Graph의 모든 Edge를 꼭 한 번씩만 지나는 경로.

 

- 오일러 순환(Eulerian Cycle): Graph의 Node v에서 출발해서 모든 Edge를 꼭 한 번씩만 지나서 다시 v로 돌아오는 경로.

 

- 오일러 그래프(Eulerian Graph): Eulerian Cycle을 가지는 그래프.

 

- 하나의 Graph가 Eulerian Path를 만족해도, Eulerian Cycle을 만족하지 않을 수 있다.

 

   즉, Eulerian Path와 Eulerian Cycle은 따로 구별되어야 한다.

 

 

- 해밀턴 경로(Hamiltonian Path): Graph의 모든 Node를 꼭 한 번씩만 지나는 경로.

 

- 해밀턴 순환(Hamiltonian Cycle): Graph의 Node v에서 출발해서 모든 Node를 꼭 한 번씩만 지나서 다시 v로 돌아오는 경로.

 

- 해밀턴 그래프(Hamiltonian Graph): Hamiltonian Cycle을 가지는 그래프.

 

- Hamiltonian에서 하나의 Edge를 여러 번 지나도 된다.

 

---

 

13. 3. 그래프의 활용(Use of Graphs)

 

- 최단경로 문제(Shortest Path Proplem): 2개의 꼭짓점이 주어졌을 때 가장 짧은 거리의 경로를 찾는 문제.

 

  1) 가중치가 부여되지 않은 그래프는 경로의 길이(or 경로에 포함된 edge의 수)로 최단경로를 결정.

 

  2) 가중치가 있으면 지나간 Edge의 모든 가중치를 더하고 합산한 가중치가 최소값이 되도록 결정.

 

  3) 최단경로 문제를 해결하는 대표적인 알고리즘으로 시작점으로 최단경로를 갖는 꼭짓점들을 차례로 탐색해가는 다익스트라 알고리즘(Dijkstra Algorithm)이 있다.

 

 

- 그래프 탐색(Graph Search): Graph에 표시된 모든 Node를 탐색하는 방법.

 

- 깊이우선탐색(DFS).

 

  1) 시작점을 탐색한다.

 

  2) 탐색한 꼭짓점의 인접한 꼭짓점들 중 탐색되지 않은 꼭짓점을 탐색한다.

 

  3) 탐색할수 있는 꼭짓점이 있다면 2)를 반복한다.

 

  4) 더 이상 탐색할 수 있는 꼭짓점이 없다면 이전에 탐색한 꼭짓점으로 거슬러 올라가 2), 3)을 반복한다.

 

  5) 그래프의 모든 꼭짓점을 탐색할 때까지 반복한다.

 

- 너비우선탐색(BFS).

 

  1) 시작점을 탐색한다.

 

  2) 탐색한 꼭짓점의 인접한 모든 꼭짓점들을 탐색한다.

 

  3) 탐색된 꼭짓점에서 2)를 반복한다.

 

  4) 그래프의 모든 꼭짓점을 탐색할 때까지 반복한다.

 

---