자료구조 - 그래프

해당 내용은 프로그래머스 코딩테스트 광탈 방지 A to Z : JavaScript 강의를 공부하며 정리한 내용입니다.

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

실무사용 예시

• 지하철 노선도
• 페이지랭크
  https://ko.wikipedia.org/wiki/%ED%8E%98%EC%9D%B4%EC%A7%80%EB%9E%AD%ED%81%AC

2-1 그래프의 특징

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

2-2 그래프 종류

방향의 유무

• 무방향 그래프
  간선으로 이어진 정점끼리는 양방향으로 이동이 가능
  표현하기에 (A, B)와 (B, A)는 같은 간선으로 취급
  ex) 양방향 통행 도로
  

• 방향 그래프
  간선에 방향성이 존재하는 그래프
  양방향으로 갈 수 있더라도 (A, B)와 (B, A)는 다른 간선으로 취급
  ex) 일방 통행

연결 상태에따라

• 연결 그래프
  모든 정점이 서로 이동 가능한 상태인 그래프

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

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

한 노드(정점)의 간선 수 = (모든 노드의 수 -1)
모든 노드의 수 = 한 노드의 간선수 +1

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

3. 코테
   핵심 키워드 :
   대표문제