Data Structure(4) Graph(그래프)

Graph (그래프)

---

Graph(그래프)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다. 지하철 노선도처럼 서로 연결된 데이터들이 어떤 관계인 지 표시할 때 주로 사용한다.

 

출처 :  https://lovit.github.io/nlp/graph/2018/08/21/ford_for_shortestpath/

 

 

let subway = {
  '교대': ['동대문운동장','사당','충무로'],
  '동대문운동장': ['교대','을지로3가','충무로'],
  '사당': ['교대','서울역', '신도림'],
  '서울역': ['사당','시청','신도림','충무로'],
  ...}

 

Graph 종류

그래프는 방향성을 가졌는지 여부에 따라 방향 그래프(Directed Graph), 무방향 그래프(Undirected Graph)로 구분할 수 있다.

 

1. 방향 그래프(Directed Graph)

방향 그래프는 말 그대로 방향을 나타내는 화살표가 있는 그래프이다. 방향성이 있기 때문에 연결된 두 노드는 비대칭적인 관계를 이루고 있다고 할 수 있다. A노드에서 B노드로 향한다고 가정하면, <A, B>와 같이 표시한다. 두 노드는 비대칭적 관계에 있기 때문에 B에서 A노드로 향하는 <B, A>는 <A, B>와 다른 의미를 갖는다.

 

2. 무방향 그래프(Undirected Graph)

무방향 그래프는 양쪽으로 모두 이어진 방향성이 없는 그래프이다. 따라서 연결된 두 노드도 공평한 대칭적 관계를 이루고 있다. A, B노드가 연결되어 있다고 가정하면, (A, B)처럼 묶어서 표현하며 (A, B)와 (B, A)는 동일한 표현으로 취급한다.

 

출처 : https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c

 

Graph 관련 용어

노드(node) : 위치, 정점(vertex)

간선(edge) : 위치 간의 관계. 노드-노드를 연결하는 선 (link, branch)

인접 정점(adjacent vertex): 간선에 의해 직접 연결된 정점

 

진입 차수(in-degree) : 외부에서 오는 ← 간선의 수 (내차수) in 방향그래프

진출 차수(out-degree) : 외부로 향하는 → 간선의 수 (외차수) in 방향그래프

 

경로 길이(path length) : 경로에 사용된 간선 수

단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우

오일러 경로(Eulerian tour) : 모든 간선을 한 번만 통과하고 처음으로 되돌아오는 경로 (모든 정점에 연결된 간선의 수가 짝수일 때만 존재)

 

 

그래프(Graph)의 구현

1. 인접 리스트 (Adjacency List)

 

그래프를 구현할 때 사용하는 가장 일반적인 방법으로, 모든 노드들을 인접 리스트에 저장한다. 각 노드에 인접한 다른 노드들을 하나의 리스트로 표현한다. 리스트 형태는 배열, 해시테이블,  연결리스트 등이 될 수 있다. 노드가 몇 번인지만 알면 이 번호를 배열의 index로 이용할 수 있기 때문에, 각 노드와 연결된 다른 노드들이 담긴 배열에도 쉽게 접근할 수 있다. 보통 인접 리스트는 그래프에 간선이 적을 때 (희소 그래프(Sparse Graph)일 때) 주로 사용한다.

 

아래 객체를 그림으로 표현한 모습

 

Nodes = { 
  0: [1],
  1: [2, 4],
  2: [0],
  3: [2],
  4: [3, 1] 
  }

 

 

2. 인접 행렬(Adjacency Matrix)

 

인접 행렬은 그래프를 0과 1을 이용한 정수 행렬(Integer Matrix)로 표현하는 방식이다. n*n 만큼의 공간에 노드들의 연결 여부가 boolean값으로 들어가게 된다. 코드로 표현해보면 아래와 같은 느낌이다. 인접 행렬은 그래프에 간선이 많을 때 (밀집 그래프(Dense Graph) 일 때) 주로 사용한다.

 

if (a, b가 연결됨) {
  matrix[a][b] = 1;
} 
else {
  matrix[a][b] = 0;
}

 

 

인접 리스트 vs 인접 행렬

인접 리스트와 인접 행렬은 각각의 장단점이 분명하기 때문에 상황에 맞게 사용할 필요가 있다. 어떤 차이점이 있는지 정리해둔 표를 통해 비교해보자. 

 

인접 리스트	인접 행렬
간선이 적을 때, 희소 그래프(Sparse Graph)	간선이 많을 때, 밀집 그래프(Dense Graph)
👍🏻 노드에 연결된 다른 노드들을 쉽게 찾을 수 있음	👍🏻 두 노드의 연결 여부를 즉시 알 수 있음 (M[i][j]) O(1)
👎🏻 두 노드의 연결여부를 확인하려면 오래 걸림	👎🏻 연결된 다른 노드들을 찾으려면 모든 노드를 조사해야 함 O(N^2)

 

 

+ 그래프(Graph) 메서드

.addNode() : 새로운 노드 생성 + 그래프에 추가
.contains() : 그래프에 해당 노드가 존재하는지 확인
.removeNode() : 노드 제거

.addEdge() : 새로운 간선 생성 + 두 노드 연결
.hasEdge() : 노드 연결여부 확인
.removeEdge() : 간선 제거
.forEachNode() : 각 노드를 한 번씩 거쳐 그래프 순회