Algorithm/그래프 (3) 썸네일형 리스트형 DFS 심화 (1) - Bipartite (이분 그래프) 이분그래프 (Bipartite) 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 설계: Two-colorability i. BFS, DFS로 탐색하면서 정점을 방문할 때마다 두 가지 색 중 하나를 칠한다. ii. 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠한다. iii. 탐색을 진행할 때 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다. 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다. 시간복잡도: $ O(V + E) $ 코드 #include #include #include using namespace std; int V, E; vector adj_list[100]; int colored[1000],.. 최단경로 문제 (2) - ASP (플로이드-와샬) 2. All Pairs Shortest Path 모든 정점에 대해 최단경로를 찾으려면 앞서 살펴본 다익스트라, 벨만포드 알고리즘을 정점의 갯수만큼 반복하면 될 것이다. 그렇다면 시간복잡도는 아래와 같다. Dijkstra: $ O (V \log V + E) \to O (V^2 \log V + VE) \because V \to V^2 \ on \ dense \ graph, \ O(V^3) \because E = V^2 $ Bellman-Ford: $ O (V*E) \to O (V^2 *E) \because V \to V^2 \ on \ dense \ graph, \ O(V^4) \because E = V^2 $ 너무 느린것 같다. 그래서 플로이드와 와샬이란 사람이 새로운 알고리즘을 제시했다. Floyd-Wa.. 최단경로 문제 (1) - SSP (다익스트라, 벨만포드) Shortest Path 최단거리 문제 입력으로 그래프의 정보(간선과 정점의 갯수)와 각 간선의 가중치가 주어질 때, 출발점에서 도착점까지의 가는데 드는 최소비용을 구하는 문제 최단경로의 특성 i. Optimal Substructure를 가지고 있다. (Dynamic Programming) distance(n, m): n에서 m까지의 최단거리이라고 정의한다면 distance(1, 4) = distance(1, 2) + distance(2, 3) + distance(3, 4)로 정의할 수 있다. 증명 만약 각 구간 중 하나라도 구해진 최단경로보다 더 짧은 경로가 존재한다고 가정하자. 그러면 전체 최단경로는 더 짧아질 것이고, 기존에 구했던 최단경로는 더이상 최단경로가 아니게 된다. 이에 모순이 발생하므로 .. 이전 1 다음