그래프의 표현방법
행렬 방법 : 삭제 등을 하는 경우에 사용한다.
vector<vector<int>> graph(32,vector<int>(32,0));
** 간선의 갯수가 아니라 간선에 weight 나 string 등의 특성이 담긴 경우
vector<vector<vector<string>>> graph
>> i->j로 가는 간선의 목록이 vector<string>으로 저장. 각 간선은 string을 가진다.
* vector<vector<int>> adj 와 vector<vector<vector<string>>> graph로 두개의 그래프를 만든 다음에, adj로 지우면서 순회하고 graph로 간선을 짜맞추면 직접 그래프를 순회하는 바람에 간선 정보를 삭제해야 하는 번거로움과 시간 낭비를 없앨 수 있다!!
리스트 방법: 검색의 숫자가 훨신 적어져서 빠르다.
vector<vector<int>> graph(10,vector<int>());
** 간선에 내용이 추가되는 경우
vector<vector<pair<int,int>> graph
>> i->j로 가는 간선에 int 변수가 존재. 간선이 여러 개인 경우에는 리스트 자체에 여러번 push_back 해야한다
--------------
그래프 컴포넌트의 갯수 세기 : 각 정점에서 DFS 해가면서 처음에 시작하는 것들을 센다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | void DFS(vector<vector<int>> & graph, vector<bool> & visited, int target) { if (visited[target] == false) visited[target] = true; cout << "visiting " << target << endl; for (int i = 0; i < graph[target].size(); i++) { if (visited[graph[target][i]] == false) DFS(graph, visited, graph[target][i]); } } int findcomponents(vector<vector<int>> & graph) { vector<bool> visited(graph.size(), false); int count = 0; for (int i = 0; i < graph.size(); i++) { if (visited[i] == false) { count++; DFS(graph, visited, i); } } return count; } | cs |
----------
두 정점의 연결 확인하기
한 점에서 DFS를 부른 후에 다른 점을 방문하는지 확인한다.
1 2 3 4 5 | bool connected(vector<vector<int>> & graph, int i, int j) { vector<bool> visited(graph.size(), false); DFS(graph, visited, i); return visited[j]; } | cs |
---------
위상 정렬(비사이클 방향 그래프 - DAG 에서)
: DFSall(for루프로 dfs 전체 돌리는 상위함수) 로 DFS를 부르면서 DFS가 "종료" 하는 순서를 기록한 후에 그것을 뒤집는다!!
증명 - 종료하는 순서를 뒤집었다고 해보자. 이때 더 뒷쪽에 있는 u에서 앞에 있는 v로 간선이 있다고 가정해 보자. u가 더 뒷쪽에 있으므로 v보다 종료를 먼저 했겠지?
이때 visited[v] 가 거짓인 경우에는 u가 v를 불렀을 꺼기 때문에 v가 u 이전에 종료하지 못한다 >> u에서 v로 가는 간선은 존재할 수 없다.
visited[v]가 참이었을 경우에는 u가 v를 불렀을 텐데, v가 종료를 더 늦게 했는데도 이미 방문되어 있다는 점은 v가 u를 호출하게 된다는 뜻이다(v를 방문했는데, u가 살아있고, 먼저 일하고, 죽는 동안 v가 살아있어야 하므로 결국에는 v가 어떤 식으로든 u를 부른 것!!)
그말인 즉슨 v에서 u로 가는 간선이 존재한다는 뜻인데, u에서 v로 가는 간선도 존재한다고 가정했으므로 순환 사이클이 발생하게 되어 우리가 처음 가정한 비사이클 그래프의 가정에 모순된다.
** 따라서 DFS가 종료된 순서를 뒤집은 배열은 역방향 간선이 없는 topological sort이다.
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 | void tDFS(vector<vector<int>> & graph, vector<bool> & visited, int target, stack<int> & buffer) { if (visited[target] == false) visited[target] = true; for (int i = 0; i < graph[target].size(); i++) { if (visited[graph[target][i]] == false) { tDFS(graph, visited, graph[target][i], buffer); } } buffer.push(target); } void topologicalsort(vector<vector<int>> & graph) { vector<bool> visited(graph.size(), false); stack<int> buffer; for (int i = 0; i < graph.size(); i++) { if (visited[i] == false) { tDFS(graph, visited, i, buffer); } } // print stack while (buffer.size() != 0) { cout << buffer.top() << " "; buffer.pop(); } cout << endl; } | cs |
---------
사이클 존재 확인하기
방향 사이클 : 한 점에서 시작하는 DFS에 대해 모든 점을 기록해 가면서 사이클을 돌린다. 돌다가 기록된 점을 만나면 당첨. 그 점을 다 끝내고 아예 다른 폴션으로 이동할 때에 기록을 삭제해야 한다!( 아 삭제 안해도 상관 없네. 어짜피 방문 안할테니까. 그냥 기록하면서 돌자 ).
비방향 사이클 : 시작점 관계없이 DFS가 불린 부모를 제외한 다른 "visited == true" 점이 adjacent으로 있으면 사이클이 존재한다.
왜냐면, 사이클이 없다는 뜻은 그런 점이 존재하지 않는다는 뜻이고 사이클이 존재하면 그런 점을 반드시 만나게 된다.
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 | bool iscycle(vector<vector<int>> & graph) { vector<bool> visited(graph.size(), false); stack<int> buffer; unordered_set<int> contains; for (int i = 0; i < graph.size(); i++) { if (visited[i] == false) { buffer.push(i); contains.insert(i); while (buffer.size() != 0) { int curr = buffer.top(); if (visited[curr] == false) visited[curr] = true; buffer.pop(); // go through adjacent elements for (int j = 0; j < graph[curr].size(); j++) { // check if element is in track. if so, return true // because the element comes from there to here then // here to there making a cycle if (contains.find(graph[curr][j]) != contains.end()) { cout << i << " " << curr << " " << graph[curr][j] << endl; return true; } if (visited[graph[curr][j]] == false) { buffer.push(graph[curr][j]); contains.insert(graph[curr][j]); } } } contains.clear(); } } return false; } bool cDFS(vector<vector<int>> & graph, vector<bool> & visited, int target, int parent) { visited[target] = true; // go to adjacent nodes. if visited and not parent, return true bool ret = false; for (int i = 0; i < graph[target].size(); i++) { // self cycle also considered cycle here. // if not wanted, do graph[target][i]!=target here if (visited[graph[target][i]] == true && graph[target][i] != parent&&parent != -1) { cout << "found at " << target << " " << parent << " " << graph[target][i] << endl; return true; } if (visited[graph[target][i]] == false) { ret |= cDFS(graph, visited, graph[target][i], target); } } return ret; } bool iscycle2(vector<vector<int>> & graph) { vector<bool> visited(graph.size(), false); // start from every unvisited cycle for (int i = 0; i < graph.size(); i++) { bool ret; if (visited[i] == false) ret = cDFS(graph, visited, i, -1); if (ret == true) return true; } } | cs |
---------------
오일러 서킷 : u 에서 u로 모든 Edge를 지난 후에 돌아오는 경로
오일러 트레일 : u 에서 다른 v로 모든 Edge를 지난 후에 가는 경로
비방향 그래프 방향 그래프
오일러 서킷 모든 node의 edge가 짝수개 모든 node의 inbound = outbound edges
오일러 트레일 u와 v는 홀수 개, 나머지는 edge가 짝수개 u는 outbound가 한개 더, v는 inbound가 한개 더
해당 서킷/트레일이 존재하기 위한 필요충분조건이다.
무향 그래프의 오일러 서킷 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | void getEuler(int here, vector<int> & res, vector<vector<int>> & graph){ for(int there = 0 ; there < graph[0].size() ; there++){ while(graph[here][there]>0){ graph[here][there]--; graph[there][here]--; getEuler(there,res,graph); } } res.push_back(here); } void getEuler2(int here, vector<int> & res, vector<vector<int>> & graph){ for(int there = 0 ; there < graph[0].size() ; there++){ while(graph[here][there]>0){ graph[here][there]--; getEuler2(there,circuit); } } res.push_back(here); } | cs |
** 알고리즘 특성상 트레일 조건이건 서킷 조건이건 그냥 돌리면 구해준다. 엣지 추가하지 말것. 그게 마지막 점이라는 보장 절대 없다. **
방향 그래프의 오일러 서킷 존재성은 함수를 돌린 결과를 분석해도 되지만, 그래프 만드는 과정에서 inbound[n] 과 outbount[n]을 만들어서 트래킹 하면 매우 빠르다.
TODO : 종만책 예제 풀기, 트레일 서킷 변환시 그 구간이 양끝에 항상 존재하는지 확인하기
---------------
양방향 BFS(최단거리)
양쪽 끝에서 동시에 큐를 이용한 BFS를 시작해서 중간에 서로가 visit 한 점을 만나면 값을 더하고 종결한다. 순회할 때에 같은 거리의 값들을 순서대로 순회하므로 처음으로 만나는 경우 그 점이 곧 양쪽의 최단 거리이고 전체의 최단 거리이다. 큐가 비면 그 섹션을 전부 순회했다는 뜻이므로 서로 만나지 못하는 것이다.
*** 보드에 같은 것을 칠하는 여러 점에서의 최단거리 구하기나 painter problem 같은거는 그냥 그 모든 시작점을 enqueue 해버리고 BFS 하면 된다!!
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 | int distance(vector<vector<int>> & graph, int i, int j) { vector<int> dist(graph.size(), -1); vector<bool> visitedi(graph.size(), false); vector<bool> visitedj(graph.size(), false); dist[i] = 0; dist[j] = 0; queue<int> iq; queue<int> jq; iq.push(i); jq.push(j); while (iq.size() != 0 && jq.size() != 0) { int curri = iq.front(); int currj = jq.front(); iq.pop(); jq.pop(); // do left for (int i = 0; i < graph[curri].size(); i++) { if (visitedj[graph[curri][i]] == true) { // two BFS met return dist[curri] + dist[graph[curri][i]]+1; } else if(visitedi[graph[curri][i]]==false){ // mark adjacent nodes and enqueue dist[graph[curri][i]] = dist[curri] + 1; visitedi[graph[curri][i]] = true; iq.push(graph[curri][i]); } } // do right for (int i = 0; i < graph[currj].size(); i++) { if (visitedi[graph[currj][i]] == true) { // two BFS met return dist[currj] + dist[graph[currj][i]]+1; } else if (visitedj[graph[currj][i]] == false) { // mark adjacent nodes and enqueue dist[graph[currj][i]] = dist[currj] + 1; visitedj[graph[currj][i]] = true; jq.push(graph[currj][i]); } } } // not met return 99999; } | cs |
---------------
최단 경로 알고리즘(다익스트라)
우선순위 큐를 사용해서 가장 가까운 거리의 노드부터 큐에서 pop 하고, 인접 노드 중에 top의 거리 + 엣지보다 거리 긴 놈 있으면 top의 거리 + 엣지로 거리 업데이트 해준다.
주의사항은 graph의 first는 원소번호고 priority_queue는 (거리,원소번호) 로 되어있어서 first second 잘 쓰자.
시간 복잡도 : O(ElogE) - 최단 경로인 경우 엣지마다 우선순위 큐에 들어갈 수 있어 고려되는 것이 E, 각 경우에 대해 우선순위 큐에 push pop 동작이 log E
정당성 증명 : 만약에 최단 거리가 아닌 노드 u가 존재한다고 하면, 지금까지 방문했던 원소들의 경로가 아닌 다른 경로로 u에 도착하는 것이 더 빠른 경로라는 뜻이다. 그런데, 그렇다는 것은 우선순위 힙에서 u를 부르지 않고 그 최단거리 경로를 우선순위 힙으로 쭉쭉 불러냈을 것이기 때문에 모순이다. 따라서, 우선순위 힙이 u를 불러냈다는 뜻은 그 경로가 최단 경로라는 뜻이다.
*&* 최단 경로를 구하고 싶으면 노드들을 역추적하면 된다. 같은 값이 있을 수 있으므로 재귀적으로 ^^7
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | vector<int> dijkstra(vector<vector<pair<int, int>>>&graph, int i) { vector<int> dir(graph.size(), INT_MAX); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; dir[i] = 0; q.push(pair<int, int>(0,i)); while (q.size() != 0) { if (dir[q.top().second] < q.top().first) { q.pop(); continue; } int curr = q.top().second; int cdis = q.top().first; q.pop(); for (int i = 0; i < graph[curr].size(); i++) { if (dir[graph[curr][i].first] > cdis + graph[curr][i].second){ dir[graph[curr][i].first] = cdis + graph[curr][i].second; q.push(pair<int, int>(dir[graph[curr][i].first], graph[curr][i].first)); } } } return dir; } | cs |
* dijkstra with path tracing
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 | vector<pair<int,vector<int>>> dijkstra(vector<vector<pair<int, int>>> & graph, int start) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; vector<pair<int,vector<int>>> dist(graph.size(), pair<int,vector<int>>(INT_MAX,vector<int>())); dist[start].first = 0; dist[start].second.push_back(start); q.push(pair<int, int>(dist[start].first, start)); while (q.size() != 0) { auto it = q.top(); int currd = it.first; int curr = it.second; q.pop(); if (currd > dist[curr].first) continue; // update adjacent elements for (int i = 0; i < graph[curr].size(); i++) { int newdist = currd + graph[curr][i].second; if (dist[graph[curr][i].first].first > newdist ) { dist[graph[curr][i].first].first = newdist; vector<int> tmp = dist[curr].second; tmp.push_back(graph[curr][i].first); dist[graph[curr][i].first].second=tmp; q.push(pair<int, int>(newdist, graph[curr][i].first)); } } } return dist; } | cs |