그래프

🌱 그래프의 정의

노드와 에지로 구성된 집합

• 노드 : 데이터를 표현하는 단위
• 에지 : 노드를 연결

🌱 그래프 알고리즘 종류

• 유니온 파인드 : 그래프의 사이클이 생성되는지 판별하는 알고리즘
  
  

• 위상 정렬 : 사이클이 없고, 방향이 있는 그래프. 노드를 정렬하는 알고리즘. 정렬 결과가 꼭 1개는 아니다(EX. 수강신청)
  
  

• 다익스트라, 벨만-포드, 플로이드-워셜: 최단거리 알고리즘
  - 다익스트라 : 시작점이 있고 다른 모든 노드로 가는 최단거리를 구하는 알고리즘. 음수 간선이 있으면 안됨.

  • 벨만 포드 : 시작점이 있고 다른 모든 노드로 가는 최단거리를 구하는 알고리즘. 음수 간선이 있어도 됨. 음수 사이클이 있는지 판별하는 코딩테스트 문제가 많이 나온다.

  • 플로이드- 워셜: 시작점이 없음. 모든 노드에 대해서 최단거리를 구한다.

    
    

• 최소 신장 트리(MST) : 모든 노드를 연결하는데 드는 최소의 비용 구하기. 사이클이 있으면 안된다.(이를 파악하기 위해서는 유니온 파인드가 필요하다)