[자료구조] 그래프

그래프

 

트리와 같이 노드와 간선으로 연결된 형태를 그래프라고 한다.

싸이클이 형성될 수 있기 때문에 계층적 자료구조라기 보다는 전체를 나타내는 형태로 생각할 수 있다.

따라서 부모-자식 관계나 루트노드 같은 성질이 없다.

 

그래프

위 그림에서 A-B-E-C-A의 사이클이 있다.

 

그래프에는 여러가지 특징이 있다.

먼저, 방향이 있는 그래프와 방향이 없는 그래프로 나눌 수 있다. 

위에서 그린 그래프는 방향이 없는 그래프이고, 방향이 있는 그래프는 다음과 같다.

방향이 있는 그래프

방향이 있을 때는 해당 방향으로만 진행할 수 있다는 특징이 있다.

 

다음으로는 모든 노드가 연결되어있지 않아도 된다는 것이다.

비연결 그래프

이를 비연결그래프, disjoint 그래프라 한다.

 

반면 모든 노드가 서로 연결되어있는 그래프는 완전그래프라 한다.

완전 그래프

간선에 가중치를 둘 수 있다.

쉽게 예를 들면 거리라고 생각할 수 있다. 

A에서 C로 가는 방법은 A-C로 바로 가는 것과, A-B-E-C를 가는 방법이 있다.

가중치를 거리라고 생각할 때, A-B-E-C로 가는 방법이 거리가 1 더 가까움을 알 수 있다. 

 

그래프의 구현

그래프는 두가지 방법으로 구형할 수 있다.

먼저 인접행렬 방식이다.

인접 행렬 방식

각 노드에서 연결된 노드를 1로 하고, 연결되지 않은 노드는 0의 값을 갖는 행렬을 만든다.

만약 가중치가 있는 그래프일 경우 1대신 가중치를 넣을 수 있다.

 

인접행렬의 장점

• 두 노드를 연결하는 간선의 존재 여부를 $O(1)$만에 찾을 수 있다.

단점

• 그래프에 존재하는 모든 간선의 수는 $O(N^2)$만에 찾을 수 있다.
• 차지하는 메모리 공간이 크다.

그래프에 간선이 많을 경우 주로 사용

 

두번째로는 인접리스트 방식이다.

인접 리스트 방식

인접 리스트 방식은 각 노드에서 갈 수 있는 노드를 리스트형태로 저장한다.

이번에는 가중치까지 함께 저장한 모습이다.

 

인접리스트의 장점

• 모든 간선을 찾을 때 $O(N)$

단점

• 특정 두 노드가 연결되었는지 확인하려면 시간이 오래 걸린다.

그래프에 간선이 적을 경우 주로 사용

 

그래프의 탐색

그래프의 노드를 모두 찾기 위한 탐색방법에는 크게 두 가지가 있다.

• 깊이 우선 탐색 (DFS)

시작 노드로부터 연결된 노드들을 스택에 넣어 하나씩 탐색하는 방법

이렇게 탐색할 경우 그래프의 깊이를 먼저 탐색하게 된다.

주로 모든 노드를 방문할 필요가 있을 때 이 방법을 선택한다.

 

• 너비 우선 탐색 (BFS)

시작 노드로부터 연결된 노드들을 큐에 넣어서 하나씩 탐색하는 방법

이렇게 탐색할 경우 각 노드에 연결된 모든 노드를 먼저 탐색하게 되므로 너비 우선 탐색이라 한다.

주로 두 노드 사이의 최단 경로를 찾을 때 이 방법을 사용한다.