Algorithms/Data Structure & Algorithm (5) 썸네일형 리스트형 강한 연결 요소 - Strongly Connected Component 안녕하세요. 오늘 포스팅할 내용은 강한 연결 요소입니다. 강한 연결요소란 일종의 Cycle인데요. 일반적으로 생각하는 Cycle보다는 조금 더 큰 범위를 다룹니다. 정점 u에서 v로 가는 간선이 존재할때, 임의의 정점 j(v에서 도달가능한)이 u로 가는 간선이 존재하면 이때의 경로 u->v->...->j->u는 강한 연결요소가 됩니다. 강한 연결요소를 찾아서 그래프를 DAG(Directed Acyclic Graph)로 바꿀 수 있습니다. 위상정렬(Topological Sorting)을 통해 주어진 문제를 해결 할 수 있도록 할수도 있고, 각각의 SCC간의 관계에서 정답을 구하는 문제도 있습니다. 자세한 내용은 위키피디아를 참조하세요! https://en.wikipedia.org/wiki/Strongly_.. Ford - Fulkserson 최대 유량 알고리즘 Ford - Fulkerson 알고리즘은 3단계로 이루어져 있습니다. 그래프 순회 알고리즘(DFS/BFS)을 이용해 Augmenting path 찾기 Augmenting path의 V1, V2, V3, ... , Vn 사이에 존재하는 residual capacity의 최소값 찾기. residual capacity의 최소값만큼 Skew Symmetry 성질을 이용해 지나온 path상의 flow 들을 f(u,v)=-f(u,v)해줍니다. 이때 residual capacity는 capacity[u][v] - flow[u][v]이고 u,v 사이의 간선에 흐를 수 있는 유량의 양이라고 생각하면 됩니다. #include #include #include #define INF 999999999 using namespac.. Flow Network - 유량 네트워크 참고자료 wikipedia https://en.wikipedia.org/wiki/Flow_network Flow network - Wikipedia In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a en.wikipedia.org 유량 네트워크가 성립하기 위한 3가지 조건 1 Capacity Constr.. Binary Search 응용하기 https://en.wikipedia.org/wiki/Binary_search_algorithm Binary search algorithm - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Search algorithm finding the position of a target value within a sorted array This article is about searching a finite sorted array. For searching continuous function values, see bisec en.wikipedia.org binary search를 책으로 배우고 실제로 응용할때 bi.. 고급 자료구조 - Disjoint Set Disjoint? 뭘까요? 사전을 찾아보니까 "분리된" 이라는 형용사 입니다. 아하 그럼 disjoint set은 분리된 집합이라는 뜻이겠네요. 집합간의 intersection이 없는것이 disjoint set입니다! disjoint set은 Kruskal MST algorithm과 같이 그래프 상에서 각각의 정점이 연결되었는지를 검사할때 요긴하게 사용됩니다. Minimum Spanning Tree는 Tree인 만큼 Cycle이 형성되면 안되는데요. 이 Cycle 찾기위해 인접한 정점을 일일이 찾는다면 상당히 복잡해집니다. 이럴때 사용하는 것이 Disjoint Set! disjoint set을 활용하면 그래프 상에서 각각의 정점이 서로 붙어있는지(Cycle을 형성하는지) 알 수 있습니다. 먼저 자료구조니.. 이전 1 다음
