알고리즘 공부[5] 간선의 분류와 싸이클 검출

안녕하세요. 

오늘은 그래프의 간선에 대한 내용과 싸이클 검출 방법에 대해 알아보겠습니다.

Contents

간선의 분류

싸이클 존재 여부의 확인

간선의 분류

---

간선 구분에 대한 정확한 정의를 살펴봅시다.

DFS를 수행할 때 방문하는 간선들을 모아 만든 tree를 DFS spanning tree라고 합니다.

아래와 같은 그래프가 있고, DFS를 1번 정점으로 부터 정점 번호가 작은 순으로 선택한다고 합시다.

그렇다면 DFS Spanning tree는 아래 그림에서 실선에 해당하는 트리를 말합니다. (Root는 1번 정점이 되겠죠)

여기서 실선으로 이루어진, DFS spanning tree를 이루는 간선을 tree edge(트리 간선)이라고 합니다.

forward edge(순방향 간선)이란 트리간선이 아닌데, 트리의 부모에서 자식으로 이어진 간선을 말합니다. 

여기서는 4번에서 8번으로 가는 간선이죠.

back edge(역방향 간선)이란 순방향과 반대로 트리간선이 아닌데, 자식에서 부모로 이어진 간선을 말합니다. 

6번에서 1번으로 가는 간선이 역방향 간선입니다.

이외의 나머지인 트리간선이 아니면서, 부모 자식간의 관계가 아닌 정점들 끼리 이어진 간선을 cross edge(교차간선)이라 합니다.

8번에서 2번으로 가는 간선이 여기서는 교차간선이 됩니다.

간선을 구분해 내는 방법 또한 역시 dfs를 이용하면 됩니다.

역방향 간선은 위에서 이미 살펴보았던 싸이클을 구분할 때 이미 검출이 됩니다.

이 외에 순방향 간선을 구분하기 위해서는 정점의 방문 순서를 저장해 놓으면 쉽게 검출할 수 있습니다.

DFS spanning tree에서 부모 정점은 자식 정점보다 무조건 먼저 방문하기 때문이죠.

간선 구분하는 방법

1) tree edge : DFS spanning tree를 만들면서 구분

2) forward edge : 정점의 방문 순서를 저장하여 구분

3) back edge : DFS의 종료 여부를 이용하여 구분

4) cross edge : 1), 2), 3)이 아닌 경우는 모두 cross edge로 구분

싸이클 존재 여부의 확인

---

앞서 DFS를 공부했으니 싸이클의 존재를 확인하는 방법은 아주 직관적으로 찾을 수 있습니다.

그 전에 다시 한번 DFS의 구현 코드를 살펴봅시다.

#include<iostream>
#include<vector>
using namespace std;
 
int V_size;                     //주어진 그래프의 Vertex개수(|V|)
vector< vector<int> > adjacent; //인접 행렬의 표현(|V|x|V|)
vector<bool> visited(V_size, false);
 
void dfs(int here) {
    cout << "VISIT : " << here << '\n';
    visited[here] = true;         //방문 표시
    for (int i = 0; i < V_size; i++) {
        if (adjacent[here][i] != 0 && !visited[i])
            dfs(i);
    }
}
 
void dfsAll(){ //모든 정점에 대해서 dfs수행을 합니다.
/*
그래프가 여러개 일 수 있으므로 모든 정점에 대해 수행하여야 합니다.
*/
    visited = vector<bool>(V_size,false);
    for(int i = 0; i < V_size; i++){
        if(!visited[i])
            dfs(i);
    }
}
 

코드에서 보면 here라는 현재 정점 기준으로 만들어진 DFS spanning tree의 모든 depth를 살펴본 후 dfs(here)는 종료되게 됩니다.

그런데 dfs(here)가 종료되기 전에 모든 depth를 살펴보던 도중 here라는 정점에 도달하게 되면 이는 역방향 간선을 의미합니다.

즉, dfs(here)가 종료되기 전에 here에 재방문 하는 일이 생기면 싸이클이 존재한다는 것입니다.

DFS를 이용한 싸이클 존재 여부확인

dfs(u) 가 종료되기 전에 u 를 재방문 하면 싸이클이 존재한다.

따라서 이를 바탕으로 다시 구현하면 아래와 같습니다.

#include<iostream>
#include<vector>
using namespace std;
 
int V_size;
vector< vector<int> > adjacent;
vector<bool> visited(V_size, false);
vector<bool> finished(V_size, false);
bool haveCycle = false;
 
void dfs(int here) {
    visited[here] = true;         //방문 표시
    for (int i = 0; i < V_size; i++) {
        if (adjacent[here][i] != 0){
            if(!visited[i])
                dfs(i);
            else if(!finished[i])
                haveCycle = true;
        }
    }
    finished[here] = true;
}
 

---

이번 글에서는 간선의 분류와 싸이클 검출에 대해 알아보았습니다.

질문이 있으시거나, 잘못된 내용을 발견하시면 댓글 남겨주시면 답변드리겠습니다.

감사합니다.