DFS를 이용한 위상정렬

//깊이 우선 탐색을 이용한 위상 정렬
 
vector<int> seen, order;
void dfs(int here)
{
    seen[here] = 1;
    for(int there = 0; there < adj.size(); ++there)
        if(adj[here][there] && !seen[there])
            dfs(there);
    order.push_back(here);
}
//adj에 주어진 그래프를 위상정렬한 결과를 반환한다
//그래프가 DAG가 아니라면 빈 벡터를 반환한다
vector<int> topologicalSort()
{
    int m = adj.size();
    seen = vector<int>(m, 0);
    order.clear();
    for(int i = 0; i<m; ++i)
        if(!seen[i]) dfs(i);
    reverse(order.begin(), order.end());
    //만약 그래프가 DAG가 아니라면 정렬 결과에 역방향 간선이 있다
    //교차 간선은 위의 dfs의 order에 넣는 순서에 의해 무시되고 오직 역방향 간선만이 검출된다
    //교차 간선은 DAG와 아무상관 없지만 역방향 간선은 무조건 DAG임으로 역방향 간선이 있으면 빈 벡터를 반환한다
    for(int i = 0; i<m; ++i)
        for(int j = i+1; j<m; ++j)
            if(adj[order[j]][order[i]])
                return vector<int>();
    return order;
}

 

 

 

 

 

 

시간복잡도

인접행렬 : O(V^2)

(DAG인지 판단하는것 == DFS에 걸리는 시간)

인접리스트 : O(V^2) or O(|V| + |E|)

(DAG인지 판단하는것 or DFS에 걸리는 시간)

 

 

 

 

 

 

종만북2