그래프 (Graph)

 

 ** 그래프

 - 정점들간의 관계를 표현하는 자료구조 ( G=(V,E) )

 - V는 Vertex(정점) 과 E는 Edge(간선) 을 의미하며 간선은 정점들 간의 연결관계를 표시합니다.

 - 간선 edge는 두 개의 정점이 있어야 정의가 됩니다 (cycle을 가지지 않을 경우)

 - directred graph(유향그래프) 와 undirected graph(무향 그래프) 가 있으며

 - 유향그래프에서는 vw와 wv는 다른 방향을 가지므로 다른 간선이다.

 - 가중치 그래프(weighted graph) 의 경우 (V,E,W)로 구성

 

 

 ** 그래프의 용어

 - 정점(Vertex) : 연결된 객체 (node)

 - 간선(Edge) : 정점들 간의 연결관계를 나타내는 선

 - incident : 정점과 간선의 관계에서 쓰는 용어 (정점에  간선이 연결된 경우)

 - adjacent : 정점과 정점간의 관계에서 쓰는 용어 (정점과 정점이 간선에의해 직접적으로 연결되어있는 경우)

 - 사이클(cycle) : 경로의 시작 정점과 끝 정점이 같을 경우

 - 차수(degree) : 정점에 연결되어 있는 간선의 수를 그 정점의 차수 라고 한다.

 

 

 ** 그래프의 구현

 - 보통 인접리스트로 구현을 하여, 인접 행렬으로도 구현 가능하다.

 - 인접행렬로 구현을 할 경우 두 정점이 직접 연결되어있는지 (adjacent) 를 O(1) 에 바로 알아낼 수 있다.

 - 그러나 어떤 특정 정점에 인접한 모든 정점들을 탐색하거나, 그래프의 간선의 수 등을 알아내려면

    O(n*n)이 걸린다 matrix를 모두 조사해야하므로....

 - 인접리스트로 구현할 경우 어떤 정점에 인접한 노드들은 바로 찾을 수 있다는 장점이 있다.

 

 

 ** 그래프의 탐색

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

     - 정점을 탐색을 하는데 다음 연결된 정점을 탐색하기 전에 첫 정점과 연결된 정점을 우선 탐색

     - 모든 노드를 다 탐색하고자 할 경우 자주 사용한다.

     - 특정 정점에서 시작하여 원하는 다른 정점까지 경로가 있는지를 탐색할 때 사용하기도 한다.

 

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

     - 탐색 시작 정점으로 부터 연결된 모든 정점을 먼저 탐색을 한 후 그 탐색한 정점과 연결된 다른 정점들을 탐색

     - 보통 최단경로를 찾는 문제에 BFS를 많이 사용한다.

     - 큐를 이용하여 구현을 많이 하는데 탐색정점과 연결된 정점들을 큐에 넣어서 탐색을 해가면서

     - 탐색한 정점은 큐에서 POP하고 그 정점에 연결된 새로운정점들을 큐에 PUSH해 준다.

     - 탐색을 시작할 때의 큐의 SIZE만큼 탐색을 하면 탐색 후에는 직접적으로 연결된 정점들은 모두 POP되었을 것이고

       탐색을 했던 정점들과 연결된 새로운 정점들이 큐에 들어와 있다.