More on Graph algorithms

1. 최소 스패닝 트리

1) 프림 알고리즘

현재 MST에 속해 있는 점에서 가장 작은 가중치의 엣지와 노드를 추가한다.

계속 추가해 나간다.

끗.

정당성 : 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <queue>
#include <unordered_map>
 
using namespace std;
 
int main() {
    // get inputs and make graph
    int nodes;
    int edges;
    scanf("%d %d", &nodes, &edges);
    unordered_map<int, int> locator;
    vector < vector<pair<int, int>>> graph(nodes, vector < pair<int, int>>());
    int numbering = 0;
    for (int i = 0; i < edges; i++) {
        int from;
        int to;
        int weight;
        scanf("%d %d %d", &from, &to, &weight);
        auto it = locator.find(from);
        if (it != locator.end()) {
            from = it->second;
        }
        else {
            locator.insert(pair<int, int>(from, numbering));
            from = numbering;
            numbering++;
        }
        it = locator.find(to);
        if (it != locator.end()) {
            to = it->second;
        }
        else {
            locator.insert(pair<int, int>(to, numbering));
            to = numbering;
            numbering++;
        }
        graph[from].push_back(pair<int, int>(to, weight));
        graph[to].push_back(pair<int, int>(from, weight));
    }
 
    // do prim mst
    vector<int> included(nodes, 0);
    priority_queue < pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> queue;
    vector<pair<int, int>> total;
    long long sum = 0LL;
 
    for (int k = 0; k < nodes; k++) {
        if (included[k] == 0) {
            included[k] = 1;
            for (int i = 0; i < graph[k].size(); i++) {
                queue.push(pair<int, pair<int, int>>(graph[k][i].second, pair<int, int>(k, graph[k][i].first)));
            }
 
            // go through all candidates
            while (queue.size() != 0) {
                pair<int, pair<int, int>> curr = queue.top();
                queue.pop();
                if (included[curr.second.second] == 0) {
                    included[curr.second.second] = 1;
                    total.push_back(pair<int, int>(curr.second.first, curr.second.second));
                    sum += curr.first;
                    for (int i = 0; i < graph[curr.second.second].size(); i++) {
                        if(included[graph[curr.second.second][i].first]==0)
                            queue.push(pair<int, pair<int, int>>(graph[curr.second.second][i].second, pair<int, int>(curr.second.second, graph[curr.second.second][i].first)));
                    }
                }
            }
        }
    }
    cout << sum << endl;
}

시간 복잡도 : O(ElogE ~ ElogV)

공간 복잡도 : O(V+E)

2. 최단 경로 알고리즘

1) 다익스트라

출발점을 0으로 두고 주변 엣지를 min heap에 저장. 가장 작은 weight부터 하나씩 확장하면서 해당 node의 값을 업데이트하고, 그 edge를 전부 min heap에 추가하면서 진행한다. node의 weight가 작아지는 경우에만 다시 업데이트한다.

2) 플로이드 - 워셜

3) 벨만 - 포드

3. Strongly connected components

[알고리즘]

DFS의 종료 순서대로 스택에 담는다.

역방향 그래프를 생성한다.

스택의 순서대로 역방향 그래프를 DFS로 순회한다.

각 DFS 조각이 SCC 조각이다.

정당성 :

코드 :  https://github.com/fw93/Personal_Projects/tree/master/School/Algorithm%20HW/HW3

시간 복잡도 : O(V+E)