DFS트리에서 간선의 종류, 사이클 검출

ㅁ방향그래프

dfs를 수행하면 그래프의 모든 간선을 한 번씩은 만나게 된다.

그래프에서 어떤 점에서 dfs를 수행하면 트리가 만들어지는데, 트리를 중심으로 그래프의 모든 간선의 종류를 구분해보면

 

1. 트리간선

dfs트리를 이루는 간선

2. 순방향 간선

스패닝 트리의 선조에서 자손으로 연결되지만 트리간선이 아닌 간선

3. 역방향 간선

트리의 자손에서 선조로 연결되는 간선. 당연히 트리간선에 포함 안됨.

그래프의 사이클유무 판단할때 사용하는 간선. ( 이 간선이 존재하면 그래프에 사이클 존재 )

4. 교차간선

그 외의 모든 간선. 선조-자손관계가 아닌 정점들 간 연결된 간선.

 

<코드 및 자세한 설명>

vector<int> adj[MAX];
int vst[MAX]; //방문순서 기록. -1이면 방문안된것.
bool fin[MAX];

int counter = 0; //방문순서카운트
void dfs(int u) {
	vst[u] = counter++;
	for (int v : adj[u]) {
		//간선 (u,v)에 대해

		//v를 방문한적 없다면 트리간선. 계속 dfs
		if (vst[v] == -1) dfs(v); 
		else if (vst[u] < vst[v]) {
			//u를 v보다 먼저 방문했다면 v는 u의 후손이다. 순방향간선
		}
		else if (!fin[v]) {
			//단순히 vst로만 비교한다면 교차간선인지 역방향간선인지 판단불가하다.
			//fin배열을 이용해서 교차간선을 찾기 이전에 먼저 역방향간선을 찾아줄 수 있다.
			//v가 아직 탐색할 여지가 있다면, 역방향 간선
		}
		else {
			//그 외의 경우 모두 교차간선
		}
	}
	fin[u] = true;
}

 

 

ㅁ 무향그래프

** 무향그래프에선 교차간선이 없다. 단순히 방문 순서만 놓고 역방향 간선이 있는지 없는지 알 수 있다.

->사이클 검출 가능. (엄밀히 말해선 역방향 간선이 아니다. 무향그래프에선 순방향,역방향 간선의 구분이 없다.)

<코드>

int n, m, vst[MAX], counter=0;
vector<int> adj[MAX];
bool cycle = false;
void dfs(int u, int p) {
	vst[u] = counter++;
	for (int v : adj[u]) {
		if (v == p) continue; 
		if (vst[v] == -1) dfs(v,u);
		else if (vst[u] > vst[v]) cycle = true;
	}
}

 

하지만 https://suuntree.tistory.com/149?category=805933방법이 좀 더 범용적이다.

 

https://jackpot53.tistory.com/92이분처럼 유니온파인드를 사용하기도 한다.