Graph (그래프)

✅ Graph (그래프)란?

노드(node)와 간선(edge)으로 이루어진 자료 구조

---

Graph 종류

그래프는 방향성에 따라 무방향 그래프(Undirected Graph), 방향 그래프(Directed Graph)로 나눌 수 있다.

 

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

• 간선을 통해서 양 방향으로 갈 수 있다.
• 정점 A와 정점B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현한다.
  (A, B) = (B, A) 동일

2. 방향 그래프 (Directed Graph)

• 간선에 방향성이 존재한다.
• A ➡ B로만 갈 수 있는 간선은 <A, B>로 표현한다.
  <A, B>는 <B, A>와 다름

---

Graph 용어

• 노드(node)
  위치라는 개념 (node라고도 부름)
• 간선(edge)
  위치 간의 관계 즉, 노드를 연결하는 선
• 인접 정점(adjacent verte)
  간선에 의해 직접 연결된 정점
• 정점의 차수(degree)
  무방향 그래프에서 하나의 정점에 인접한 정점의 수
  
  ➡ 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 무방향 그래프의 간선 수의 2배
• 진입 차수(in-degree)
  방향 그래프에서 외부에서 오는 간선의 수 (내차수)
• 진출 차수(outdegree)
  방향 그래프에서 외부로 향하는 간선의 수 (외차수)
  
  ➡ 방향 그래프에 존재하는 정점의 진입 / 진출 차수의 합 = 방향 그래프의 간선의 수 
  
• 경로 길이(path length)
  경로를 구성하는 데 사용된 간선의 수
• 단순 경로(simple path)
  경로 중에서 반복되는 정점이 없는 경우

---

🖋 Graph의 구현

graph를 코드로 표현하는 방법에는 크게 두 가지가 있는데 하나는 인접 리스트를 사용하는 방법과, 인접 배열을 사용하는 방법이 있다.

 

1. 인접 리스트(adjacency list)

인접 리스트는 각 노드에 인접한 다른 노드들을 하나의 연결 리스트로 표현하는 방법이다.

 

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

 

2. 인접 배열(adjacency matrix)

그래프를 구성하는 노드에 대해 두 노드를 연결한 간선의 유무를 저장할 때 정방행렬을 사용한다.

(행렬의 크기 = 노드의 수 x 노드의 수)

하나의 노드에서 자기 자신으로의 자체 간선은 있을 수 없으므로 인접 행렬의 대각선의 값은 항상 0이다. 무방향 그래프에서는 1[a][b]와 1[b][a]값이 같기 때문에 대각선을 기준으로 대칭을 이루고, 방향 그래프에서는 각기 다른 간선이기 때문에 대칭을 이루지 않는다.

if(A, B 연결) {
  matrix[A][B] = 1;
} else {
  matrix[A][B] = 0;
}

 

---

인접 리스트 vs 인접 행렬

인접 리스트	인접 행렬
간선이 적을 때 유용	간선이 많을 때 유용
장점 : 노드에 연결된 다른 노드를 쉽게 찾을 수 있다.	장점 : 두 노드의 연결 여부를 즉시 알 수 있다.
단점 : 연결 여부를 확인하려면 오래 걸린다.	단점 : 연결된 다른 노드를 찾으려면 모든 노드를 조사해야 한다.

---

🖋 그래프 메서드 (Method)

.addNode() : 정점(노드)를 추가

.contains() : 해당 노드의 존재유무 확인

.removeNode() : 해당 노드 제거

.hasEdge() : 두 노드 사이 간선 연결여부 확인

.addEdge() : 두 노드 사이 간선 추가

.removeEdge() : 간선 제거