DFS 스패닝 트리 간선의 분류

출처: 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 2권

DFS 스패닝 트리 간선의 분류

 

   (0에서 출발하여 DFS 탐색을 했을경우)

• 트리 간선(tree edge): 굵은 선 즉, 실제로 방문을 할 때 쓰인 간선
• 순방향 간선(forward edge): 부모에서 자식으로 연결된 간선이지만 쓰인 간선은 아닌 간선 (ex (0->6))
• 역방향 간선(back edge): 자식에서 부모로 연결된 간선 (ex (2->0))
• 교차 간선(cross edge): 위 3가지에 속하지 않는 간선들 (ex (6->3))
                               (무향그래프에서는 교차간선 이 존재할 수 없다.)

 

<간선의 종류를 알 수 있는 소스>

[-] Collapse

#include<vector>
#include<iostream>
using namespace std;

vector<vector<int> > adj;

vector<int> discovered, finished;

int counter;

void dfs2(int here) {
    discovered[here] = counter++;
    for (int i = 0; i < adj[here].size(); i++){
        int there = adj[here][i];
        cout << "(" << here << "," << there << ") is a ";

        if (discovered[there] == -1) {
            cout << "tree edge" << endl;
            dfs2(there);
        }
        else if (discovered[here] < discovered[there])
            cout << "forward edge" << endl;

        else if (finished[there] == 0)
            cout << "back edge" << endl;

        else
            cout << "cross edge" << endl;
    }
    finished[here] = 1;
}
int main(){
    adj = vector<vector<int> >(7);
    discovered = vector<int>(7, -1);
    finished = vector<int>(7);
    //간선 추가
    adj[0].push_back(1), adj[0].push_back(4), adj[0].push_back(5), adj[0].push_back(6);
    adj[1].push_back(2);
    adj[2].push_back(0);
    adj[4].push_back(2);
    adj[5].push_back(3), adj[5].push_back(6);
    adj[6].push_back(3);
    //0에서 시작.
    dfs2(0);

    return 0;
}