[자료구조] 그래프(feat. Javascript)

그래프

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

실제 소프트웨어 사용 사례

1. 지하철 노선도

2. 페이지 랭크

https://ko.wikipedia.org/wiki/%ED%8E%98%EC%9D%B4%EC%A7%80%EB%9E%AD%ED%81%AC

페이지랭크 - 위키백과, 우리 모두의 백과사전

 

 

그래프의 특징

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

 

간선 방향에 따른 그래프 분류

1. 무방향 그래프

- 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다. 표현하기에 (A, B)와 (B, A)는 같은 간선으로 취급된다.

ex) 양방향 통행 도로

무방향 그래프

2. 방향 그래프

- 간선에 방향성이 존재하는 그래프로서, 양방향으로 갈 수 있더라도 <A, B>와 <B, A>는 다른 간선으로 취급된다.

ex) 일방 통행

방향 그래프

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

1. 연결 그래프

모든 정점이 서로 이동 가능한 그래프

 

2. 비연결 그래프

특정 정점 쌍 사이에 간선이 존재하지 않는 그래프

ex) 친한 친구 설문 그래프

3. 완전 그래프

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

• 모든 정점끼리 연결되어있기 때문에 한 정점에 연결된 연결점의 수는 전체 정점의 -1과 같다.
• 모든 정점의 수 -1 * 모든 정점 수 = 모든 간선의 개수

4. 사이클

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

그래프의 구현 방법

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

**JavaScript로 표현 방법

1. 인접 행렬

- Graph

- Code

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

- Result

 

2. 인접 리스트

-Graph

- Code

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

- Result