TLDR

• 그래프는 여러 노드가 엣지로 연결된 자료 구조이다.

• JS에선 그래프를 인접 행렬과 인접 리스트로 만든다.

정의

컴퓨터 과학에서 그래프는 수학의 그래프 이론에서 정의된 무방향 그래프와 방향 그래프 개념을 구현하기 위한 추상 자료형이다. - wikipedia (graph)

graph TD

A[A] --> B[B];
A --> C[C];
B --> D;
B --> E;
C --> F;
C --> G;

이전 글에서 HTML 트리, DOM api의 자료 구조를 비교하며 "그래프"에 대해 조금은 더 근본적인 탐구를 해보았다. 문제 풀이에만 집중하다 보니, 기본 개념을 제대로 안살펴본 것 같아 그래프 구조, 탐색, 구체적 탐색법을 나눠 글을 작성했다.

작성하면서 느낀 거지만, 알면 알수록 깊고 심오한 내용으로 다가온다.(?)

기본 요소

그래프의 기본 요소들은 다양한 이름으로 불리지만, 아래의 정의로 통일한다.

    A ---- 0번 노드 
  /   \ 
 B     C ---- 2번 노드
 └ 1번 노드
 
예시 노드 { 인덱스 : 저장 값 }
{ 0 : "A" } { 1 : "B" } { 2 : "C" }

노드

• 그래프를 구성하는 기본 단위로, 데이터를 저장하는 개체이다.

• 노드 인덱스 + 노드 값 : 노드는 고유한 식별자와 안에 저장된 데이터로 구성된다.

노드 인덱스: 노드의 식별자. 0, 1, 2을 인덱스로 사용해 노드에 접근하고, 그래프 전체를 탐색할 수 있다.
노드 데이터(값): 각 노드에 저장된 값. 노드는 인덱스와 별도의 데이터(값, 라벨, 가중치 등)를 저장할 수 있다.

노드 = ●    엣지: ● --- ● (노드 사이의 선)
높이 = 3

┌            ● - 루트         - 레이어 0
|           / \
|          /   \
높이       ●     ● - 깊이 = 1  - 레이어 1
|        / \   / \
|       ●   ● ●   ●          - 레이어 2
|      /           \
└     ●             ● - 리프  - 레이어 3

• 루트와 리프 : 트리 구조에서 최상위 노드를 루트, 자식이 없는 노드를 리프라 한다.

• 엣지(간선): 노드 간의 관계를 나타내며, 두 노드를 연결하는 선이다.

• 깊이: 주로 트리 구조에서 사용된다. 깊이(depth)는 특정 노드에서 루트까지의 거리이다.

• 레이어(층위): 그래프에서 특정 노드가 몇 단계 깊이(depth)에 위치하는지를 나타낸다.

• 높이: 그래프 전체의 최대 깊이는 높이(height)라고 부른다. 예를 들어, 트리에서 높이는 루트 노드부터 가장 깊은 리프 노드까지의 길이로 정의한다.

방향:                 
   ●        ● <--> ● <--> ●    
 ↙   ↘ 
●     ●


순환: 어느 노드에서 출발해도 재자리로 돌아올 수 있음
    ●
  ↗   ↘ 
 ●  ←  ● 

가중치: ● --(5)-- ●  (엣지에 숫자로 표현)

• 방향: 엣지가 단방향인지, 양방향인지에 따라 방향 그래프와 무방향 그래프로 구분된다.

• 순환: 그래프 내에서 동일한 노드로 돌아올 수 있는 경로가 있을 때 순환한다.

• 가중치: 엣지에 부여된 값으로, 특정 노드에서 다른 노드로 이동하는 비용이나 거리 등을 나타낸다.

종류

그래프는 가장 상위의 개념이다. 방향, 순환, 가중치 등 요소로 분류할 수 있다. 예를 들어 HTML 트리는 비순환 방향 비가중치 그래프이다. 어떤 그래프인 지 감이 잡히지 않을 때, 조금 더 구체적으로 그래프를 파악할 수 있다.

순환

비순환 그래프       순환 그래프
     ●              ●
   ↙   ↘          ↗   ↘ 
  ●     ●        ●  ←  ●  
                  ↖   ↙
     0              ●              
   ↙   ↖          
  1  ←  2 
  비순환 그래프

• 순환 그래프 : 노드들이 특정 경로를 따라 다시 자기 자신으로 돌아올 수 있는 그래프.

• 비순환 그래프 : 순환 경로가 존재하지 않는 그래프.

방향

● --- ● --- ●     무방향 그래프
● --> ● --> ●     단방향 그래프
● <--> ● <--> ●   양방향 그래프

• 방향 그래프 : 엣지에 방향성이 존재하는 그래프. (단방향/양방향)

• 무방향 그래프 : 엣지에 방향성이 없는 그래프.

가중치

● --(5)-- ●  가중치 그래프
● ------- ●  비가중치 그래프

• 가중치 그래프 : 엣지에 가중치 값이 있는 그래프.

• 비가중치 그래프 : 엣지에 가중치가 없는 그래프

트리*

이진 트리
	      A  --루트----┐       
	   ↙     ↘        |  
 	  B       C    ---┼- 서브 트리           
    ↙  ↘     ↙        | 
   D    E   F      ---┘   
   └ 리프 (D~F)   

트리는 프론트엔드 개발에서 자주 사용되며, 특히 코딩 테스트에선 이진 트리가 자주 사용된다.

특징

• 단방향, 비순환 그래프이다.

• 루트 노드는 하나이며, 이로 인해 레이어가 계층을 이룬다.

• 임의의 두 노드를 연결하는 유일한 경로만 존재한다.

• 일반적으로 루트에서 리프까지 내려갈 수록 노드의 숫자가 점차 증가한다.

• 부분과 전체의 구조가 일치

• 서브 트리: 특정 노드를 루트로 하는 하위 트리. (ex: 위에선 A-B-C, B-D-E, C-F)

  • 서브 트리도 전체 트리처럼 여전히 트리이다 (ex: C-F).

• 이진 트리 : 각 노드가 최대 두 개의 자식을 가지는 트리.

이외로 다양한 형태의 트리가 있다.

• 힙: 특정 규칙에 따라 구성된 완전 이진 트리.

• AVL 트리 : 자동 균형 조정이 이루어지는 이진 탐색 트리.

• 레드-블랙 트리 : 삽입, 삭제 시 균형을 유지하는 이진 탐색 트리.

• B-트리 : 데이터베이스 시스템에서 널리 사용되는 균형 트리 구조.

힙

힙
	      8  ---- 루트(최대 값)     
	   ↙     ↘          
 	  4       5              
    ↙  ↘     ↙  ↘          
   2    3   2    3 ---- 리프(최소 값)    

힙은 노드에 저장된 값을 특정 규칙에 따라 구성한 이진 트리이다. 노드 데이터가 무엇이든, 엣지로 연결된 노드들을 그래프로 간주하지만, 힙은 노드 데이터에 따라 노드 트리로된다. "특정 규칙"은 결국 이렇게 표현될 수 있다.

• 최대 힙 : 부모 노드가 자식보다 항상 큰 값을 가짐.

• 최소 힙 : 부모 노드가 자식보다 항상 작은 값을 가짐.

힙은 특정 규칙으로 우선 순위를 반영할 수 있다. 새로운 개념이 많이 등장하니, 상세한 내용은 추후 살펴보도록 한다.

힙에 새로운 노드가 추가되거나 삭제되면, "힙 속성"을 유지하기 위한 로직이 수행된다. JS에서는 보통 배열로 구현되며, 우선순위 큐Priority Queue로 정렬한다.

기타 유형

이외에도 다양한 그래프가 있다.

• 멀티 그래프: 두 노드 사이에 여러 개의 엣지가 존재할 수 있는 그래프.

• 유사 그래프: 멀티그래프의 한 유형으로, 자기 자신을 향하는 엣지를 포함할 수 있음.

• 완전 그래프: 모든 노드가 서로 연결된 그래프.

• 이분 그래프: 노드 집합이 두 개의 그룹으로 나뉘고, 같은 그룹 내에서는 엣지가 없는 그래프.

• 평면 그래프: 엣지가 교차하지 않고 평면에 그릴 수 있는 그래프.

• 희소 그래프: 엣지 개수가 노드 개수에 비해 상대적으로 적은 그래프.

• 밀집 그래프: 엣지 개수가 노드 개수에 비해 상대적으로 많은 그래프.

그래프 in JS

인접 행렬과 인접 리스트*

대표적인 그래프 구현 방법은 인접 리스트와 인접 행렬이다. 목적에 따라 적합한 형태를 활용한다.

인접 행렬

인접 행렬은 그래프의 노드 연결 관계를 2차원 배열(행렬)로 표현하는 방식이다.

인접 행렬의 구조
배열[노드1][노드2] = 값 (값으로 노드1,2의 연결 관계를 표현한다.)
배열[행 번호 row][열 번호 col] = 0 | 1 (not 연결/연결)
row와 col의 최댓값은 같아야한다.

• 인접 행렬에서 노드 인덱스는 노드 데이터와 같다.

• 인접 행렬에서 노드 인덱스는 배열의 인덱스와 동일하다.

• 두 노드의 연결 여부(엣지)가 인접 행렬에 저장된다.

• 2차원 배열(행렬)에서 노드 1은 행 번호, 2는 열 번호이다.

• 노드가 N개면 NxN 크기의 배열로 행렬을 나타낸다.

노드 데이터의 의미

인접 행렬에서 두 노드를 통해 값을 얻을 수 있다. 값은 다양한 형태와 의미를 갖을 수 있다.

가장 기본적인 방식은 인접 행렬이 두 노드의 연결 관계를 나타내는 것이다.

const adjacencyMatrix = [
  [0, 1, 1, 0], // 0번 노드는 1, 2와 연결
  [1, 0, 0, 1], // 1, 2번 노드는 0, 3과 연결
  [1, 0, 0, 1],
  [0, 1, 1, 0] // 3번 노드는 1, 2와 연결
];

/* 
이 행렬을 그래프로 표현하면 다음과 같다
    0 
   / \
  1   2
   \ /
    3
 모두 연결된 순환 그래프인 것을 알 수 있다.
*/

adjacencyMatrix의 두 인덱스는 그래프에서 두 노드를 가리키고, 데이터는 엣지를 나타낸다. adjacencyMatrix는 노드가 4개로 이루어진 그래프를 표현한다.

• 0번 노드와 1번 노드는 adjacencyMatrix[0][1] = 1이므로 연결되어있다.

• adjacencyMatrix[0][3] = 0으로 노드 0,3은 연결되어 있지 않다.

장단점

✅ 장점:

• 구현이 직관적이고 단순하다.

• 두 노드의 인덱스로 행렬에 O(1)로 접근해 값을 얻을 수 있다.

✅ 단점:

• 행렬이기 때문에 불필요한 공간 낭비가 생긴다.

• 가장 큰 노드 인덱스를 기준으로 행렬 크기가 결정되어 차이가 클 수록 공간 낭비가 커진다.

  • 3 노드의 인덱스가 1, 2, 999 이라면, 가장 큰 인덱스 999로 전체 행렬이 만들어진다

• 이런 경우 행렬에는 연결되지 않음을 나타내는 불필요한 값이 행렬 대부분을 차지한다.

• 간선이 노드보다 매우 적은 그래프를 희소 그래프라고 하며, 이때 행렬은 대부분 비효율적이다.

NOTE

❓ 인접 행렬은 항상 두 노드의 연결 여부를 나타낼까

노드 인덱스
인접 행렬에서 인덱스가 곧 노드인 경우가 일반적이지만, 예외도 많다.

• 변환(예: 문자열 ID, 객체): 데이터를 인접 행렬로 변환해야 할 때. 데이터와 행렬을 맵핑하면서 노드 인덱스를 숫자로 만들고, 행렬에 두 노드 연결 여부를 반영해야 한다.

• 노드 번호가 특정 범위(예: 1부터 시작)인 ...