School

Data Structure - Graph ( Floyd-Warshall Algorithm && Transitive Closure )

Floyd-Warshall Algorithm 플로이드-워셜 알고리즘이란 모든 최단 경로를 구하는 알고리즘으로서 정점을 기준으로 하는 알고리즘을 말합니다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이였다면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다. 모든 노드 간의 최단거리를 구해야 하므로 2차원 adjacent matrix를 구성합니다. 알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 증간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복해야 합니다. 이를 간단한 코드로 짜보면 다음과 같을 수 있겠습니다. ... for(int k = 0; i < n; k++) { for..

Data Structure - Graph ( Dijkstra && Bellman and Ford Algorithm )

Shortest Paths Path finding system은 그래프를 이용하는 시스템을 말합니다. Single Source / All Destinations : Nonnegative Edge Costs directed graph G=(V, E)에서 weighting function w(e)에서 source vertex v0을 바탕으로 a shortest path를 찾는 과정을 말합니다. 여기서 중요한 점은 w(e) > 0입니다. negative을 찾는 방법은 아래에서 다룹니다. 예를 들면 다음과 같습니다. v0에서 v1로 갈 수 있는 a shortest path는v0 -> v3 -> v4 -> v1이 됩니다. v0 -> v3이 아니라요. 이러한 a shortest path를 찾는 알고리즘을 소개합니다..

Data Structure - Graph ( MST )

Minimum Spanning Trees MST에서의 cost는 weighted undirected graph에서 sum of costs ( weights )를 말합니다. 또한 MST는 cost가 최소인 spanning tree를 말하게 됩니다. MST를 찾기 위해서는 3개의 알고리즘이 있습니다. Kruskal's, Prim's Sollin's algorithm이 있는데, 모드 greedy method에 기반되어 있습니다. MST에서의 제약조건을 말씀드리겠습니다. 여기에서는 우리는 무조건 edge를 사용해야 합니다. 또한 우리는 정확히 n-1 edge를 MST를 그리는데 사용해야 합니다. 우리는 cycle을 가지는 edge를 만들어 내면 안됩니다. Kruskal's Algorithm 신장 트리(Spann..

Data Structure - Graph ( Biconnected Components )

Biconnected Components articulation point란 G의 vertex v를 deletion했을 떄, 최소한 2개의 컴포넌트로 쪼개지면 이때의 vertex를 articulation point라고 한다. 이 떄 biconnected graph란 연결그래프인데 articulation point가 없는 그래프를 말합니다. 많은 그래프에서 articulation points는 탐탁치 않습니다. biconnected component는 maximal biconnected subgraph of G입니다. 즉 2개의 biconnected component에서 한개 보다 많은 공통된 vertex를 가질 수는 없습니다. 또한 biconnected component에서 하나의 edge는 2개가 들어..