그래프 알고리즘

그래프의 정의

: 그래프는 정점(노드)와 간선(엣지)로 이루어진 자료구조를 의미한다. 또한 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프로 나뉜다.

그래프의 표현

그래프를 표현하는 방식에는 크게 연결선 리스트, 인접 행렬 , 인접 리스트 세가지로 나눌 수 있다.  

 

연결선 리스트

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5], [3,8], [4,5], [4,9], [7,8], [7,9] ]

인접 행렬

[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

인접 리스트

[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]

 

그래프의 탐색

그래프의 탐색 기법은 크게 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS), 다익스트라(Dijkstra), 플로이드 와샬(Floyd Washall)이 있다.

	너비우선탐색	깊이 우선 탐색	다익스트라	플로이드 와샬
탐색 방식	자신과 연결된 주변 정점부터 탐색해 나감	자신과 연결된 정점을 선택해, 그 정점에서 연결된 모든 정점을 파고들어가며 끝날 때 까지 들어가 탐색	간선에 음의 가중치가 없는 그래프에서, 어느 한 정점에서 각 정점까지 최소 가중치를 갖는 루트 탐색	간선에 양, 음의 가중치가 있는 그래프에서, 모든 정점에 대해 각 정점까지 최소 가중치를 갖는 루트 탐색
특징	깊이가 깊은 그래프에 대해 높은 성능	넓이가 넓은 그래프에 대해 높은 성능	비교적 빠르게 최단경로 탐색 가능	모든 정점에서의 최단 경로와, 양, 음수 값의 모든 가중치에 대해 탐색 가능. 코드가 단순하다.
제약 조건	너비가 넓은 그래프에 대해 낮은 성능	깊이가 깊은 그래프에 대해 낮은 성능	한 정점에 대해서만 가능하며, 음수 가중치는 불가	속도가 느림
이용되는 자료구조	큐	스택	BFS 응용(+최소 힙)	3중 for문
시간 복잡도	인접행렬: O(V^2) 인접리스트: O(V+E) (V: 정점의 개수, E: 간선의 개수)		일반: O(V^2) 최소 힙 사용: O(E+VlogV)	O(V^3)

 

 

출처

m.blog.naver.com/occidere/220923695595

ko.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs