Graph

그래프(Graph)란?

그래프는 정점(Vertice)과 간선(Edge)으로 구성된 비선형 데이터 구조이다.

그래프

 

 

정점(Vertice): 노드(node)라고도 하며 정점에는 데이터가 저장된다. (위의 그림에서 0, 1, 2, 3, 4, )
간선(Edge): 노드간을 연결하는 선이며 노드간의 관계를 나타낸다.

 

그래프와 트리의 차이

트리는 그래프의 한 종류이다. 하지만 서로 차이점이 존재한다. 아래 그림에서 자세히 설명한다.

 

그래프의 구현 방법

그래프의 구현 방법에는 일반적으로 인접행렬(Adjacency Matrix), 인접목록(Adjacency List) 두 가지가 있다.

근접 행렬(Incidence Matrix), 인접리스트(Incidence List) 방식도 있지만 본 글에서는 인접행렬과 인접목록 구현 방법에 대해서만 서술한다.

 

인접 행렬(Adjacency Matrix)

인접 행렬은 V x V (V는 그래프의 정점 수) 크기의 이차원 배열이다. 이차원 배열을 adj[][]라고 하고 adj[i][j]가 1인 부분은 정점 i에서 정점 j까지의 간선이 있음을 나타낸다. 무방향 그래프의 인접 행렬은 항상 대칭이다.

아래 그림은 위 그래프 그림에 대한 인접 행렬이다.

위 그래프에 대한 인접 행렬

장점: 그래프를 구현하기 더 쉽다. 가장자리를 제거하는 데 O(1)의 시간이 걸린다.

단점: 더 많은 공간을 차지한다. 그래프의 간선 수가 적더라도 정점 X 정점 수 만큼의 공간을 사용한다.

 

Javascript로 인접행렬을 통한 그래프 구현

// TODO: 구현 코드 작성

 대부분의 경우 인접행렬보다 인접목록을 사용한다. (복잡성 증가 및 메모리 낭비)

 

인접목록(Adjacency List)

인접목록을 구현하는데 배열을 사용한다. 배열의 크기는 정점의 수와 같다. 배열을 array[]로 설정한다. array[i]는 i번째 정점 에 인접한 정점 목록을 나타낸다. 아래 그림은 위 그래프 그림에 대한 인접 목록이다.

위 그래프에 대한 인접목록

 

Javascript로 인접목록을 통한 그래프 구현

/**
 * 인접 목록
 */

/**
 * edge 를 무방향 그래프에 추가하는 함수
 *  
 * @param adj
 * @param u
 * @param v
 */
function addEdge(adj,u,v) {
    adj[u].push(v);
    adj[v].push(u);
}

// 인접 목록을 log에 찍어주는 함수
function printGraph(adj) {
    for (let i = 0; i < adj.length; i++) {
        console.log(`인접목록의 정점(v) ${i}`);
        console.log("head");
        for (let j = 0; j < adj[i].length; j++) {
            console.log(` -> ${adj[i][j]}`);
        }
        console.log(" ------------------- ");
    }
}

// 5개의 정점이 있는 그래프 생성
let V = 5;
let adj= [];

for (let i = 0; i < V; i++) {
    adj.push([]);
}
// adj: [ [], [], [], [], [] ]

// edge를 추가
addEdge(adj, 0, 1); // adj: [ [ 1 ], [ 0 ], [], [], [] ]
addEdge(adj, 0, 4); // adj: [ [ 1, 4 ], [ 0 ], [], [], [ 0 ] ]
addEdge(adj, 1, 2); // adj: [ [ 1, 4 ], [ 0, 2 ], [ 1 ], [], [ 0 ] ]
addEdge(adj, 1, 3); // ...
console.log(adj)
addEdge(adj, 1, 4); // ...
addEdge(adj, 2, 3); // ...
addEdge(adj, 3, 4); // ...
// adj: [ [ 1, 4 ], [ 0, 2, 3, 4 ], [ 1, 3 ], [ 1, 2, 4 ], [ 0, 1, 3 ] ]
/**
 * head는 정점을 의미한다.
 *
 * 인접목록의 정점(v) 0
 * head -> 1 -> 4
 *  -------------------
 * 인접목록의 정점(v) 1
 * head -> 0 -> 2 -> 3 -> 4
 * -------------------
 * 인접목록의 정점(v) 2
 * head -> 1 -> 3
 * -------------------
 * 인접목록의 정점(v) 3
 * head -> 1 -> 2 -> 4
 * -------------------
 * 인접목록의 정점(v) 4
 * head -> 0 -> 1 -> 3
 * -------------------
 */
printGraph(adj);


/**
 * 또는
 */


const adjacencyList = new Map();
adjacencyList.set(0, [1,4]);
adjacencyList.set(1, [0,4,2,3]);
adjacencyList.set(2, [1,3]);
adjacencyList.set(3, [1,4,2]);
adjacencyList.set(4, [3,0,1]);

/**
 * Map(5) {
 *   0 => [ 1, 4 ],
 *   1 => [ 0, 4, 2, 3 ],
 *   2 => [ 1, 3 ],
 *   3 => [ 1, 4, 2 ],
 *   4 => [ 3, 0, 1 ]
 * }
 */
console.log(adjacencyList);

 

사용된 전체 코드

https://github.com/rkdden/Data-Structure/blob/main/graph.js

GitHub - rkdden/Data-Structure

 

출처

https://www.geeksforgeeks.org/graph-and-its-representations/?ref=lbp 

Graph and its representations - GeeksforGeeks