[자료구조] 그래프

그래프란?

정점(노드)와 간선(정점을 이어주는 선)들의 집합을 그래프라고 한다.

객체 간의 연결을 시각적으로 나타낸 것

트리도 그래프 중 하나다.

용어

정점(vertex) - 그래프를 형성하는 노드, V로 표현

간선(edge) - 노드를 연결하는 선, E로 표현

정첨 차수(degree of vertext) - 해당 노드에 연결된 간선의 개수

가중치(weight) - 간선에 대한 값, 문맥에 따라 다양한 것을 나타낼 수 있다. ex) 노드와 노드 사이의 거리를 표현

무지향성 그래프 ( undirected graph )

간선 간에 방향이 없는 그래프

간선은 두 노드 간의 상호 연결을 암시한다. 

반대는 Directed Graph = Digraph

그래프를 구현하는 두가지 방법

인접 행렬 ( adjacent matrix )

행렬의 각 항목이 두 정점 간의 연결을 나타내는 V x V 행렬

인접 리스트 ( adjacency list )

정점을 노드의 키로 사용해, 해당 노드의 이웃들을 리스트에 저장한다.

 

그래프 탐색 방법

너비 우선 탐색 ( BFS, breadth-first  search )

연결된 노드와 해당 노드들 간의 간선을 순서대로 검색하는 알고리즘

큐를 사용해서 탐색을 한다. 큐에 현재 정점과 간선으로 연결된 정점들을 넣고 해당 큐에서 꺼낸 정점과 연결된 정점들을 다시 큐에 넣는다. 위 과정을 반복하면서 탐색을 진행한다.

 

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

다른 연결을 방문하기 전에 하나의 연결을 깊게 파고들어서 순회하는 검색 알고리즘

연결 할 수있는 정점까지 계속 연결을 한 후, 더이상 연결되지 않은 정점이 없으면 그 이전 단계 정점으로 돌아가 살펴본다.

스택을 사용한다.