[자료구조 및 알고리즘] 그래프

그래프 (Graph)

자료구조는 크게 비선형구조, 선형구조로 구분된다.

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다.

그래프는 대표적인 비선형구조이다. 따라서 연결 관계에 초점이 맞춰져 있다.

 

그래프는 노드(Node)와 간선(Edge) 으로 구성되어 있다.

노드는 연결 관계를 가진 데이터. 정점(Vertex)라고도 한다.

간선은 노드를 연결하고 있는 선을 의미한다. 즉 노드간에 관계를 표현한다.

 

그래프 유형

그래프는 간선에 방향이 존재하는 유방향 그래프, 방향이 없는 무방향 그래프 2가지가 있다.

유방향 그래프(Directed Graph) : 방향이 있는 간선

무방향 그래프(Undirected Graph) : 방향이 없는 간선

 

 

그래프 표현방식

그래프를 코드상으로 표현하기 위한 방법은 2가지가 있다.

인접 행렬 : 2차원 행렬 형태로 그래프의 노드 관계를 표현

인접 리스트 : Linked List로 그래프의 연결 관계를 표현

 

 

이 두 방식의 차이는?

인접행렬의 경우는 이차원 배열의 인덱스로 값에 접근하면 두 노드가 연결이 되어있는지 여부를 바로 

알 수 있다.  하지만 이차원 배열의 크기가 n^2 이므로 노드의 수가 많을 수록 배열의 크기가 커지면서 

공간 사용량이 늘어난다.

 

반면 인접리스트의 경우 특정 노드 사이의 연결 여부를 바로 알 수가 없다. 리스트를 순차적으로 탐색을 해야되므로 그만큼 시간이 소요된다. 하지만 연결이 되어있는 정보만 저장을 하기때문에 인접행렬보다 공간 사용량은 훨씬 적다. 

 

그래프를 활용한 알고리즘 문제는 그래프를 탐색하면서 푸는 방식이 대부분이다. 

그리고 그래프를 탐색하는 방식에는 크게 DFS와 BFS 방식이 있다.