Graph

그래프는 노드와 에지로 구성된 집합.

노드 - 데이터를 표현하는 단위

에지 - 노드를 연결

사용 알고리즘

• 유니온 파인드
  • 그래프의 사이클이 생성되는지 판별하는 알고리즘
• 위상 정렬
  • 방향 그래프 에서 선행 작업이 완료된 후에 다음 작업을 수행해야 하는 경우의 순서를 정하는 알고리즘 Ex) 과목 선수 과목 순서
  • 그래프의 각 노도들을 선형으로 정렬하는것
  • 값이 유일하지 않다는 특징이 있다.
  • 사이클이 없는 방향 그래프 에서만 사용이 가능하다.
• 다익스트라
  • 최단거리 알고리즘
  • 음수 간선 X
• 벨만 - 포드
  • 최단거리 알고리즘
  • 음수 간선 O
• 플로이드 - 워셜
  • 최단거리 알고리즘
  • 시작점이 없다.

이 외의 길찾기 알고리즘

• 최소 신장 트리 (MST)

  • 모든 노드를 연결할때 최소 가중치로 연결하는 알고리즘