[자료구조 공부] 자바스크립트 그래프 #7

☘️ 그래프

그래프 정의

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조

그래프에서 정점은 Node, 간선은 Edge 라고 불리며,

아래 사진에서 파란색 원이 정점(node), 검은색 선이 간선(edge) 이다.

 

 

그래프 사용 예시

이러한 그래프가 사용되는 예시로는 지하철 노선로가 있다.

지하철역이 정점(node), 지하철역과 역 사이를 이어주는 것이 간선(edge) 이라고 할 수 있다.

 

그래프 특징

1. 다수의 간선

그래프는 비선형 구조라서 정점이 여러 개의 간선을 가질 수 있다.

비선형 구조
하나의 데이터에 여러 개의 데이터가 존재할 수 있고, 데이터 간 1:n 또는 n:n 관계를 가짐

 

2. 방향, 무방향 그래프

그래프는 방향이 있는 방향 그래프와, 방향이 없는 무방향 그래프가 있다.

 

3 . 가중치

그래프에서 간선은 가중치를 가질 수 있다.

 

4. 사이클 발생

그래프는 탐색할 때, 계속 루프가 도는 사이클이 존재하여 무한루프에 빠지지 않게 유의해야 한다.

 

☘️ 그래프 종류

방향 상태

그래프 간선에 방향의 유무에 따라 방향 그래프, 무방향 그래프로 나뉜다.

무방향 그래프
간선에 방향이 없어 간선으로 이어진 정점끼리 양방향으로 이동 가능
(A,B) 와 (B,A) 는 같은 간선

방향 그래프
간선에 방향성이 존재
양방향으로 이동 가능해도 <A,B> 와 <B,A> 는 다른 간선

 

연결 상태 (연결, 비연결, 완전)

그래프는 정점간의 연결 상태에 따라 연결 그래프, 비연결 그래프, 완전 그래프로 나뉜다.

연결 그래프
모든 정점이 서로 이동 가능한 상태
특정 정점에서 특정 정점으로 이동 가능

비연결 그래프
특정 정점 사이에 간선이 존재하지 않아 이동하지 못하는 정점이 있는 그래프

완전 그래프
모든 정점끼리 연결된 그래프
한 정점의 간선 수 = 모든 정점의 수 - 1

 

☘️ 그래프 구현

그래프를 구현하는 방법에는 인접 행렬, 인접 리스트 2가지 방법이 있다.

인접 행렬

방향 그래프

인접 행렬은 정점의 개수만큼 2차원 배열을 만든다.

그래서 정점끼리 연결이 안 된 상태인 false에서 연결하고 싶은 정점끼리 값을 true로 수정해준다.

const myGraph = Array.from(Array(5), () => {
  return Array(5).fill(false);
});

myGraph[0][1] = true; // 0번 정점 -> 1번 정점
myGraph[0][3] = true; // 0번 정점 -> 3번 정점
myGraph[1][2] = true; // 1번 정점 -> 2번 정점
myGraph[2][0] = true; // 2번 정점 -> 0번 정점
myGraph[2][4] = true; // 2번 정점 -> 4번 정점
myGraph[3][2] = true; // 3번 정점 -> 2번 정점
myGraph[4][0] = true; // 4번 정점 -> 0번 정점

 

 

무방향 그래프

무방향 그래프는 대칭으로 정점을 연결시켜 줘야 한다.

그리고 그래프에 가중치 값을 넣고 싶으면 true, false 대신 임의의 값 넣어도 된다.

const myGraph = Array.from(Array(5), () => {
  return Array(5).fill(null);
});

myGraph[0][1] = 3; // 0번 정점 -> 1번 정점
myGraph[1][0] = 3; // 1번 정점 -> 0번 정점

myGraph[0][3] = 6; // 0번 정점 -> 3번 정점
myGraph[3][0] = 6; // 3번 정점 -> 0번 정점

myGraph[1][2] = 5; // 1번 정점 -> 2번 정점
myGraph[2][1] = 5; // 2번 정점 -> 1번 정점

myGraph[3][2] = 1; // 3번 정점 -> 2번 정점
myGraph[2][3] = 1; // 2번 정점 -> 3번 정점

myGraph[4][0] = 7; // 4번 정점 -> 0번 정점
myGraph[0][4] = 7; // 0번 정점 -> 4번 정점

 

인접 리스트

인접 리스트는 배열을 사용하여 값을 넣는 형태이다.

 

정점의 개수만큼 빈 배열을 만들고 그 배열을 다시 배열에 감싸준다.

그리고 각 정점과 연결할 정점을 추가한다.

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

myGraph[0].push(1); // 0번 정점 -> 1번 정점
myGraph[0].push(3); // 0번 정점 -> 3번 정점
myGraph[1].push(2); // 1번 정점 -> 2번 정점
myGraph[2].push(0); // 2번 정점 -> 0번 정점
myGraph[2].push(4); // 2번 정점 -> 4번 정점
myGraph[3].push(2); // 3번 정점 -> 2번 정점
myGraph[4].push(0); // 4번 정점 -> 0번 정점

 

인접 리스트에서 가중치를 넣고 싶으면 객체 형태로 연결할 정점과 가중치 값을 입력하고,

무방향 그래프를 만들고 싶으면 위에처럼 대칭으로 연결해주면 된다.

 

---

 

해당 게시물은 프로그래머스 - 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 참고하여 작성한 글입니다. (유료강의)

코딩테스트 광탈 방지 A to Z : JavaScript