자료구조&알고리즘_그래프

Woogie·2022년 10월 21일
0

그래프 (Graph)

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

[사진출처]
https://velog.io/@gimtommang11/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EA%B7%B8%EB%9E%98%ED%94%84

용어

  • 정점(Node/Vertice) : 그래프를 형성하는 노드
  • 간선(Edge/arcs) : 정점 간에 선 (노드 간의 연결)
  • 정점 차수 : 해당 정점에 연결된 간선의 개수
  • 가중치 : 간선에 대한 값. 문맥에 따라 다양한 것을 나타낼 수 있음

그래프의 특징

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

그래프의 종류

무방향 그래프

간선으로 이어진 정점끼리는 양방향으로 이동이 가능
(1,2)와 (2,1)은 같은 간선으로 취급
ex) 양방향 통행 도로

방향 그래프

간선에 방향성이 존재
만약 양방향으로 갈 수 있다고 해도 (1,2)와 (2,1)은 다른 간선으로 취급
ex) 일방통행 도로

그래프의 종류(2)

비연결 그래프

노드들 중, 간선에 의해 연결되어있지 않은 노드가 있는 그래프

연결 그래프

모든 정점이 서로 이동 가능한 상태인 그래프
(무방향 그래프와 그림이 같음)

완전 그래프

모든 정점끼리 연결된 상태인 그래프
한 정점의 간선 수 = (모든 정점 수 - 1)
모든 간선의 수 = (모든 정점 수 - 1) * 정점 수

사이클

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

그래프의 구현 방법

인접 행렬

2차원 배열로 표현

const graph = Array.from(
  Array(5), () => Array(5).fill(false)
);
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[3].push(2);	// 3 -> 2
graph[4].push(0);	// 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[3].push(2);	// 3 -> 2
graph[4].push(0);	// 4 -> 0

그래프 관련 문제
가장 먼 노드

출처

프로그래머스 데브코스 교육 내용을 바탕으로 정리한 글 입니다.

프로그래머스 데브코스
sue님 velog

profile
FrontEnd Developer

0개의 댓글