그래프 간선의 분류 간단 정리

참고

https://rebro.kr/71

https://hy38.github.io/about-edges-in-graph

https://bowbowbow.tistory.com/1

https://www.tutorialspoint.com/data_structures_algorithms/spanning_tree.htm

 

설명

아래와 같은 그래프가 있습니다.

출처:https://rebro.kr/71

1번 정점부터 깊이 우선으로 탐색을 시작하면 다음과 같은 스패닝 트리가 나옵니다. 스패닝 트리를 연결하고 있는 간선을 스패닝 트리 간선이라고 합니다. 스패닝 트리에는 순환이 없습니다.

출처:https://rebro.kr/71

 

스패닝 트리는 이미 방문한 노드는 방문하지 않기 때문에 (5, 1), (6, 4), (6, 3), (1, 7) 간선은 스패닝 트리에 포함되지 않습니다. 여기에서 순방향 간선, 역방향 간선, 교차 간선을 알아보겠습니다.

 

1. 순방향 간선

스패닝 트리 간선 포함되지 않으면서 (u, v)일 때 u가 v의 조상인 간선입니다. (1, 7)이 순방향 간선입니다. 코드로 구성할 때 조상/손자를 구분하기 위해 순서를 정하는데요. 순서가 앞서면 조상입니다. 즉 u가 v보다 먼저 방문되어야 합니다. 

 

2. 역방향 간선

스패닝 트리 간선에 포함되지 않으면서 (u, v)일 때 u가 v의 자손이 되는 간선입니다. (5, 1), (6, 3)입니다. 즉, v는 이미 방문된 상태이어야 하는 것이죠. 그러므로 v의 순서가 u보다 빨라야 합니다. v가 조상이니까요. 여기서 중요한 건 v가 아직 탐색이 끝나지 않은 상태여야 합니다. 조상이 어느 순간 어느 정점의 자손이 되는 상황은 순환이 일어난다는 사실을 알려줍니다. 즉, 역방향 간선이 존재하면 순환을 돌게 되는데요, 순환이 일어나려면 v노드가 탐색을 종료하지 않은 상태여야 합니다. 이것이 교차 간선과 구분되는 지점입니다.

 

3. 교차 간선

순방향 간선과 역방향 간선에 해당하지 않으면 교차 간선입니다. 교차 간선 역시 스패닝 트리 간선에 포함되지 않습니다. (6, 4)가 해당되는데요, 순환이 일어나지 않습니다. 4번 정점이 이미 탐색이 끝난 정점이기 때문입니다. 탐색이 끝난 정점에 접근해봤자 순환은 일어나지 않을 것입니다.

 

#include <vector>
#include <cstdio>
std::vector<std::vector<int>> vertices(8);
std::vector<int> visit_order(8); // 방문 순서
std::vector<int> finished(8);	 // 각 정점의 방문 종료
std::vector<std::pair<int, int>> spanning_tree, forward, backward, cross;
int cnt = 1; 
void dfs(int u);

int main()
{
	vertices[1].push_back(2);
	vertices[1].push_back(3);
	vertices[1].push_back(7);

	vertices[2].push_back(5);

	vertices[5].push_back(1);
	vertices[5].push_back(4);

	vertices[3].push_back(7);

	vertices[6].push_back(3);
	vertices[6].push_back(4);

	vertices[7].push_back(6);

	dfs(1);

	printf("Spanning tree\n");
	for (auto [u, v] : spanning_tree)
		printf("(%d, %d)", u, v);
	printf("\n\n");

	printf("Forward edges\n");
	for (auto [u, v] : forward)
		printf("(%d, %d)", u, v);
	printf("\n\n");

	printf("Backward edges\n");
	for (auto [u, v] : backward)
		printf("(%d, %d)", u, v);
	printf("\n\n");

	printf("Cross edges\n");
	for (auto [u, v] : cross)
		printf("(%d, %d)", u, v);
	printf("\n");
}

void dfs(int u)
{
	visit_order[u] = cnt++;
	for (int v : vertices[u])
	{
		if (0 == visit_order[v])
		{
			spanning_tree.push_back({ u, v });
			dfs(v);
		}
		else if (visit_order[u] < visit_order[v])
			forward.push_back({ u, v });
		else if (finished[v] == 0)
			backward.push_back({ u, v });
		else cross.push_back({ u, v });
	}
	finished[u] = 1;
}