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부터 시작)인 경우:
matrix[1][1]부터 사용하며,0번 인덱스는 비워둘 수 있다.
노드 데이터 (배열의 값)
인접 행렬에 들어있는 값은 문제에 따라 다를 수 있다. 조건에 따라 노드 값은 연결 관계를 나타낼 수도, 아닐 수도 있다. (ex: 노드 값 = 가중치 ) 혹은 노드 연결 관계를 구현하는 것 자체가 문제일 수도 있다.
경험 상 DFS, BFS 등 그래프 탐색에 사용해야 하는 경우가 잦아 인접 행렬의 기본 개념을 확실히 해두는 것이 중요하다.
인접 리스트
인접 리스트는 반대다. 인접 행렬과 달리, 연결된 노드만 저장하여 공간 효율성이 높다. 인접 리스트는 보통 배열로 그래프 연결 관계를 표현한다.
인접 리스트 배열에서 인덱스는 보통 노드 인덱스를 가리킨다.
인접 리스트 예시
인덱스 = 노드 번호
배열[인덱스] = 값 // 값은 연결 관계인 노드 번호나 가중치 등 다양한 형태가 될 수 있다.하지만 인접 행렬과 마찬가지로 주어진 문제에 따라 다양하게 표현되거나 변환이 필요할 수 있다.
노드 데이터의 의미
배열로 표현된 인접리스트는 다음과 같다.
// 1차원 배열
const adjacencyList = [-1, 0, 0, 1, 1, 2, 2, 3]
// 1,2번 노드는 0번과, 3,4번 노드는 1번과, 5,6은 2, 7은 3과 연결
// 보통 루트는 -1로 표기하나,
const adjacencyList = [Infinity, 0, 1, 1, 2, 2, 3, 3]
// 인덱스 0번에 빈 값으로 Infinity 등 빈값을 넣기도 한다.
// 저장 값이 더 복잡한 형태로 표현된 인접 리스트
const weightedGraph = [
[[1, 5], [2, 10]], // 노드 0이 노드 1과 가중치 5, 노드 2와 가중치 10으로 연결됨
[[0, 5], [2, 3]], // 노드 1이 노드 0과 5, 노드 2와 3으로 연결됨
[[0, 10], [1, 3]] // 노드 2가 노드 0과 10, 노드 1과 3으로 연결됨
];장단점
장점과 단점은 인접 행렬과 반대이다.
✅ 장점:
공간 효율성이 좋다. 메모리를 적게 사용한다.
인접 행렬과 반대로 희소 그래프(노드가 엣지보다 상대적으로 많은 경우) 유리하다.
그래프 표현이 인접 행렬보다 직관적이다. 불필요한 값이 줄어들고, 연결 관계와 노드 값만 남긴다.
✅ 단점:
인접 행렬보다 탐색 효율이 낮다.
최악의 경우 모든 엣지를 확인해야 하여 O(E = 엣지 갯수)이 될 수 있다.
그래프가 가독성이 떨어진다. 데이터 구조가 복잡해질 수록 더 파악이 어려울 수 있다. (위의
weightedGraph가 예시이다.)
NOTE
❓ 인접 리스트의 인덱스와 값은 항상 노드 인덱스와 엣지(연결 관계)일까
노드 인덱스와 노드에 저장된 값을 적절히 설계해야 한다.
배열을 사용해 인덱스를 노드로, 값을 엣지로 하는 것은 직관적이다. 하지만 행렬과 마찬가지로 인접 리스트를 직접 만드는 것 자체가 문제 의도일 수 있다.
노드 인덱스
그래프 목적과 자료 구조에 따라 인덱스가 항상 노드 번호를 나타내지 않을 수 있다.
배열 인덱스로 엣지를 나타낼 수 없는 경우도 흔하다.
노드의 고유한 ID가 문자열이거나, 특정 데이터 구조가 필요한 경우
노드는 배열 인덱스가 아닌 키가 노드를 식별하고, 값이 연결 정보를 저장하게 된다.
배열 대신 객체(Map)를 활용하여 노드의 식별자를 키로 사용하는 방식도 가능하다.
노드 데이터 (배열 요소)
노드에 저장된 값이 추가적인 정보를 포함하는 경우
- 노드 값이 단순히 다음 노드를 가리키는 것이 아니라 가중치나 방문 여부 등을 나타낼 수도 있다.
인접 리스트가 주어지면, 인덱스와 배열 내부의 값이 각각 어떤 의미인지 파악하는 것이 중요한 단서를 준다. 이를 토대로 추론을 이어가야 수월하다.
경험 상 코딩 테스트 문제에서 그래프는 인덱스로 연결된 두 배열을 인접 행렬이나 인접 리스트로 만들어야 하는 경우가 많았다. ex) arr1과 arr2는 인덱스로 연결된 두 배열입니다.
JS로 그래프 표현하기
TLDR :
그래프 변환이 필요한 지 판단하고
탐색이 가능한 그래프를 판단하고 (리스트/ 행렬)
탐색을 수행하며 조건에 맞는 데이터를 얻는다
이제 인접 행렬과 인접 리스트가 구체적으로 어떻게 JS에서 표현되는 지 알아보자. 보통은 참조 타입인 객체, 배열로 표현된다. 코딩 테스트에서는 문제에서 매개변수로 주어진 데이터를 적절한 형태의 그래프로 변경해야 한다.
객체
JS에서 객체는 키-값 구조를 가지며, 그래프를 표현하는 방식 중 하나로 사용될 수 있다. 주로 인접 리스트 방식으로 표현된다. 주로 키는 노드, 값은 연결된 노드의 배열로 표현한다.
객체 인접 행렬
인접 행렬을 객체로 표현하는 것은 일반적이지 않다. 인접 행렬은 2차원 배열로 표현되며, 객체 기반 표현은 비효율적이다. 하지만 객체를 2차원 배열의 인접 행렬로 변환해야 될 때가 있다.
/*
{노드: 연결 관계[]}
문제의 매개변수 obj의 키는 노드, 값은 연결 관계를 배열로 나타낸다.
*/
const paramObj = { // 그래프 obj의 키는 문자이다.
A: ['B', 'C'],
B: ['D'],
C: ['D'],
D: []
};
// 객체로 주어진 그래프를 인접 행렬로 변경하는 함수
function convertToAdjacencyMatrix(obj) {
const nodes = Object.keys(obj); // A~D까지 노드를 모두 가져온다.
const size = nodes.length; // 그래프 전체 노드 개수와 같다.
// 빈 인접 행렬을 만든다.
const matrix = Array.from({ length: size }, () => Array(size).fill(0));
/* size X size 크기의 행렬에 0으로 모든 값을 채워 초기화한다
문제 조건에 따라 fill(x)는 다른 값이 될 수 있다.*/
// nodes A부터 D까지 순회하며 연결 관계를 인접 행렬에 업데이트한다.
nodes.forEach((node, i) => {
// node는 A~D, i는 현재 노드의 인덱스이다.
// 행렬은 배열이니, 문자열 노드 인덱스를 숫자로 바꿔 행렬에 넣는다.
// obj[node]는 노드의 값이다.
// 이 값은 현재 node와 연결된 모든 노드를 배열로 표현한다.
obj[node].forEach(adjNode => {
const j = nodes.indexOf(adjNode); // 연결된 노드의 인덱스를 찾는다.
// 현재 노드의 인덱스 i는 행 번호가 되고 adjNode의 인덱스 j는 열 번호가 된다.
if (j !== -1) matrix[i][j] = 1; // j가 -1이 아니라면, 즉 nodes에 존재한다면
// 연결 관계를 1로 설정한다
});
});
return matrix;
}
const adjacencyMatrix = convertToAdjacenctMatrix(paramObj)현재 노드 인덱스는 i, 연결된 노드의 인덱스는 j.
adjacencyMatrix[i][j] = 값은 0, 1 주목 할 만한 점은 객체 그래프를 행렬(2차원 배열)로 만들기 위해 노드 인덱스(A~D)를 숫자로 변환하는 것이다.
예시에서 이미 paramObj가 연결 관계를 나타내고 있지만, 행렬로 만들면 두 노드의 숫자 인덱스를 통해 연결 관계를 O(1)로 확인할 수 있다. 인접 리스트 탐색은 최악의 경우 O(N)이 될 수 있고, paramObj 구조가 복잡해질 수록 효율적 탐색을 떠올리기 어렵다. 이런 경우 일반적으로 인접 행렬은 노드가 1,000개 이하일 때 유용하게 사용할 수 있다고 한다. (제한 조건에서 매개 변수인 배열의 길이가 10^2 이하인 경우)
객체 인접 리스트
객체로 표현된 인접 리스트는 노드와 엣지를 문자로 나타난다. 깔끔하게 표현되어 인접 리스트의 장점이 잘 보인다. 그러나 객체로 그래프를 구현하는 것 자체가 문제 의도일 때가 많다. 특히 해결 과정의 중간 단계에서 직접 인접 리스트를 만들어야 할 때가 많다.
// 인접 리스트를 객체로 표현
const adjacencyListObj = {
A: ['B', 'C'], // A노드는 B, C를 자식 노드로 갖는다.
B: ['D'], // B, C 노드는 D를 자식 노드로 갖는다
C: ['D'],
D: [] // D는 자식이 없는 리프 노드다.
};
// Map으로 인접 리스트를 표현할 수 있다.
/*
아래 예시는 2개의 배열을 인접 리스트로 변환한다.
arr1 = 모든 노드의 배열, arr2 = 모든 노드의 연결 관계를 나타낸 배열.
문제에서 주어진 두 개의 매개변수가 각각 노드와 노드들의 연결 관계를 나타낸다.
*/
arr1 = ["A", "B", "C","D"]
arr2 = [["B","C"],["D"],["D"],[]]
const adjacencyListMap = new Map();
for(let i = 0; i < arr1.length; i++) {
const node = arr1[i]
const connectedNode = arr2[i]
if(adjacencyListMap.get(node)){
adjacencyListMap.set(node, []) // 빈 배열로 노드의 값을 초기화한다.
}
// .push는 참조된 값을 직접 변경하기에 set을 사용하지 않을 수 있다.
adjacencyListMap.get(node).push(connectedNode)
}두 개의 배열이 인덱스로 연결된 경우를 자주 볼 수 있다. 배열 안의 값이 문자라면 꽤 자주 접하는 패턴이다.
배열*
JS에서 배열과 그래프는 연관이 깊다.
배열 인접 행렬
인접 행렬은 보통 2차원 배열이다. 배열 행과 열이 각각 노드 번호를 의미하며, 행렬의 값은 두 노드 간의 연결 관계를 나타낼 수 있다. 앞서 살핀 객체 변환 말고도, 배열 데이터를 인접 행렬로 가공할 필요가 자주 생긴다.
// 인접 행렬: 일반적인 2차원 배열 방식
const adjacencyMatrixArray = [
[0, 1, 1, 0],
[1, 0, 0, 1],
[1, 0, 0, 1],
[0, 1, 1, 0]
];
// 인접 행렬을 1차원 배열로 압축하여 표현하는 방식
const flatMatrix = [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0];
// 결국 adjacencyMatrixArray을 flat()한 것과 같다.
// 1차원 배열을 다시 2차원 배열로 만든다.
const col = Math.sqrt(adjacencyMatrixFlat.length); // 4 = 행의 크기
const undoFlatMatrix = Array.from(
{ length: col },
(_, row) => flatMatrix.slice(row * col, (row + 1) * col)
);행렬을 만드는 것이 쉽기 때문에 활용하는 문제가 더 많다. 데이터가(ex:인덱스로 연결된 두 배열) 주어지고, 이를 행렬로 만든 뒤 연결 관계를 찾는 식이다. 인접 행렬 문제는 결국 이렇다:
핵심
매개 변수: arr1과 arr2는 길이가 동일하며 인덱스로 연결됩니다. (역시 다양한 변주가 있을 수 있다.)
x에서 y를 만족하는 z를 반환하시오.
x: arr1과 arr2, 데이터로 행렬을 만들라는 거다. 서술형으로 길게 풀어쓰면 놓치기 쉽다.
y: 조건이다. 조건은 결국 행렬에 있는 값의 일치 여부다. 행렬 안에는 보통 0과 1로만 표현될 수 있는 값이 들어간다. (ex: 양/늑대, 벽/통로, 바다/섬, 땅/석유, etc)
z: 사실상 정답과 가장 연관이 깊다. 유형마다 다르며, 적절한 탐색법이 요구된다. (ex: 연결된 노드 그룹의 갯수, 연결된 노드 그룹 중 가장 최대/최소의 노드 갯수, 연결된 노드가 있는 지의 여부 등)
/*
매개변수
arr1 = ["A", "B","C","D"] // arr1은 문자로 되어있고
arr2 = [0, 1, 1, 0] // arr2는 연결 관계가 아닌 특정한 값을 나타낸다.
보통 arr2는 육지나 바다, 통로 혹은 벽, 양 혹은 늑대 등 두가지를 뜻한다.
*/
function solution(arr1, arr2) {
const size = arr1.length;
const matrix = Array.from(
{ length: size },
(_, row) => arr2.slice(row * size, (row + 1) * size)
);
const visited = new Set();
let count = 0; // z = 연결된 노드 그룹의 갯수 일 때
let maxSize = 0; // z = 연결된 노드 그룹 중 최대 노드 개수 일때
const target = 2 // z = 특정 노드가 연결 그룹에 속해 있는 지 여부
// 행렬 문제는 자주 dfs로 탐색한다
function dfs(node) {
// 로직은 조건 y, 반환 값 z가 무엇이냐에 따라 달라진다
if (visited.has(node)){
// 더 깊은 내용은 DFS 글에서 다룬다.
// return;
// return 0;
}
// 생략....
}
}배열 인접 리스트
배열로 표현된 인접 리스트는 인덱스가 노드, 값이 연결 노드를 가리킬 때가 많다.
const list = [-1, 0, 0, 2, 1]
// 인덱스 = 자신의 노드 번호이고 값이 연결된 노드라면
list[0] = -1 // 보통 루트는 -1로 표현한다
list[1] = 0 // 1번 노드는 0번과 연결
list[2] = 0 // 2번은 0번과
list[3] = 2 // 3번은 2번과
list[4] = 0 // 4번은 1번과
// 2차원 배열로도 나타낼 수도 있다.
const list2D = [
[1, 2], // 0번 노드는 1, 2와 연결
[0, 4], // 1번 노드는 0, 4
[0, 3], // 2번은 0, 3
[2], // 3은 2
[1] // 4는 1
];list는 이런 그래프를 그린다.
0
/ \
1 2
/ /
4 3그래프 list가 복잡하고 추상적일 수 파악이 어렵고, 바로 그것이 문제 의도일 때가 많다.
// 가장 흔한 방식은 엣지가 배열로 주어진다.
const edges = [ [0, 1], [0, 2], [1, 4], [2, 3], [3, 2], [4, 1] ];
// 이 변수에서 노드는 0,1,2,3,4 5개이지만 엣지는 6개다.
const size = new Set(edges.flat()).size // 중복된 노드(숫자)를 없애고
// 1차원 배열로 리스트를 만든다면
// 인덱스가 노드, 값은 연결된 노드이다.
const list = Array(size).fill(-1) // -1 = 연결 없음을 나타내는 값으로 초기화
// 2차원 배열일 때: 인덱스 = 노드, 값 = 연결된 모든 노드[]
const list = Array.from({length:size}, () =>
[] // 빈 배열로 초가화
)
// 이후 edge를 순회하면서 list에 연결 관계를 업데이트한다.
for(let [nodeA, nodeB] of edges) {
// 1차원 배열
list[nodeB] = nodeA
// 여기서 nodeA,B 중복된 노드는 덮어쓰기 된다
// ex) [nodeA, nodeB] : [0,1] → [0,2] → [3,2] → [4,1]
// list[1]은 0 -> 4로, list[2] 0 -> 3으로 덮어쓰기
// 2차원 배열
list[nodeA].push(nodeB);
list[nodeB].push(nodeA);
// 중복된 노드가 추가될 수 있다.
// ex) list[0].push(1) : list[0] = [1]
// list[1].push(0) : list[1] = [0]
// list
}
// 1차원 배열 결과:
result = [
-1, // 0번 노드 → nodeA만 있고, 다른 노드에 의해 방문되지 않음 (루트 개념)
4, // 1번 노드 → 4번 노드를 통해 마지막으로 방문됨
3, // 2번 노드 → 3번 노드를 통해 마지막으로 방문됨
2, // 3번 노드 → 2번 노드를 통해 마지막으로 방문됨
1 // 4번 노드 → 1번 노드를 통해 마지막으로 방문됨
]
/*
0번 노드는 nodeA만 있어 값이 업데이트 되지 않는다.
배열 값이 덮어쓰기되는 것은 같은 노드가 다른 노드에서 여러 번 방문되기 때문이다.
그래서 배열의 값은 연결된 노드의 마지막 방문 경로를 나타낸다
*/
// 2차원 배열 결과
result = [
[1, 2], // 0번 노드는 1번, 2번과 연결됨
[0, 4, 4], // 1번 노드는 0번, 4번(중복)과 연결됨
[0, 3, 3], // 2번 노드는 0번, 3번(중복)과 연결됨
[2, 2], // 3번 노드는 2번(중복)과 연결됨
[1, 1] // 4번 노드는 1번(중복)과 연결됨
]
/* 반면 2차원 배열은 덮어쓰기 없이 연결된 모든 노드 관계를 표현한다.
result[0] = 1,2 0번 노드가 1,2와 연결
중복 값을 없애기 위한 추가 로직이 필요할 수 있다.
*/인접 리스트 변환이 필요한 상황은 다양하다. 몇 가지 예시로 인접 리스트로 변환이 필요한 데이터를 보면,
// 두 변수는 노드 전체 갯수와 연결 관계를 표현한다.
const numCourses = 4;
const prerequisites = [[1, 0], [2, 1], [3, 2]];
// 0 루트 -> 1 -> 2 -> 3
// 두 변수에 각각 저장된 노드 저장값과 엣지로 리스트를 만드는 경우
const nodeValues = [5, 6, 4, 3, 0]; // 노드의 저장값
const edges = [ // 노드의 연결
[1, 2],
[0, 4],
[0, 3],
[2],
[1]
];
// ex: 위의 list2D와 동일한 그래프이지만, 노드에 추가적인 저장값이 있을 때
const list2D = [
[5 ,1, 2], // 0번 노드는 5라는 값이 저장되고 1, 2와 연결된다
[6, 0, 4], // 1번 노드는 저장값 6, 엣지는 0, 4
[4, 0, 3], // 2번은 값 4, 엣지 0,3
[3, 2], // 3은 값 3, 엣지 2
[0, 1] // 4는 값 0, 엣지 1
];
// 혹은 엣지에 가중치가 포함된 리스트
const weightedList = [
[[1, 4], [2, 1]], // 0번 노드는 1와 4 가중치로 연결, 2와는 1 가중치로 연결
[[0, 4], [3, 2]], // 1 노드는 0과 4로, 3과 2으로
[[0, 1], [3, 3]], // 2 노드는 0과 1로, 3과 3으로
[[1, 2], [2, 3]] // 3 노드는 1과 2로, 2와 3으로
];ㄱ
// 임의의 문자 배열을 리스트로 나타낼 때
const alienWords = ["wrt", "wrf", "er", "ett", "rftt"];
// 배열 값을 조건에 따라 정렬하고 새로운 데이터 구조로 변환을 요구한다. 모든 변환의 가능성을 익히는 것은 불가능하다. 사실 가장 중요한 점은 대부분의 문제가 그래프 설계와 함께 탐색 알고리즘을 요구한다.
이전 해시 글에서 알게된 내용이 떠오른다. 해시를 사용한다고 문제가 바로 풀리는 것이 아니다. 해시를 어떻게 설계하는 가가 관건이었다. 구체적으로 데이터가 키-값으로 저장되는 시점부터 탐색이 가능한 저장 구조를 다뤘다. 그래프도 똑같다. 그래프를 만들고 탐색을 해야한다. 그래프를 만들 때, 탐색이 효율적으로 이루어지게 만들어야 한다.
프론트 개발에서 그래프
JS 기반의 프론트엔드에서 그래프는 자주 사용된다. Web API인 document 객체, DOM 트리, 상태 관리 등이 있다.
HTML 문서와 DOM 트리 (관련 글)
모듈의 의존성 그래프
상태 그래프 (ex 리액트 상태, Props 의존성, 전역상태 등)
라우팅 그래프 (ex 라우팅 경로 (? 맞나))
// 리액트 엘리먼트는 객체로 표현된 연결 리스트이다.
// children에서 자식 노드의 연결 관계를 나타낸다.
const ReactElement = {
type: "App",
children: [
{ type: "Header", children: [] },
{ type: "Main", children: [
{ type: "Sidebar", children: [] },
{ type: "Content", children: [] }
]
},
{ type: "Footer", children: [] } ] };
]
};
// JS document 객체는 브라우저가 생성한 DOM 트리를 탐색, 변경하는 DOM API이다. // 각 노드는 부모-자식 관계로 연결된다.
// console.dir(document)
/*
#Document
URL: "https://example.com"
documentElement: html
head: head
body: body
title: "Example"
cookie: ""
location: Location {...} ...
*/
// console.log(document)
/*
<html>
<head>
<body>
<header>
<main>
<footer>
*/다음 글은 그래프 탐색이다.