Digraphs

개요

모든 간선이 directed인 그래프

 

 

Directed DFS

간선은 탐색 시점을 기준으로 discovery, back, forward, cross의 네 종류로 분류한다.

• discovery: end vertex가 unexplored인 edge
• back: end vertex가 ancestor인 edge
• forward: end vertex가 descendant인 edge
• cross: end vertex가 ancestor도 descendant도 아닌 정점인 edge

 

DAG와 위상 순서

DAG: Directed Acyclic Graph

 

위상 순서: 각 정점을 v1, v2, ..., vn이라고 할 때 모든 간선 (vi, vj)에 대해 i < j가 성립하는 순서

 

 

위상 정렬 알고리즘

시간복잡도 O(n + m)의 알고리즘이다.

TopologicalSort(Graph G):
    H = G
    n = G.numVertices()
    while not H.empty():
        v = vertex with no outdegree
        v.setLabel( n )
        n -= 1
        remove v from H

 

dfs를 이용한 구현은 다음을 참고하자.

 

#include <bits/stdc++.h>
using namespace std;

enum { UNEXPLORED, VISITED };

struct Node {
    int label, order;
    Node() { label = UNEXPLORED, order = -1; }
};

struct digraph {
    int N, M;
    vector<Node> nodes;
    vector<vector<int>> edges;

    digraph(int n) {
        N = M = n;
        nodes.resize(N);
        edges.resize(N);
    }

    void addEdge(int p, int q) { edges[p].push_back(q); }
};

void dfs(digraph& G, int cur) {
    G.nodes[cur].label = VISITED;
    for (int next : G.edges[cur]) {
        if (G.nodes[next].label == UNEXPLORED) {
            dfs(G, next);
        }
    }
    G.nodes[cur].order = G.M;
    G.M -= 1;
}
void toposort(digraph& G) {
    int N = G.N;
    vector<bool> dup(N, false);
    for (int i = 0; i < N; ++i)
        if (G.nodes[i].label == UNEXPLORED) dfs(G, i);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    digraph G(n);
    while (m--) {
        int p, q; cin >> p >> q; p--; q--;
        G.addEdge(p, q);
    }
    toposort(G);

    for (Node& n : G.nodes) cout << n.order << " ";
}