(TIL Day03-6)자료구조- 그래프

그래프(Graph)

• 정점과 정점 사이를 연결하는 간선으로 이뤄진 비선형 자료구조.
• 정점 집합과 간선 집합으로 표현할 수 있다.
• 지하철 노선도나 인물 관계도를 떠올리면 쉽게 이해할 수 있다.
• 정점은 여러 개의 간선을 가질 수 있다.
• 방향 그래프와 무방향 그래프가 존재.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있다.
• JS에서 인접 행렬, 인접 리스트로 그래프를 표현할 수 있다.

 

무방향 그래프

간선으로 이어진 정점끼리는 양방향으로 이동이 가능.

ex) (A, B) == (B, A)

 

방향 그래프

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

 

코드

// 인접 행렬
const graph = Array.from(Array(5), () => Array(5).fill(false));

graph[0][1] = true; // 0 -> 1
graph[0][2] = true; // 0 -> 2
graph[1][2] = true; // 1 -> 2
graph[2][4] = true; // 2 -> 4
graph[4][3] = true; // 4 -> 3

console.log(graph);

// 인접 리스트
const graph = Array.from(Array(5), () => []);

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

console.log(graph);