비선형 자료구조 - 그래프

프로그래머스 '코딩테스트 광탈 방지 A to Z' 강의 내용을 정리해놓은 포스트입니다.

그래프란,

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

특징

1. 정점은 하나 이상의 간선을 가질 수 있으며 선형 구조와는 다르게 앞뒤로 여러개를 가질 수 있다.
2. 방향 / 무방향으로 나눌 수 있다.
   • 무방향: 양방향으로 이동이 가능하다. (a,b) === (b,a)
   • 방향: 한방향으로 이동할 수 있으며 동일한 노드를 오가더라도 동일하다고 볼 수 없다. (a,b) !== (b,a)
3. 간선은 가중치를 가질 수 있다.
4. 특정 위치에서 순환 (사이클)이 발생할 수 있다.

표현 방법

인접 행렬

const graph2 = Array.from(Array(5), () => Array(5).fill(false));
graph2[1][3] = true;

• 정점의 크기만큼 2차 배열을 만든다.
• 연결인 안되게 초기화
• 열부분을 시작, 행부분을 도착 정점으로 두어 true값을 넣으면 연결이 된다.

인접 리스트

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

• 정점의 수만큼 배열 생성
• 연결할 정점을 배열에 추가한다.

참고

• 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript