그래프 문제 및 최단경로 문제

그래프 문제 특징 => 정점개수, 간선개수 주어짐

정점개수 대비 간선개수가 어느정도인지 가늠 가능
→ 입력으로 들어온 간선수(E)가 최대간선수(V*(V-1)/2)보다 어떤지 봄

• 보통 최대간선수의 절반(1/2)보다 작으면(희소그래프) → 인접리스트가 유리
• 보통 최대간선수의 절반(1/2)보다 크면(밀집그래프) → 인접행렬이 유리

그래프 문제 풀이 과정

1) 그래프가 무향인지 유향인지 봄
2) 무/유향에 따라 정점수를 보고 → 최대간선수를 생각해봄
3) 가중치 있는지 없는지 봄

최단 경로 정의

• 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로

가중치 여부에 따른 그래프 최단 경로

• 가중치가 없는 그래프의 최단경로 => 간선수 최소여야!! => 무조건 BFS
  • 거쳐가는 너비(길이)의 수가 최단이어야 함. 방문순서 Queue로 관리 (너비순 관리)
  • DFS는 비효율적임
• 가중치가 있는 그래프의 최단경로 => 가중치합 최소여야!!
  • 하나의 시작 정점(출발지)에서 끝 정점(도착지)까지의 최단 경로
    • 양의 가중치 => 다익스트라(Dijkstra) 알고리즘
      • BFS로 구현한다면 방문관리 다르게 해야함
        • BFS + PQ → Dijkstra
          • 재방문 가능하게 구현(true/false x) ⇒ 그곳을 먼저 방문했을때 비용
          • 원래 거기 있던애보다 비용 커지면 가지 x
      • DFS로도 가능하긴 함
    • 양&음의 가중치 => 벨만-포드(Bellman-Ford) 알고리즘
  • 모든 정점들(모든 쌍)에 대한 최단 경로
    • 양&음의 가중치 => 플로이드 워샬(Floyd-Washall) 알고리즘