프로그래밍/Algorithm - 2 (14) 썸네일형 리스트형 6. Maximum Flow & Minimum Cut 1. Mincut & Maxflow problem mincut problem이란 source vertex s, target vertex t를 포함하는 그래프를 s를 포함하는 vertex set A와 t를 포함하는 vertex set B로 분할하였을 때, A->B로 향하는 모든 Edge의 capacity의 합을 최소로 하는 분할을 결정하는 문제이다. maxflow problem이란, 임의의 Edge/Vertex에 대해 아래 조건을 만족하면서 target vertex t로 들어오는 flow를 최대로 만드는 값을 찾는 것이다. 참고로 그래프에서 flow vlaue = inflow at t 이다. - Capacity constraint : 0 t 인 경로이며, 역방향인 backward edge도 선택될 수 있다.. 5. Shortest Paths Shortest path 문제는 edge-weighted digraph가 주어졌을 때, s에서 t로 가는 최단 경로를 찾는 문제이다. 네비게이션, 네트워크 라우팅 등 여러 응용에 쓰인다. 여기서는 하나의 출발지에 대한 모든 다른 지점까지의 shorest-path를 계산하는 single-source shorest paths에 대해 고려할 것이다. 1. APIs Weighted directed edge의 API는 다음과 같다. DirectedEdge(int v, int w , double weight) int from() int to() double weight() EdgeWeightedDigraph의 API는 다음과 같다. EdgeWeightedDigraphp(int V) void addEdge(Dired.. 4. Minimum spanning tree(MST) Mininum spanning tree란 weight를 가진 undirected graph가 주어졌을 때, 모든 vertex를 연결하면서 비용을 최소로하는 tree형태(cycle x)의 subgraph이다. 클러스터 분석등 여러 가지 응용에서 쓰인다. 1. Greedy algorithm Greedy algorithm은 매 순간 최적인 선택을 하며 그러한 방식으로 진행할 때, 최종적으로 해답에 도달하게 되는 알고리즘이다. 모든 문제에 대해서 적용되는 것은 아니지만, MST를 구할 때 이것을 적용할 수 있다. - 가정 : connected graph, distinct weights - Cut : 그래프가 주어졌을 때, 두개의 집합으로 vertex들을 분할하는 것 - crossing edge : 한 집합의 v.. 3. Directed Graph(Digraph) Directed graph는 edge의 방향이 존재하는 그래프이다. 우리 주변에 매우 많은 것들은 서로 연결되어있고, 가리키는 방향이 정해져있다. 프로그래밍으로 따지면, 상속관계, 함수의 호출구조 등이 있고, 응용은 무궁무진하다. 사실 이전에 배웠던 Undirected graph는 양방향 directed graph로도 볼 수 있다. 1) Digraph API Diagraph는 Undirected graph와 동일하게 Sparse Matrix를 표현할 때 사용하는, Adjacency-list를 주로 사용한다. Digraph API는 Undirected graph의 API와 완전히 동일하며, 모든 Edge의 방향을 바꾸는 연산이 추가된다. Digraph reverse() 구현 또한 완전히 동일한데, addE.. 2. Undirected Graphs 1. Terminology Graph란 edges로 연결된 vertices 집합이다. 지하철 노선도, 우주 은하 등 세상에 존재하는 수많은 것들을 그래프로 추상화하여 표현할 수 있다. Vertices의 이름은 symbol table로 Integer로 mapping하여 사용하면된다. 특히 Undirected graph는 edge의 방향이 존재하지 않는다. - Path : sequence of vertices connected by edges - Cycle : 첫번째와 마지막 vertex가 같은 Path 2. API & Representation Graph의 API는 다음과 같다. Graph(int V) // V개 vertice를 가진 그래프 생성 Graph(In in) // Input stream에 따라 .. 1. Introduction 알고리즘 강의를 다 들었다... 너무 유익한 강의였다! 그런데... 이게 알고보니 조금 더 내용은 어려운데 강의가 part2로 하나 더 있었다! 그래서 이걸 공부하면서 내용을 정리해보려고 한다...! 근데 또 욕심이 생겨서 최근에 시간날 때마다 MIT의 Computer Structure강의를 듣기 시작했다. 이것도 내용이 너무 좋아서 계속 볼것 같은데 큰일인듯.. (프로젝트는 언제하지.. ㅠ) 이전 1 2 다음
