Graph(그래프)

컴퓨터 공학에서의 그래프 : 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조.

그래프의 실사용 예제

서울에 사는 A는 부산에 사는 B와 오랜 친구 사이입니다. 이번 주말에 B의 결혼식이 있다고 하여 A는 차를 몰고 부산으로 가려고 합니다. 마침, 대전에 살고 있는 A와 B의 친구 C도 참석을 한다고 하여 A는 대전에서 C를 태워 부산으로 이동을 하려고 합니다.

위의 예제 에서는 3개의 정점이 존재합니다: A, B, C가 사는 각각의 도시를 그래프의 정점에 대입할 수 있습니다. 그리고 이 3개의 정점은 서로 이어지는 간선(관계)을 가지고 있다.

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}
console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

---

• 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 현재의 그래프는 비가중치 그래프 라고 부른다.
• 비가중치 그래프는 각 정점간의 연결 유무만을 판단하는 반면, 가중치 그래프는 더 자세한 정보를 담을 수 있습니다.

• 비가중치 그래프
  정점: 서울, 대전, 부산
  간선: 서울—대전, 대전—부산, 부산—서울

• 가중치 그래프
  정점: 서울, 대전, 부산
  간선: 서울—140km—대전, 대전—200km—부산, 부산—325km—서울

---

알아둬야 할 그래프 용어들

• 무향그래프(undirected graph): 앞서 보았던 내비게이션 예제는 무향 그래프 입니다. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능합니다. 하지만 단방향(directed) 그래프로 구현 된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
• 인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
• 자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
• 사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다. 내비게이션 예시에선 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로 사이클이 존재하는 그래프 입니다.

---

인접 행렬

A의 진출차수는 1개 입니다: A —> C
[0][2] === 1
B의 진출차수는 2개 입니다: B —> A, B —> C
[1][0] === 1
[1][2] === 1
C의 진출차수는 1개입니다: C —> A
[2][0] === 1

Q) 언제 인접 행렬을 사용하면 좋을까?

• 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이.
• A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있습니다.
• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됩니다.

---

인접 리스트

Q) 인접 리스트는 언제 사용하면 좋을까?

• 인접 행렬은 연결 가능한 모든 경우의 수를 저장.
• 서로 인접하지 않다면 0을, 인접하다면 1을 저장하기 때문에 메모리를 많이 차지하게 됩니다.
• 메모리를 효율적으로 사용하고 싶다면 인접 행렬 대신 인접 리스트를 사용합니다.

---