그래프 알고리즘 정리

1. DFS 스패닝 트리

 

DFS 탐색하면서 탐색 순서에 따른 간선 분류와 만들어지는 트리

 

트리 간선 : 스패닝 트리에 포함되는 간선

순방향 간선 : 선조에서 자손으로 연결되는 간선이지만 트리간선이 아닌 간선

역방향 간선 : 자손에서 선조로 연결되는 간선

 

2. 절단점 찾기

정의

절단점 : 무향그래프에서 어떤 점의 인접한 간선을 모두 지웠을 때 컴포넌트가 두 개 이상으로 나눠지는 점 

 

기차역, 라우터 등 절단점이 있으면 해당 점이 고장나면 전체 망이 고장난다.

 

절단점 찾는 방법 : DFS 스패닝 트리에서 어떤 정점 u의 서브트리 중에 u의 선조로 가는 역방향 간선이 하나라도 존재하지 않으면 절단점이 된다.

-> 그럼 u의 1,2,3 서브트리 중 1이 선조로 가고 2가 1로 3이 2로 가면 u는 절단점인가? -> 아니다 2가 1로 가고 1이 가장 상위 선조를 반환하기 때문

 

예외 조심 - 루트인데 자손이 하나도 없거나, 자손이 하나밖에 없다면 그 루트는 절단점이 아님.

 

구현

서브 트리에서 가장 상위(방문 순서 상)로 가는 정점의 order(가장 작은 order)를 반환하도록 한다. 

https://www.acmicpc.net/problem/11266

 

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<cmath>
#define INF 1e9
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
int cnt; // 방문 순서
vector<vector<int>> v;
vector<int> order;
vector<bool> isCurVertex;
 
/* 
 진입점을 root로 하는 tree에서 역방향 간선으로 가는 정점 중
 가장 상위 정점의 order를 반환한다.
*/
int findCutVertex(int cur, bool isRoot) {
    order[cur] = cnt++; // 방문 순서 증가
    int child = 0, ret = order[cur];
    for(int i=0; i<v[cur].size(); i++) {
        int next = v[cur][i];
        if(order[next] == -1) { // 방문하지 않은 자식들 계속 해서 방문한다.
            child++;
            
            // 자식 sub tree에서 역방향 간선으로 가는 가장 상위 정점으로 가는 order를 반환.
            int v_order = findCutVertex(next, false);
            
            // 자식 sub tree에서 가장 상위 정점의 order가 나(cur)와 같거나 그 이상이면
            // 상위로 가는 방법이 없기때문에 절단점이 된다.
            if(!isRoot && v_order >= order[cur]) {
                isCurVertex[cur] = true;
            }
            
            // 현재 tree에서 갈 수 있는 가장 상위 정점 order 업데이트.
            ret = min(ret, v_order);
        }
        else {
            // 이미 방문한 order라면 재귀로 들어가지 않고 order 사용.
            ret = min(ret, order[next]);
        }
    }
    
    // 루트이면서 자식이 둘 이상이면 절단점이 된다.
    if(isRoot && child >= 2) isCurVertex[cur] = true;
    return ret;
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    v = vector<vector<int>>(n+1);
    order = vector<int>(n+1, -1);
    isCurVertex = vector<bool>(n+1, false);
    
    for(int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    for(int i=1; i<=n; i++) {
        if(order[i] == -1) {
            cnt = 0;
            findCutVertex(i, true);
        }
    }
    
    vector<int> ans;
    for(int i=1; i<=n ;i++) {
        if(isCurVertex[i]) ans.push_back(i);
    }
    
    cout << ans.size() << "\n";
    for(int i=0; i<ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
 

 

절단선은 하위 sub tree 에서 자신보다 같거나 상위 정점으로 가는 역방향 간선이 없으면 절단선이 된다.

 

https://www.acmicpc.net/problem/11400

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<cmath>
#define INF 1e9
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
int cnt; // 방문 순서
vector<vector<int>> v;
vector<int> order;
vector<pair<int,int>> cut_edge;
 
// 내 하위 트리에서 가장 상위 정점 (가장 작은 order) 반환.
int findCutEdge(int cur, int prev) {
    order[cur] = cnt++; // 방문 순서 증가
    int ret = order[cur];
    for(int i=0; i<v[cur].size(); i++) {
        int next = v[cur][i];
        if(order[next] == -1) {
            
            int v_order = findCutEdge(next, cur);
            
            // 내 하위 subtree 의 가장 상위 정점이 내 자신보다 크다면 절단선. 작거나 같으면 절단되지 않고 연결됨.
            if(order[cur] < v_order) {
                if(cur < next) cut_edge.push_back({cur, next});
                else cut_edge.push_back({next, cur});
            }
            
            ret = min(ret, v_order);
        }
        // 이전과 다음이 같을 수 있다.
        else if (prev != next) {
            ret = min(ret, order[next]);
        }
    }
    
    return ret;
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    v = vector<vector<int>>(n+1);
    order = vector<int>(n+1, -1);
    cut_edge.resize(0);
    
    for(int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    cnt = 0;
    findCutEdge(1, 1);
    
    sort(cut_edge.begin(), cut_edge.end());
    
    cout << cut_edge.size() << "\n";
    for(int i=0; i<cut_edge.size(); i++) {
        cout << cut_edge[i].first << " " << cut_edge[i].second << "\n";
    }
    
    return 0;
}
 

 

3. SCC (Strong Connected Component)

정의

Biconnected Component : 무향그래프에서 절단점이 존재하지 않는 그래프

Strong Connected Component : 방향그래프에서 임의의 한점에서 다른 모든 정점으로 가는 경로가 존재하는 컴포넌트

 

SCC 검출에 사용되는 알고리즘

 

코사라주 : 위상정렬 사용

1. 역방향 그래프를 준비한다.
2. 위상정렬을 한다. (빠져나오면서 스택에 push)
3. 스택을 pop하며 역방향 그래프를 dfs 탐색한다.  (이미 방문했다면 pop만 한다.)
4. 탐색이 가능한 정점끼리 scc가 된다.

아이디어 - 위상정렬의 순서에서 역방향 그래프더라도 scc끼리는 탐색이 가능하다.

(SCC 정의에 따르면 임의의 정점에서 다른 모든 정점으로 가는 경로가 존재한다는 뜻이다. 

즉 컴포넌트 내부의 임의의 두 정점 X, Y가 존재할 때 X->Y의 경로가 존재하면 Y->X 의 경로도 존재한다는 의미이고, SCC면 역방향 그래프더라도 동일한 scc를 형성한다.)

만약 scc가 아닌 두 컴포넌트 간의 연결이라면 역방향 그래프에서 탐색이 되지 않는다.

코사라주 방식 풀이

https://www.acmicpc.net/problem/2150

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<stack>
#include<cmath>
#define INF 1e9
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
 
vector<vector<int>> v;
vector<vector<int>> reverse_v;
vector<bool> visited;
stack<int> st;
 
vector<vector<int>> scc;
 
void reverse_dfs(int cur, vector<int>& t) {
    t.push_back(cur);
    visited[cur] = true;
    
    for(int i=0; i<reverse_v[cur].size(); i++) {
        int next = reverse_v[cur][i];
        if(!visited[next]) {
            reverse_dfs(next, t);
        }
    }
}
 
void dfs1(int cur) {
    visited[cur] = true;
    
    for(int i=0; i<v[cur].size(); i++) {
        int next = v[cur][i];
        if(!visited[next]) {
            dfs1(next);
        }
    }
    
    st.push(cur);
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    v = vector<vector<int>>(n+1);
    reverse_v = vector<vector<int>>(n+1);
    visited = vector<bool>(n+1, false);
    scc.resize(0);
    
    for(int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        reverse_v[y].push_back(x);
    }
    
    for(int i=1; i<=n; i++) {
        if(!visited[i]) {
            dfs1(i);
        }
    }
    
    visited = vector<bool>(n+1, false);
    
    while(!st.empty()) {
        int x = st.top();
        st.pop();
        if(!visited[x]) {
            vector<int> t;
            reverse_dfs(x, t);
            sort(t.begin(), t.end());
            scc.push_back(t);
        }
    }
    
    cout << scc.size() << "\n";
    sort(scc.begin(), scc.end());
    for(int i=0; i<scc.size(); i++) {
        for(int j=0; j<scc[i].size(); j++) {
            cout << scc[i][j] << " ";
        }
        cout <<"-1\n";
    }
    
    return 0;
}
 

 

타잔 : 절단선 자르는 것과 비슷하다.

방문한 정점 순서를 저장하면서 dfs 탐색한다.

sub tree에서 도달 가능한 최소 순서의 정점이 자기 자신이면 SCC로 구분한다.

 

재귀 탐색 시에 이미 SCC 구분이 지어진 정점이면? 

-> 내가 해당 SCC에 속했다면 이미 나도 정해져 있을테고, 그렇지 않다면 서로 다른 SCC이므로 고려할 필요 없다.

 

이미 방문했지만 SCC 구분이 지어지지 않은 정점이면?

-> 방문한 정점의 도달 가능한 상위 정점이 내 조상과 같은 정점일 수 있어서 같은 SCC가 될 수 있다.

타잔 방식 풀이

https://www.acmicpc.net/problem/2150

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<stack>
#include<cmath>
#define INF 1e9
using namespace std;
using ll = long long;
using pii = pair<int, int>;
 
int vCnt, sCnt; // 방문 순서, scc 번호
vector<vector<int>> v;
vector<int> order, sccId;
stack<int> st;
 
vector<vector<int>> scc;
 
int getSCC(int cur) {
    order[cur] = vCnt;
    int ret = order[cur];
    vCnt++;
    st.push(cur);
    for(int i=0; i<v[cur].size(); i++) {
        int next = v[cur][i];
        if(order[next] == -1) { // 방문하지 않았다면 탐색
            ret = min(ret, getSCC(next));
        }
        else if(sccId[next] == -1){ // 방문했지만 sccId가 없다면,
            ret = min(ret, order[next]); // order[next]로 갱신해도 괜찮다. next 에서 도달 가능한 최소 순서의 정점일 필요는 없다.
            // 방문한 next에서 이미 해당 재귀에서 최소 순서의 정점을 return하여 처리하고 있기 때문.
            // 결국 next와 나의 공통 조상에서 이미 반환되어 min 처리된 반환값 가지고 scc를 결정함.
        }
        // sccId가 이미 있다면 탐색 대상이 아님.
    }
    
    // sub tree의 도달 가능한 최소 순서의 정점이 나와 같다면 SCC.
    // A -> B -> C -> A 이면 A,B,C는 같은 SCC가 되고,
    // A -> B -> C 이면 A, B, C는 별개의 서로 다른 SCC가 된다.
    if(ret == order[cur]) {
        vector<int> tmp;
        while(true) {
            int t = st.top();
            st.pop();
            sccId[t] = sCnt;
            tmp.push_back(t);
            if(t == cur) break;
        }
        
        sort(tmp.begin(), tmp.end());
        scc.push_back(tmp);
        
        sCnt++;
    }
    
    return ret;
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    
    v = vector<vector<int>>(n+1);
    order = vector<int>(n+1, -1);
    sccId = vector<int>(n+1, -1);
    scc.resize(0);
    
    for(int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
    }
    
    for(int i=1; i<=n; i++) {
        if(order[i] == -1) {
            getSCC(i);
        }
    }
    
    cout << scc.size() << "\n";
    sort(scc.begin(), scc.end());
    for(int i=0; i<scc.size(); i++) {
        for(int j=0; j<scc[i].size(); j++) {
            cout << scc[i][j] << " ";
        }
        cout <<"-1\n";
    }
    
    return 0;
}
 

 

 

+ 구현은 코사라주가 쉽고, 속도는 타잔이 미세하게 빠르다고 하는데 자기가 편한 거 쓰면 될 듯
(타잔이 함수 하나로 구현할 수 있어서 깔끔한 것 같다~)

 

4. 한 붓 그리기 (오일러 트레일, 오일러 서킷)

정의

오일러 서킷 : 모든 간선을 한번만 지나면서 시작점에서 출발하여 시작점으로 돌아오는 회로

오일러 트레일 : 모든 간선을 한번만 지나면서 시작점에 출발하여 끝점에 도착하는 회로

 

오일러 서킷과 오일러 트레일의 차이점은 시작점과 끝점이 같냐 아니냐의 차이

 

존재성 

오일러 서킷 : 모든 정점이 짝수개의 간선을 가진다.  (시작점으로 돌아와야 하기 때문)

오일러 트레일 : 시작점 끝점은 간선이 항상 홀수개이고, 그 외의 정점은 짝수개의 간선을 가진다.

 

구현

간선을 지우면서 재귀에 들어간다.

재귀를 빠져나오면서 결과에 추가한다. (유향 그래프라면 결과를 역순으로 출력한다.)

이러면 회로 내부에 회로가 있어도 빠짐없이 추가된다.

 

시간복잡도는 간선만큼 수행한다. O(|E|) 혹은 O(|V||E|)

 

vector<vector<int>> adj;

void getEulerCircuit(int here, vector<int>& circuit) {
    for(int there = 0; there < adj[here].size(); ++there) {
        while(adj[here][there] > 0) {
            adj[here][there]--;
            adj[there][here]--;
            getEulereCircuit(there, circuit);
        }
        
    circuit.push_back(here);
}

 

5. 음수 사이클

 

벨만포드 사용

음수 사이클이 없다면 모든 간선에 대해 최대 V-1번 만큼 반복 수행하면 업데이트가 완료됨 (V-1 번 반복하기 전에 확정될 수도 있음)

음수 사이클 판정 -> 모든 간선을 V-1번 만큼 확인했음에도 거리가 업데이트 된다면 음수사이클 존재

 

다익스트라와 달리 모든 간선에 대해 반복 수행

 

6. 위상 정렬 (DAG)

전제 조건. 사이클이 없어야 한다.

 

구현

1. dfs를 전부 돌면서 마지막 정점부터 결과에 추가하면서 재귀 빠져나옴 -> 결과 거꾸로 출력

 

1-1. 시작하는 지점이 진입차수가 0 이다. 

-> 당연히 성립

 

1-2. 시작점이 진입차수가 0이 아닌 중간부터다.

->어차피 방문한 곳은 방문을 안하니, 해당 재귀 안에서는 순서가 유지되고

재귀와 재귀 사이에선 결과적으로 중간 이후 재귀가 먼저 쌓이고, 그 앞의 재귀가 나중에 쌓이니 역시 순서가 유지됨.

즉. 재귀 안에서는 순서 유지, 재귀와 재귀 사이에서도 방문처리를 하니까 순서 유지.

 

2. queue를 이용 . indegree

각 정점의 진입차수를 기록.

진입차수 0인 정점을 큐에 넣음.

큐에서 꺼내면서 자신의 간선의 진입차수 감소.

0이 되는 정점을 큐에 push.

큐가 빌 때까지 반복.

 

7. 최단 경로

다익스트라

 

8. 최소 스패닝 트리

 

가중치 합이 가장 낮은 스패닝 트리

대표적으로 크루스칼과 프림 알고리즘이 있음

 

크루스칼 - 가중치 순으로 정렬하고, union-find 사용

프림 - 시작정점에서 가중치 작은 정점을 선택하면서 확장하는 방식. 우선순위큐 사용