선형 구조 - Graph (그래프)

개념

정의

• 단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아놓은 자료구조
  즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조 이다.

그래프와 트리의 차이

용어

• 정점(vertex) : 위치라는 개념. (node 라고도 부름)
• 간선(edge) : 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
• 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
• 정점의 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진입 차수(in-degree) : 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
• 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
• 경로 길이(path length) : 경로를 구선하는 데 사용된 간선의 수
• 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우
• 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

종류

무방향 그래프 vs 방향 그래프

• 무방향 그래프 (Undirected Graph)
  - 두 정점을 연결하는 간선에 방향이 없는 그래프
  

• 방향 그래프 (Directed Graph)
  - 두 정점을 연결하는 간선에 방향이 존재하는 그래프

  • 간선의 방향으로만 이동할 수 있다.
    

가중치 그래프 (Weighted Graph)

• 네트워크(Network)라고도 부름
• 간선에 비용이나 가중치가 할당된 그래프
  

연결 그래프 vs 비연결 그래프

• 연결 그래프 (Connected Graph)
  - 무방향 그래프에 있는 모든 정점쌍에 대해서 항상 경로가 존재하는 경우

  • Ex) 트리(Tree) : 사이클을 가지지 않는 연결 그래프

• 비연결 그래프 (Disconnected Graph)
  - 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

완전 그래프 (Complete Graph)

• 모든 정점이 간선으로 연결되어 있는 그래프
  

구현 방법

인접 리스트 (Adjacency List)

• 그래프의 노드들을 리스트로 표현한 방법

• 주로 정점의 리스트 배열을 만들어 관계를 설정하여 구현합니다.
  

• 장점
  1. 정점들의 연결 정보를 탐색할 때 O(n)의 시간이면 가능합니다. (n : 간선의 갯수)
  2. 필요한 만큼의 공간만 사용하기 때문에 공간의 낭비가 적습니다.

• 단점
  1. 특정 두 점이 연결되어 있는지 확인하는 시간이 인접행렬에 비해 오래 걸립니다.
  2. 구현이 비교적 어렵습니다.

**인접 행렬 (Adjacency Matrix)

• 그래프의 노드를 2차원 배열로 만든 것입니다.

• matrix[i][j] 가 true라면 i → j로의 간선이 존재한다는 뜻이다.
  

• 장점
  1. 두 점에 대한 연결 정보를 탐색할 때 O(1)의 시간복잡도면 가능합니다.
  (2차원 배열안에 모든 정점들의 간선 정보를 담기 때문에)
  2. 구현이 비교적 간편합니다.

• 단점
  1. 모든 정점에 대해 간선 정보를 대입해야 하므로 O(n2)의 시간복잡도가 소요됩니다.
  2. 무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비됩니다.