[TIL 5] 그래프(Graph) in JS

그래프(graph)

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.
지하철 노선도, 페이지 랭크 알고리즘이 대표적으로 그래프를 사용하는 구조이다.

그래프의 특징

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

그래프는 2가지 특성에 따라 분류될 수 있다.😊

방향에 따라

무방향 그래프

• 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.
• 따라서 a -> b / b -> a 를 같은 정점으로 취급한다.

방향 그래프

• 간선 방향이 정해져 있다.
• 따라서 양방향으로 갈 수 있더라도 a -> b / b -> a는 다른 간선으로 취급된다.

연결 상태에 따라

연결 그래프

• 모든 정점이 연결되어있다.

비연결 그래프

• 어떤 정점과는 연결되어 있지 않다.

완전 그래프

• 모든 정점끼리 연결 상태이다.

그래프의 구현 방법

그래프 역시 인접 행렬, 인접 리스트로 구현할 수 있다. js에서 구현은 굉장히 쉬운 편!

인접 행렬로 구현하기

const graph = Array.from(
	Array(5), 
	() => Array(5).fill(false)
);

graph[0][1] = true;
graph[0][3] = true;
graph[1][2] = true;
graph[4][0] = true;

연결리스트로 구현하기

=> JS는 배열이 고정된 크기가 아닌 무한정 늘어날 수 있기 때문에, 특히 구현하기가 더 간단하다고 할 수 있다.😊👍

const graph = Array.from(
	Array(5), 
	() => []
);

graph[0].push(1);
graph[0].push(3);
graph[1].push(2);
graph[4].push(0);

매우 간편!

이와 관련된 알고리즘에는 BFS, DFS등이 있는데, 추후 추가하겠다.🔥