혼자서 공부하는 블로그

Kruskal 알고리즘의 시간복잡도 = O(E logE) Prim 알고리즘의 시간복잡도 = O(E logV) 즉, 간선이 많다면 Prim을, 그렇지 않다면 Kruskal을 쓰는 것이 효율적이다. //유니온-파인드가 구현된 상태여야 함. '알고리즘 공부/Disjoint-set(유니온-파인드)' 카테고리의 글 목록 공부한 것을 이것저것 다시 정리해보는 블로그 castlejh.tistory.com typedef struct _elem { int a, b, w; } elem; struct cmp { bool operator()(elem a, elem b) { return a.w > b.w; } }; priority_queue pq; int v, e; int parent[10001]; int depth[10001..

Kruskal 알고리즘의 시간복잡도 = O(E logE) Prim 알고리즘의 시간복잡도 = O(E logV) 즉, 간선이 많다면 Prim을, 그렇지 않다면 Kruskal을 쓰는 것이 효율적이다. typedef pair pii; bool visit[10001] = { false }; vector adj[10001]; int v, e; struct cmp { bool operator()(pii a, pii b) { return a.second > b.second; } }; int prim(int start) { priority_queue pq; int ret = 0; int joined = 0; pii cur, connect; pq.push({ start, 0 }); while (joined

#include #include #define INF 1

#include #include #define INF 9999999 using namespace std; int table[101][101]; //table[i][j]는 i==j인 경우 0으로, i->j의 cost가 w인경우 w로, i->j인 간선이 없으면 INF로 초기화한 상태여야 한다. void Floyd(int v) { //v는 정점 개수 for (int k = 1; k

#include #include #include #define INF 123456789 using namespace std; vector adj[20001]; //인접리스트 int table[20001]; //비용을 갱신할 테이블 void dijkstra(int start) { priority_queue pq; //큐에 들어있는 원소의 의미는 이다. //이때, 비용은 절댓값이 같은 음수로 저장되어있다. (e.g. 비용이 5라면 큐에는 -5로 저장되어있음.) //그 이유는 기본적으로 큐의 원소인 pair가 사전순(first->second) 기준으로 내림차순 삽입되기 때문이다. //즉, 예를들어 5, 3, 7의 비용이 있다면 이것이 7, 5, 3이 아닌 -3, -5, -7 순으로 삽입되도록 비용을 절댓값이 ..

DFS와 BFS의 Pseudocode이다. DFS void dfs(int idx) { /* 여기에다 현재 방문한 vertex에 대해 해주고 싶은것 이것저것 하세요~~ */ for (a = adjacent of idx) { //모든 인접 노드들에 대하여 if (!visited[a]) { //탐색 안했으면 visited[a] = true; //이번 vertex 방문표시 dfs(a); //들어갑시다~ } } } BFS void bfs(int start) { queue.push(start); //시작 vertex 방문 및 큐에 넣기. visited[start] = true; while (queue에 원소가 있음) { idx = q.front(); //큐에서 원소 하나 빼오기. q.pop(); /* 여기에다 현재..