Graph

컴퓨터 공학에서 이야기하는 자료구조 그래프는 아래와 같이 복잡한 네트워크 망과 같은 모습을 하고 있습니다

그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다

직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다

간접적인 관계라면 몇개의 점과 선에 걸쳐 이어집니다

하나의 점을 그래프에서는 정점이라 표현하고 하나의 선은 간선이라 합니다

비가중치 그래프

추가적인 정보를 파악할 수 없는 그래프, 가중치(연결의 강도가 얼마나되는지)가 적혀있지 않은 이런 그래프를 비가중치 그래프 라고 합니다

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
// 서로 간의 거리같은 중요한 정보가 없음

그래프 용어

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

그래프의 표현방식

인접행렬

인접(adjacency) 이라는 용어를 찾을 수 있습니다 두 정점을 바로 이어주는 간선이 있다면 이 두 정점은 인접하다고 이야기합니다

만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표입니다. 만약 가중치 그래프라면 1 대신 관계에서 의미 있는 값을 저장합니다. 위의 내비게이션 예제라면, 거리를 입력하면 좋습니다. 네비게이션 그래프를 인접 행렬로 표현하면 다음과 같습니다.

• 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

인접 행렬은 언제 사용할까?

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

인접리스트

인접 리스트 는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현합니다

각 정점마다 하나의 리스트를 가지고 있으며 이 리스트는 자신과 인접한 다른 정점을 담고 있습니다

보통은 중요하지 않습니다다. 그래프, 트리, 스택, 큐 등 모든 자료 구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있습니다. 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해 구현할 수 있습니다. 이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있습니다. 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 됩니다.

• 우선 순위를 다뤄야 한다면 더 적합한 자료구조(ex. queue, heap)를 사용하는 것이 합리적 입니다. 따라서 보통은 중요하지 않습니다. (언제나 예외는 있습니다.)

인접 리스트는 언제 사용할까?

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