Graph

Depth-First Search (DFS)

 

 

Backtracking 전에 가능한한 시작점으로부터 깊은 노드들을 먼저 탐색한다.

 

보통 재귀나 stack을 사용하여 구현.

 

 

Breadth-First Search (BFS)

 

시작점으로부터 같은 깊이의 노드들을 먼저 탐색한 후 더 깊은 노드들을 탐색한다.

 

queue를 사용하여 구현.

 

 

Lowest Common Ancestor (LCA)

 

트리 구조에서 height가 가장 낮은 공통 ancestor을 LCA라 부른다.

 

 

Euler tour를 순회하는 방법

 

- sqrt decomposition (O(n) for preprocessing, O(n^(1/2)) for query)

 

- segment tree (O(n) for preprocessing, O(log n) for query)

 

 

ancestor을 저장하는 방법

 

- sparse table (O(n log n) for preprocessing, O(log n) for query)

 

 

Segment tree implementation (0-base node)

 

#include <bits/stdc++.h>

using namespace std;

struct LCA {
    vector<int> height, euler, first, segtree;
    int n, m;

    LCA(vector<vector<int> > &adj, int root = 0) {
        n = adj.size();
        height.resize(n);
        first.resize(n);
        euler.reserve(n * 2);
        dfs(adj, root);
        m = euler.size();
        segtree.resize(m * 4);
        build(1, 0, m - 1);
    }

    void dfs(vector<vector<int> > &adj, int node, int h = 0) {
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto child : adj[node]) {
            dfs(adj, child, h + 1);
            euler.push_back(node);
        }
    }

    void build(int cur, int left, int right) {
        if (left == right) {
            segtree[cur] = euler[left];
        } else {
            int mid = (left + right);
            build(cur << 1, left, mid);
            build((cur << 1) + 1, mid + 1, right);
            int l = segtree[cur << 1], r = segtree[(cur << 1) + 1];
            segtree[cur] = (height[l] < height[r]) ? l : r;
        }
    }

    int query(int q_left, int q_right, int cur, int left, int right) {
        if ((q_right < left) || (right < q_left)) {
            return -1;
        }
        if ((q_left <= left) && (right <= q_right)) {
            return segtree[cur];
        }

        int mid = (left + right) / 2;
        int l = query(q_left, q_right, cur << 1, left, mid);
        int r = query(q_left, q_right, (cur << 1) + 1, mid + 1, right);
        if (l == -1) {
            return r;
        }
        if (r == -1) {
            return l;
        }
        return height[l] < height[r] ? l : r;
    }
};

 

 

Minimum Spanning Tree (MST)

 

비용이 최소가 되는, 그래프의 모든 정점들을 가진 트리이다.

 

당연하게도 근원이 되는 그래프가 connected graph 여야 한다.

 

구현 방법으로는 Prim's algorithm과 Kruskal's algorithm 이 있다.

 

둘 다 greedy한 방법이다.

 

알고리즘의 정당성에 대한 증명은 쉽다.

 

대상이 되는 graph의 MST를 가정한다.

 

그리고 MST에서 하나의 edge를 없애 두 개의 tree를 만든다.

 

이 두 개의 tree가 다시 원래의 MST로 복귀하기 위해서는 두 tree를 연결하는 edge가 필요한데,

 

당연하게도 minimum cost를 위해 선택되는 edge의 cost는 최소가 되어야 한다.

 

 

Prim's algorithm

 

 

Kruskal's algorithm

 

 

 

* 코드는 차후 추가