그래프

그래프란?

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.
정점 집합과 간선 집합으로 표현할 수 있으며, 주로 인물관계도나 지하철 노선도, 페이지 랭크 등에 사용된다.

특징

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

간선의 방향성에 따른 분류

방향 그래프

간선에 방향이 존재하는 그래프로, <A,B>와 <B,A>는 다른 간선이다.

무방향 그래프

간선으로 이어진 정점끼리는 양방향으로 이동이 가능하며, (A,B)와 (B,A)는 같은 간선으로 취급한다.

그래프의 연결 상태에 따른 분류

연결 그래프

모든 정점으로 이동 가능한 상태인 그래프이다.

비연결 그래프

특정 정점으로 가는 간선이 존재하지 않는 그래프

완전 그래프

모든 정점끼리 연결된 상태인 그래프

사이클

그래프의 정점과 간선의 부분 집합에서 순환되는 부분을 가지는 그래프

Javascript 에서의 구현

주로 인접 행렬 방식이나 인접 리스트 방식으로 구현한다.

// 노드가 5일경우

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

console.log(graph);

//인접리스트 방식
const graph2 = Array.from(Array(5), () => []);

graph2[0].push(3);
graph2[1].push(5);

console.log(graph2);