[자료구조] 그래프(Graph)

Graph (그래프)

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
정점 집합과 간선 집합으로 표현할 수 있다.

그래프의 특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다.

그래프 용어

• 정점(vertex & node) : 데이터를 저장하는 위치
• 간선(Edge) : 정점(노드)를 연결하는 선
• 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점을 의미한다.
• 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우를 의미한다.
• 차수(degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 의미한다.
• 진출 차수(in-degree) : 방향 그래프에서 외부로 향하는 간선의 수를 의미한다.
• 진입 차수(out-degree) : 방향 그래프에서 외부에서 들어오는 간선의 수를 의미한다.
• 경로 길이(path length) : 경로를 구성하는데 사용된 간성의 수를 의미한다.
• 사이클(cycle) : 단순 경로 중에서 시작 정점과 종료 정점이 동일한 경우

그래프의 종류

무방향 그래프

무방향 그래프는 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다. 표현하기에 (A,B)와 (B,A)는 같은 간선으로 취급된다.

ex ) 양방향 통행 도로

방향 그래프

방향 그래프는 두 정점을 연결하는 간선에 방향이 있는 그래프이다. 간선이 가리키는 방향을만 이동할 수 있다.

가중치 그래프

가중치 그래프는 간선에 가중치(조건 & 비용)가 할당된 그래프이다. 두 정점을 이동할 때 (조건 & 비용)이 있는 그래프이다.

연결 그래프

연결 그래프는 노드들이 하나도 빠짐없이 간성에 의해 연결되어 있는 그래프이다.

완전 그래프

완전 그래프는 그래프의 모든 정점이 서로 연결되어 있는 그래프이다.

그래프 구현 방법

인접 행렬, 인접 리스트 두 가지 방식으로 그래프를 표현할 수 있다.

인접행렬

// 인접 행렬
const graph = Array.from(Array(5), () => Array(5).fill(false));
graph[0][1] = true; // 0 -> 1
graph[0][3] = true; // 0 -> 3
graph[1][2] = true; // 1 -> 2
graph[2][0] = true; // 2 -> 0
graph[2][4] = true; // 2 -> 4
graph[3][2] = true; // 3 -> 2
graph[4][0] = true; // 4 -> 0

인접 리스트

const graph = Array.from(Array(5), ()=>[]);
graph[0].push(1); // 0 -> 1
graph[0].push(3); // 0 -> 3
graph[1].push(2); // 1 -> 2
graph[2].push(0); // 2 -> 0
graph[2].push(4); // 2 -> 4
graph[3].push(2); // 3 -> 2
graph[4].push(0); // 4 -> 0