그래프(Graph)

그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 입니다.
정점 집합과 간선 집합으로 표현 가능합니다.

특징

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

방향에 따른 분류

무방향 그래프

간선으로 이어진 정점끼리 서로 이동이 가능합니다.
즉, A기준으로 (A,B)와 B기준으로 (B,A)는 같은 간선입니다.

방향 그래프

간선에 방향성이 존재하고 간선이 서로 다른 방향이면 양방향 이동이 가능합니다.
하지만, (A,B)와 (B,A)는 다른 간선으로 취급됩니다.

연결 상태에 따른 분류

연결 그래프

모든 정점이 서로 이동 가능해야합니다.
특정 정점에서 또다른 정점까지 모든 경우의 수중에 이동 가능해야합니다.

비연결 그래프

특정 정점에 간선이 존재하지 않는 그래프입니다.

완전 그래프

모든 정점끼리 연결된 상태인 그래프로 다음과 같은 공식이 성립됩니다.

한 정점의 간선수 = 모든 정점 - 1
모든 정점 - 1 x 정점 수 = 모든 간선수

사이클

그래프의 정점과 간서의 부분 집합에서 훈환이 되는 부분입니다.

구현 방법

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

• 인접 행렬: 2차원 배열 사용
• 인접 리스트: 연결 리스트 사용

  

인접 행렬

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