[자료구조] 그래프(Graph)

개요

그래프는 정점과 정점을 잇는 간선의 모임이며 데이터의 표현 방식이다.

그래프 자체가 알고리즘이라기 보단, 그래프를 근거로한 여러 알고리즘들이 존재한다.

본문

그래프의 종류

그래프의 집합 표현

V = Vertex

E = Edge

V(G1) = {A, B, C, D}

E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}

V(G3) = {A, B, C, D}

E(G3) = {<A, B>, <A, D>, <D, A>}

그래프의 구현

인접 행렬 기반

인접 행렬 기반 그래프

V*V 크기의 2차원 배열을 사용하여 구현한다.

인접 리스트 기반

인접 리스트 기반 그래프

연결리스트를 기반으로 그래프를 구현한다.

무방향 그래프의 경우 정점 노드를 둘다 연결해야함에 주의

 

그래프 탐색 알고리즘

대표적으로 DFS와 BFS가 있다.

• DFS(Depth First Search, 깊이 우선 탐색)
• BFS(Breadth First Search, 너비 우선 탐색)

참고

윤성우의 열혈 C 자료구조