Graph란 무엇인가

자료구조의 그래프는 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 보이고있다.

• 정점 (vertex): 하나의 점
• 하나의 선(edge) : 간선

Graph의 실사용예제

• 포털사이트의 검색엔진, SNS에서 사람들과의 관계, 네비게이션 (길찾기) 등에서 사용하는 자료구조
• 세 가지 모두 수많은 정점을 가지고 있고, 서로 관계가 있는 정점은 간선으로 이루어져있다.

네비게이션 예시

정점: 서울, 대전, 부산
간선: 서울ㅡ대전, 대전ㅡ부산, 부산ㅡ서울

하지만 정점에 시카고를 추가한가도 하면? 자동차로는 한국에서 시카고로 이동할 수 없기 때문에, 어떠한 간선을 추가할 수 없다. Graph에서는 이런 경우를 관계가 없다 라고 표현한다.

비가중치 그래프

위의 간선을 살펴보면, 서울, 대전, 부산이 서로 관계가 있다는 것은 알 수 있지만, 각 도시가 얼마나 떨어져있는지는 알 수 없다. 이렇게 추가적으로 정보를 파악할 수 없는 그래프, 가중치(연결의 강도가 얼마나 되는지) 가 적혀있지 않은 그래프를 비가중치 그래프라고 한다. 간단한 JS Object를 이용하여 비교할 수 있다.

let isConnected = {
	seoul: {
    	busan: true;
    	daejeon: true;
    },
  ...
}
 console.log(isConnected.seoul.daejeon) // true;
[비가중치 그래프로 나타낸 서울, 대전, 부산 그래프]

위 정보만으로는 서울에서 부산까지 갈 수 있다는 사실외에 파악할 수 있는 정보가 없다. 네비게이션이라면, 적어도 각 도시간의 거리가 얼마나 되는지 표시해야한다. 그래서 가중치 그래프로 바꾸고, 각 도시간의 거리를 표시한다면 어떨까? 가중치 그래프는 더 자세한 정보를 담을 수 있기 때문이다.

• 정점: 서울, 대전, 부산

• 간선: 서울ㅡ140kmㅡ대전, 대전ㅡ200kmㅡ부산, 부산ㅡ325kmㅡ서울

이렇게 네비게이션은 간선에 거리를 표시한 가중치 그래프가 확장되어서, 수백만개의 정점(주소)과 간선이 추가되어서 네이게이션에서 쓰는 자료구조와 비슷해진다.

알아둬야할 Graph 용어들

• 무(방)향그래프 (undirected graph)
  => 위의 네이게이션 예제는 무(방)향 그래프이다. 서울에서 부산을 갈 수 있듯이, 반대로 부산에서 서울까지도 가능하다. 하지만 단방향 그래프로 구현된다면, 부산에서 서울로 가는 것은 불가능하다. 만약 두 지점이 일방통행 도로로 이어져있다면, 단방향인 간선으로 표현할 수 있다.

• 진입차수 (in-degree) / 진출차수(out-degree)
  => 한 정점에 진입(들어오는 간선) 하고 진출 (나가는 간선)하는 간선이 몇개인지를 나타낸다.

• 인접(adjacency) :
  => 두 정점간에 간선이 이어져 있다면, 이 두 정점은 인접한 정점이다.

• 자기 루프 ( self loop)
  => 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현한다. 다른 정점을 가지지 않는다는 것이 특징이다.

• 사이클(cycle)
  => 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다 라고 표현한다. 네비게이션 Graph는 서울 > 대전 > 부산 > 서울 로 이동이 가능해서 , 사이클이 존재하는 Graph이다.

question

• 위 네비게이션 예제에서 서울은 몇개의 진입차수와 , 진출차수를 가지고 있나?
  => 진입차수는 대전과 부산 으로 갈 수 있어서 2개이고 진출 차수는 서울 하나여서 1개인 것 같다.

• 네비게이션 대신 SNS에서 자료구조를 그래프로 이용한다면, 정점과 간선은 무엇일까?
  => 개개인의 프로필이 정점이고 간선은 서로 친구일때 연결되는 것 같다.

• SNS에서 어떤 관계일 경우, 단방향 그래프가 생성될까?
  => 맞팔로우가 안되어있는 상황?

• 자기 루프와 사이클은 어떻게 다를까?
  => 자기 루프는 좀 폐쇄적일 것 같고 사이클은 소통이 가능한 구조인 것 같다.

Graph의 표현방식

인접행렬

위에서 인접이라는 용어을 설명했듯이, 두 정점을 바로 이어주는 간선이 있다면, 두 정점은 인접하다고 말한다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타난다. 만약 A라는 정점과 B라는 정점이 이어져있다면, 1(true), 아니면 0 (false)로 표시한 일종의 표이다.

만약 가중치 그래프라면 1대신 관계에서 의미있는 값을 저장한다. 위의 네비게이션 예제라면, 거리를 입력하면 좋겠다.

네비게이션 Graph를 인접행렬로 표현하면?

ㅡㅡㅡㅡㅡto A B C
from A ㅡㅡ0 0 1 => 0번째 인덱스
ㅡㅡBㅡㅡ 1 0 1 => 1번째 인덱스
ㅡㅡCㅡㅡ1 0 0 => 2번째 인덱스

• A의 진출 차수 1개
  • [0][2] === 1

• B의 진출 차수 2개
  • [1][0] === 1
  • [1][2] === 1

• C의 진출 차수 1개
  • [2][0] === 1

인접 행렬은 언제 사용하나?

• 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지 없는지 파악한다.
  • ex) A to B 로 진출하는 간선이 있는지 파악하기 위해서는 0번째 줄의 1번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있다.

• 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용한다.

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 리스트는 자신과 인접한 다른 정점을 담고 있다. 위 그래프를 인접 리스트로 표현하면

A->C->Null
B->A->C->Null
C->A->Null

question

• B는 A와 C로 이어지는 두개의 간선이 있는데, 순서가 중요한가?
  => 보통은 종요하지 않다.

  Graph, Tree, Stack, Queue 등 모든 자료구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가 및 삭제할 수 있다. Graph를 인접 리스트로 구현할 때, 정점별로 살펴봐야할 우선순위를 고려해 구현할 수 있다. 이때, 리스트에 담겨진 정점들을 우선 순위 별로 정렬할 수 있다. 우선 순위가 없다면, 연결된 정점들을 단순하게 나열한 리스트가 된다.

• 우선 순위를 다뤄야한다면, 더 적합한 구조 (Queue, heap) 를 사용하는 것이 합리적이다. 따라서 예외는 있지만, 보통은 중요하지 않다는 것이다.

인접 리스트는 언제 사용하나?

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