Sean :: Dev

Network/Maximum Flow 유량그래프 : 간선의 weight가 정점에서 정점으로 보낼수있는 최대유량을 의미하는 그래프 최대유량 : 해당 간선을 통해 동시에 흘려보낼수있는 물의 최대치 이러한 유량그래프에서, Source정점에서 Sink정점까지 최대 얼마만큼의 유량이 지나갈수있는지에 관한 문제를 Network/Maximum Flow라고 한다. 아래와 같이, 수로(간선)에 1초마다 지날수있는 물의 최대치가 정의되어있다면, 수로는 자신의 용량이상의 물은 통과 시킬수없다. 따라서 결과적으로 통과할수있는 물의 최대량은 왼쪽은 2, 오른쪽은 4이다. 따라서 위의 그래프를 Maximum Flow(최대유량)으로 보내면 그 값은 7이다. 좌측값은 실제로 해당 간선에 흐른 유량(flow), 우측값은 해당 간선의 ..

Dijkstra Algorithm 그래프의 한 노드에서 다른 노드로 가는 최단거리를 구하는 알고리즘 (만약 모든 노드 쌍간의 최단거리를 구할땐, n개의 각 정점에 대해 Dijkstra Alg를 여러번 수행해야하므로, 이때는 Floyd-Warshall Alg이 더 유리하다) 동작과정은 BFS와 비슷하지만, Queue가 아닌 Priority Queue를 이용한다. 시간복잡도=O(ElogE) 해당노드까지의 최단거리를 저장할 distance[] 배열 준비후, 미방문을 의미하는 -1로 초기화한다. 노드1에서 시작한다면, 이때까지 자기자신 1까지의 거리는 0이므로 distance[1]에 0을, pq에 (1,0)을 넣는다. 2의10보다 가깝다. distance[2]=8로 갱신, pq에도 (2,8) 넣는다. pq엔 (..

MST,MCST (Minimun_Cost Spanning Tree) (최소비용 신장트리) Spanning Tree : undirected graph에서 n개의 모든정점과 n-1개의 간선으로 만들어진 트리 순회(traversal)를 하면 n-1개의 간선을 이동하며 모든 정점을 방문하므로 spanning tree를 생성한다. DFS로 생성되면 DFST(Depth First Spanning Tree, 깊이우선 신장트리), BFS로 생성되면 BFST(Breadth First Spanning Tree, 너비우선 신장트리)라고 한다. weighted undirected graph에서 모든 노드를 포함하고 cycle이 없으며 weight의 합이 최소인 트리를 MST or MCST(Minimum Cost Spannin..

DFS (Depth First Search) (깊이 우선 탐색) LIFO(Last-In First-Out), Stack 활용 PseudoCode recursive non-recursive 1 non-recursive 2 예제 Input Output 첫 줄에 정점의 개수 N과 간선의 개수 M이 주어집니다. 다음 M줄에 간선의 관계 시작정점 u와 도착정점 v가 주어집니다. 입력에 따른 깊이 우선 탐색 결과를 출력합니다. import java.util.*; public class Test { static boolean edge[][]; static boolean visited[]; static int n; static int m; public static void main(String args[]) { Sca..

Graph (그래프) Traversal / Search (순회,탐색) DFS(Depth First Search) 깊이우선탐색 BFS(Breadth First Search) 너비우선탐색 Spanning Tree (신장트리) DFST(Depth First Spanning Tree) 깊이우선 신장트리 BFST(Breadth First Spanning Tree) 너비우선 신장트리 MST,MCST(Minimum_Cost Spanning Tree) 최소_비용 신장트리 : Kruskal, Prim 's Alg Distance (최단거리 등) Dijkstra 's Alg Floyd-Warshall 's Alg Bellman-Ford 's Alg Etc Network Flow Bipartit..