그래프

• 핵심 용어
  
  • 노드와 에지로 구성된 집합이다
  • 노드는 데이터를 표현하는 단위이고 에지는 노드를 연결한다
• 종류
  • 유니온 파인드
    • 그래프의 사이클이 생성되는지 판별하는 알고리즘
  • 위상정렬
    • 사이클이 없는, 방향이 있는 그래프를 선형으로 정렬하는 알고리즘
    • 값이 유일하지 않다는 특징이 있다
  • 다익스트라
    • 시작점이 존재하며 시작점에서 다른 모든 노드를 통과하는 최단거리 알고리즘이다(음수간선이 존재하면 안된다)
  • 벨만포드
    • 다익스트라와 같으나 음수간선이 존재해도 되는 최단거리 알고리즘이다
    • 음수 싸이클이 있는지 확인하는 문제로도 많이 나온다
  • 플로이드 워셜
    • 모든 노드에 대해서 최단거리를 구하는 알고리즘으로 다익스트라와 벨만포드에 비해 시간복잡도가 안좋다
  • 최소 신장 트리
    • 모든 노드를 연결하는데 간선의 가중치를 최소로 구하는 알고리즘
    • 트리는 사이클이 존재하면 안되므로 유니온 파인드 알고리즘을 이용하여 사이클이 없애야 한다