Graph

DSU, Dijkstra, Bellman-Ford, Floyd-Warshall, etc..

그래프란?

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

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

• 에지 : 노드를 연결하는 선

또 다르게 설명하면

자료 구조로써 그래프는 = 정점(vertex) + 간선(edge)이다.

• 간선 : 정점과 정점을 이어주는 선

  • 간선 무방향, 간선 방향, 간선 무방향/방향 + 가중치가 존재한다.

정점과 차수의 성질

정점 x의 차수 : 정점 x에 연결된 간선의 수

• 성질 : 모든 정점 차수의 합 = 간선의 개수 * 2

---

그래프 알고리즘

• 유니온 파인드 : 집합에서 대표 노드 찾기, 하나의 노드로 만들기

  • 그래프에서는 그래프의 사이클이 생성되는지 판별하는 알고리즘 -> 🌟사이클의 유무 판단

• 다익스트라 : 최단거리

  • 시작점 고정, 다른 모든 노드를 가는 최단거리 구하는 알고리즘

  • 단, 음수 간선은 존재하지 않는다.

• 플로이드-워셜 : 최단거리

  • 시작점이 없다. 모든 노드에 대해 최단거리 구하기

  • 시간 복잡도 : O(N^3). 효율이 좋지 않다.