자료구조 / 그래프

Jihoo·2023년 3월 30일

그래프

Algorithm

목록 보기

15/16

출제 빈도가 가장 높은 그래프 탐색을 복습해보자.😎

그래프

정의

객체들 간의 관계를 표현하기 위한 자료구조

객체 -> 노드
객체들 간의 관계 -> 간선

종류

유향 그래프: 간선의 방향성이 있는 그래프
무향 그래프: 간선의 방향성이 없는 그래프
가중치 그래프: 간선에 가중치가 있는 그래프

구현 방식

인접행렬
인접리스트

인접행렬

노드의 개수가 적을 때

모든 노드를 행과 열로 표현
두 노드가 연결되었으면 1, 그렇지 않으면 0
공간 복잡도: O(V*V)
특정 간선 확인: O(1)
if (graph[i][j] = 1) connected

// JavaScript
// arr = [[node1, node2], [node1, node2], ...]

let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
for (let [a, b] of arr) {
  graph[a][b] = 1;
}

인접리스트

간선의 개수가 적을 때

각 노드는 연결된 노드 리스트를 가짐
공간 복잡도: O(V+E)
특정 간선 확인: O(degree of V)

// JavaScript
// arr = [[node1, node2], [node1, node2], ...]

let graph = Array.from(Array(n + 1), () => Array(0);
for (let [a, b] of arr) {
  graph[a].push(b);
}