그래프(Graph)

그래프란?

트리처럼 노드(데이터)들이 연결되어 있는 자료구조로, 노드간의 관계를 표현할 때 주로 쓰인다. 트리와 달리 노드들에 부모/자식 관계가 없이 전부 이어질 수 있다. 그리고 노드와 노드 사이를 잇는 선을 간선이라고 한다.

 

이 간선은 방향을 나타낼 수도 있다. 방향이 있는 그래프를 Directed Graph 라고 하고 방향이 없는 그래프를 Undirected Graph 라고 한다. 방향 그래프는 단방향 혹은 양방향으로도 표현된다. 참고로 트리는 위, 아래로 흐르므로 방향 그래프인데 방향을 생략한 것이다.

 

이어지는 노드들을 따라가다보면 처음 시작한 노드로 돌아오는 그래프도 있다. 이것을 사이클이라고 하는데, 사이클이 하나라도 있는 그래프를 Cyclic Graph, 사이클이 하나도 없는 그래프를 Acyclic Graph 라고 한다.

 참고로 트리는 맨 위 루트라는 출발점이 있고 사이클이 없고 위, 아래로만 흐르는 계층 형태의 방향 그래프다!

 

그래프 표현 방법

Adjacency Matrix

그래프를 2차원 배열에 표현한다. 연결되어 있으면 1 아니라면 0의 값으로 표현한다.

 

Adjacency List

그래프를 Linked List 로 표현한다. 노드와 연결되어 있는 다른 노드를 순서 상관 없이 연결한다. 그런데 a 노드가 b 노드와 연결되어 있는것을 표현할 때, a->b, b->a 총 두번으로 표현해야해서 연결리스트는 간선의 개수 m개보다 2배 더 많은 2m개의 노드를 갖게 된다.

 

Graph 검색 알고리즘

DFS(Depth-First Search)

이진탐색트리에서의 inorder, preorder, postorder 탐색이 바로 깊이 우선 탐색 방법이다. 루트 노드의 child 노드, 그 노드의 child 노드... 점점 아래로 탐색하는 방식이다.

 

BFS(Breadth-First Search)

넓이 우선 탐색은 루트 노드의 같은 레벨 상에 있는 모든 child 노드를 다 방문 하고 그 다음 레벨을 방문하는 방식이다.

 

신장 트리(Spanning Tree)

Spanning Tree는 연결 그래프(중간에 끊겨있지 않은 그래프) 의 부분 그래프들이다. 모든 노드들이 포함되고 사이클이 존재하지 않아야 한다.

 

최소비용 신장트리(MST, Minimum Cost Spanning Tree)

간선들의 가중치를 합한 값이 최소가 되는 신장 트리다. 즉, 최소 비용으로 만들 수 있는 신장 트리. 무방향 그래프일 때 구할 수 있다. 연결 그래프에서 최소비용 신장트리를 찾아내는 알고리즘 중에는 크루스칼 알고리즘(Kruskal Algorithm)이 대표적이다.