자료구조와 알고리즘 - 그래프

본 내용은 프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 토대로 작성하였습니다.

1. 그래프란?

• 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조
  • 정점(Node) 집합과 간선(Edge) 집합으로 표현

특징

• 여러개의 간선을 가질 수 있음
• 방향 그래프, 무방향 그래프로 나눌 수 있음
• 간선은 가중치를 가짐
• 사이클이 발생 가능

2. 그래프의 종류

무방향 그래프

• 간선으로 이어진 정점끼리는 양방향으로 이동이 가능
• (A, B), (B, A)는 같은 간선 취급

방향 그래프

• 간선에 방향성이 존재하는 그래프
• <A, B>, <B, A>는 다른 간선으로 취급

연결 그래프

• 모든 정점이 서로 이동 가능한 상태인 그래프
• 특정 정점 -> 다른 정점까지의 모든 경우의 수가 이동 가능해야 함

비연결 그래프

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

완전 그래프

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

사이클

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

3. 그래프의 구현 방법

• 인접행렬, 인접 리스트 두 가지 방식으로 그래프를 표현
• 인접행렬
  • 2차원 배열 이용
• 인접 리스트
  • 연결 리스트 이용

Reference

프로그래머스의 코딩테스트 광탈 방지 A to Z : JavaScript