[자료구조론] 그래프

Graph

  그래프는 비선형 자료구조로, 정점과 간선의 집합으로 구성된다. 

    G = (V,E) // vertex(정점) - 여러가지 특성을 가질 수 있는 객체를 뜻하고, 노드(node)라고도 한다. 

                       edge(간선) - 정점들 간의 관계를 의미하고, link라고도 한다. 

 

방향성 유무에 따라 방향그래프 여부, 가중치 유무에 따라 가중치 그래프, 순환경로 유무에 따라 순환그래프로 나뉜다.

 1) 무향 그래프 

     : 선은 양방향을 의미한다. (A,B) 이든 (B,A)이든 순서에 의미가 없다.

 2)방향 그래프 

     : 선은 일방향을 의미한다. (순서에 의미가 있다) 

     *가중치 그래프: 각 선에 가중치를 부여한 형태의 그래프로,  간선에 비용을 부과하는 형식으로 가중치가 부과될 수 있다.

 

   차수(degree)란 무방향 그래프에서 정점에 연결된 간선의 개수를 의미한다. 방향 그래프에서는 나가는 간선의 개수를 외차수(Out degree), 들어오는 간선의 개수를 내차수(Indegree)라고 부른다. 

   

그래프는 이차원배열을 이용한 "인접 행렬"과 연결리스트를 이용한 "인접 리스트" 구조로 구현이 가능하다. 

    인접 행렬: 정방 행렬을 사용하여 구현하고, 연결 관계를 O(1)로 파악이 가능하다. 공간 복잡도는 O(2V)이다. 

    인접 리스트: 그래프를 나타내는 가장 흔한 방식이고, 모든 정점(혹은 노드)은 근접 정점의 리스트를 저장한다. 리스트를 사용하여 구현하고, 정점간 연결 여부 파악에 오래 걸린다. 공간 복잡도는 O(E+V)

 

 

 그래프의 탐색 방법

   1) 깊이 우선 탐색(DFS) : Stack을 통해 구현한다. root 혹은 선택된 노드에서 시작되어 각각의 가지를 완전히 탐험한 후 다음 가지로 이동한다. 즉, 옆 칸으로 이동하기 전에 해당 칸을 전부 훑는 것이다. 

   2) 너비 우선 탐색(BFS) : Queue를 통해 구현한다. BFS로 찾은 경로는 최단경로임이 수학적으로 보장된다. 한 가지의 요소를 다 훑기 전에 옆의 이웃을 먼저 탐색한다.