그래프의 간선구분, 사이클 존재 여부 판단

int V,E,cnt=1;
vector<int>adj[MAX_N],discoverd,finished;
vector<int>treeEdge,forwardEdge,backEdge,crossEdge;

int dfs(int u)
{
    discoverd[u]=cnt++;
    for(auto v:adj[u])
    {
        if(!discoverd[v])
        {
            treeEdge[v]=true;
            dfs(v);
        }
        else if(discoverd[u]<discoverd[v])forwardEdge[v]=true;
        else if(!finished[v])backEdge[v]=true;
        else crossEdge[v]=true;
    }
    finished[u]=true;
}

 

• 어떤 그래프를 DFS했을때, 탐색이 따라가는 간선들만을 모으면 트리 형태가 된다. 이르 DFS 스패닝 트리(DFS spanning tree)라고 부른다. 이때 그 그래프의 모든 간선을 다음과 같은 4가지로 나눌 수 있다.
• 트리 간선(tree edge):스패닝 트리에 포함된 간선
• 순방향 간선(forward edge):스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선은 아닌 간선
• 역방향 간선(back edge):스패닝 트리의 자손에서 선조로 연결되는 간선
• 교차 간선(cross edge):위의 분류를 제외한 나머지 간선들
• 위의 분류는 유향 그래프 일 때 정의된 것이고, 무향 그래프일때는 양방향으로 통행을 하기 때문에 교차간선이 존재 하지 않는다.또한 무향 그래프는 순뱡향과 역방향 간선의 구분이 없음도 유의하자.
• 위상 정렬의 정당성 증명에도 사용된다.
• 이를 이용해 유향 그래프일때의 사이클 존재 여부를 확인 할 수있다. 사이클 존재 여부는 역방향 간선의 존재 여부와 동치이다.
• 연관 알고리즘: 절단점 찾기