Algorithm/그래프
-
Dinic's AlgorithmAlgorithm/그래프 2020. 2. 24. 21:03
http://blog.naver.com/kks227/220812858041 디닉 알고리즘(Dinic's Algorithm) (수정: 2016-09-19) 안녕하세요. 예고한 대로 더 빠른 시간복잡도의 최대 유량 알고리즘을 소개하러 왔습니다.그런데, 본래는 ... blog.naver.com kks227님의 디닉알고리즘 코드와 설명을 참고했습니다! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 ..
-
이분 매칭 문제를 해결하는 증가 경로 알고리즘Algorithm/그래프 2020. 2. 23. 22:22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 //이분 매칭 문제를 해결하는 증가 경로 알고리즘 //A와 B의 정점의 개수 int n, m; //adj[i][j] : Ai와 Bj가 연결되어 있는가? bool adj[MAX_N][MAX_M]; //각 정점에 매칭된 상대 정점의 번호를 저장한다 vector aMatch, bMatch; //dfs()의 방문 여부 vector visited; //A의 정점인 a에서 B의 매칭되지 않은 정점으로 가는 경로를 찾는다 bool dfs(int a) { if(visited[a]) return false; ..
-
Ford-Fulkerson algorithmAlgorithm/그래프 2020. 2. 10. 17:55
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 //네트워크 유량 문제를 해결하는 포드-폴커슨 알고리즘의 구현 const int INF = 987654321; int V; //capacity[u][v] : u에서 v로 보낼수 있는 용량 //flow[u][v] : u에서 v로 흘러가는 유량(반대 방향인 경우 음수) int capacity[MAX_V][MAX_V], flow[MAX_V][MAX_V]; //flow[][]를 계산하고 총 유량을 반환한다 int networkFlow(int source, int sink) { /..
-
Prim's MST algorithmAlgorithm/그래프 2020. 1. 31. 13:23
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 //프림 알고리즘의 구현 const int MAX_V = 100; const int INF = 987654321; //정점의 개수 int V; //그래프의 인접 리스트, (연결된 정점 번호, 간선 가중치) 쌍을 담는다 vector adj[MAX_V]; //주어진 그래프에 대해 최소 스패닝 트리에 포함된 간선의 목록을 selected에 //저장하고, 가중치의 합을 반환한다. int prim(vector& selected) { selected.clear(); //해당 점정이 트리에..
-
Kruskal's MST algorithmAlgorithm/그래프 2020. 1. 30. 17:53
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 //크루스칼의 최소 스패닝 트리 알고리즘 //트리를 이용해 상호 배제적 집합을 구현한다 struct DisjointSet; const int MAX_V = 100; //정점의 개수 int V; //그래프의 인접 리스트, (연결된 정점 번호, 간선 가중치) 쌍을 담는다. vector adj[MAX_V]; //주어진 그래프에 대해 최소 스패닝 트리에 포함된 간선의 목록을 selected에 //저장하고, 가중치의 합을 반환한다. int kruskal(vector& selected) { int ret..
-
Floyd-Warshall algorithmAlgorithm/그래프 2020. 1. 23. 14:41
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; #define MAX_V 1111 //플로이드 알고리즘에서 실제 최단 경로 계산하기 //정점의 개수 int V; //그래프의 인접 행렬 표현 //adj[u][v] : u에서 v로 가는 간선의 가중치, 간선이 없으면 INF를 넣는다. int adj[MAX_V][MAX_V]; //via[u][v] : u에서 v까지 가는 최단 경로가 경유하는 점 중 가장 번호가 큰 정점 //-1로 초기화해 둔다 int via[MAX_V][M..