그래프(graph)

관련 용어

• 정점(vertex) : node를 의미한다.
• 간선(edge) : 노드 간에 연결되어 있는 선을 의미한다.
• 인접 정점(adjacent vertex) : 간선으로 연결된 정점 혹은 노드를 의미한다.
• 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 의미한다.
• 진입 차수(in-degree) :  방향이 자신 쪽으로 향하는 간선의 수를 의미한다.
• 진출 차수(out-degree) : 방향이 다른 정점을 향하는 간선의 수를 의미한다. 
• 경로 길이(path length) : 경로에서 '간선의 개수 = 지나는 정점 - 1' 을 의미한다.
• 단순 경로(simple path) : 중복되는 정점이 없는 경로를 의미한다.
• 사이클(cycle) : 출발점과 도착점이 같은 단순 경로를 의미한다.
  
  

※오일러 경로

• 모든 간선을 한번 지나가면서 출발 정점으로 되돌아오는 경로를 뜻한다.
• 모든 정점의 간선이 짝수개 있어야 한다.

 

정의 및 특징

일반적으로 정점(노드)와 간선으로 구성된 자료구조를 그래프라고 합니다.

• 일반적으로 정점(노드)는 상태 혹은 객체를 표현한 것이고 간선은 관계를 표현한 것입니다.

그래프의 특징에 대해서 알아보겠습니다.

• 트리와는 다르게 루트 노드, 부모 노드, 자식 노드의 개념이 없고 인접 노드(정점)의 개념으로 받아 들여집니다.
• 사이클이 존재하고 self-loop 또한 존재합니다.
• 간선이 존재할 수도 있고 존재하지 않을 수도 있습니다.
• 간선의 방향이 존재하면 방향 그래프, 존재하지 않으면 무방향 그래프라고 합니다.
• '모든 정점의 차수 합 = 간선의 수 x 2' 입니다.

 

그래프의 종류

• 방향 그래프
  • 간선의 방향이 정해진 그래프를 의미합니다.
  • 진입 차수, 진출 차수가 존재하며 다른 방향의 정점을 바로 갈 수 없습니다.
• 무방향 그래프
  • 방향이 정해져있지 않기 떄문에 간선으로 연결 된 모든 정점을 바로 갈 수 있습니다.
• 가중치 그래프
  • 간선에 가중치가 있는 그래프입니다.
  • 가중치가 경로를 결정하는 지의 유무에 따라 경로가 바뀔 수 있습니다.
  • 네트워크라고도 하고 주로 도시와 도시를 연결하는 도로, 통신망의 사용료 등을 추가로 표현 할 때 사용합니다.
• 완전 그래프
  • 모든 정점이 간선으로 연결되어 있는 무방향 그래프입니다.
  • 정점의 개수가 n이라면 간선의 개수는 n x (n - 1) / 2 입니다.

   

완전 그래프

 

구현 방법

• 인접 리스트
  • 각 정점에 인접한 정점들을 연결 리스트로 표현하는 방식입니다.
  • 인접한 노드들을 찾기 편합니다.
  • 정점의 개수가 n 개이고 간선의 개수가 e 개이면 n 개의 헤드 노드가 필요하고 2 x e 개의 노드가 필요합니다.
  • 모든 간선을 탐색하는 데 걸리는 시간 O(n(정점의 개수) + e(간선의 개수)) 입니다.
  • 간선의 개수가 많아지면 순회하는 시간이 증가합니다.

인접 리스트로 표현

 

• 인접 행렬
  • 이차원 배열을 활용합니다.
  • (i, j)의 값이 1이면 i 정점과 j 정점이 간선으로 연결되어 있다는 것입니다.
  • 무방향 그래프일 경우 대칭 행렬의 형태를 띕니다.
  • 정점의 개수가 n개이면 n^2의 공간이 필요합니다.
  • 간선이 적으면 공간적으로 비효율적이다.
  • 모든 간선을 탐색하는 데 걸리는 시간은 O(n^2) 입니다.
• 선택 기준
  • 간선이 많은 그래프(밀집 그래프)의 경우 인접 리스트로 구현했을 때, 정점의 차수 만큼 순회 시간이 길어지기 때문에 인접 행렬로 구현하는 것이 적합합니다.
  • 간선이 적은 그래프(희소 그래프)의 경우 인접 행렬로 구현했을 때 공간적으로 비효율적이기 때문에 인접 리스트로 구현하는 것이 적합합니다.

 

탐색

그래프를 탐색하는 데에 대표적으로 BFS(너비우선탐색)과 DFS(깊이우선탐색)이 있습니다.

간략하게 소개하자면 BFS의 경우 모든 인접 노드들을 다음 탐색 대상으로 설정하여 넓게 탐색하는 방식입니다.

DFS의 경우, 인접 노드들을 차례로 하나씩 갈 수 있을 때 까지, 깊게 탐색하는 방식입니다.

이 두 가지 탐색법에 대해서는 이후에 자세하게 다룰 예정입니다.

 

의견이 있으시거나 수정해야할 부분이 있으면 편하게 공유 부탁드립니다!