DFS - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:20:15Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:20 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Graph#Graph Traversal\|Graph]]		상위 문서: [[Graph#Graph Traversal\|Graph]]

Pinkgo: /* Strongly Connected Components */

2025-11-17T11:56:31Z

Strongly Connected Components

← 이전 판		2025년 11월 17일 (월) 11:56 판
137번째 줄:		137번째 줄:
	# 1차 DFS on G: G에 대해 DFS를 수행하고, 각 정점의 완료 순서를 스택에 저장.		# 1차 DFS on G: G에 대해 DFS를 수행하고, 각 정점의 완료 순서를 스택에 저장.
	# Transpose Graph G<sup>t</sup> 생성: 모든 간선의 방향을 뒤집는다.		# Transpose Graph G<sup>t</sup> 생성: 모든 간선의 방향을 뒤집는다.
	# 2차 DFS on G<sup>t</sup>: 스택의 “가장 나중에 완료된 ~~정점”부터~~ DFS 시작.		# 2차 DFS on G<sup>t</sup>: 스택의 “가장 나중에 완료된 정점”<ref>Figure를 기준으로는 1번 정점에 해당한다. 8번 정점은 가장 나중에 완료되었다.</ref>부터 DFS 시작.
	마지막 단계를 거친 후, 각 DFS 탐색이 하나의 SCC가 된다. 따라서 해당 알고리즘의 시간 복잡도는 O(V + E)(정점 + 간선 수에 선형 비례)이므로 매우 효율적이다.		마지막 단계를 거친 후, 각 DFS 탐색이 하나의 SCC가 된다. 따라서 해당 알고리즘의 시간 복잡도는 O(V + E)(정점 + 간선 수에 선형 비례)이므로 매우 효율적이다.

	==각주==		==각주==

Pinkgo: /* Strongly Connected Components */

2025-11-17T11:43:06Z

Strongly Connected Components

← 이전 판		2025년 11월 17일 (월) 11:43 판
135번째 줄:		135번째 줄:
	[[파일:Figure 5. Finding SCC with DFS.png\|섬네일\|300x300픽셀\|Figure 5. Finding SCC with DFS]]		[[파일:Figure 5. Finding SCC with DFS.png\|섬네일\|300x300픽셀\|Figure 5. Finding SCC with DFS]]
	가장 널리 쓰이는 SCC를 찾는 알고리즘은 DFS 기반의 Kosaraju’s Algorithm이다. 이는 figure 5에 그 양상이 나타나 있다. Kosaraju’s Algorithm은 아래와 같은 과정을 통해서 SCC를 찾는다.:		가장 널리 쓰이는 SCC를 찾는 알고리즘은 DFS 기반의 Kosaraju’s Algorithm이다. 이는 figure 5에 그 양상이 나타나 있다. Kosaraju’s Algorithm은 아래와 같은 과정을 통해서 SCC를 찾는다.:
	# 1차 DFS on G: ~~모든 정점에~~ 대해 DFS를 수행하고, 각 정점의 완료 순서를 스택에 저장.		# 1차 DFS on G: G에 대해 DFS를 수행하고, 각 정점의 완료 순서를 스택에 저장.
	# Transpose Graph G<sup>t</sup> 생성: 모든 간선의 방향을 뒤집는다.		# Transpose Graph G<sup>t</sup> 생성: 모든 간선의 방향을 뒤집는다.
	# 2차 DFS on G<sup>t</sup>: 스택의 “가장 나중에 완료된 정점”부터 DFS 시작.		# 2차 DFS on G<sup>t</sup>: 스택의 “가장 나중에 완료된 정점”부터 DFS 시작.

Pinkgo: /* Articulation Vertices */

2025-11-17T10:58:05Z

Articulation Vertices

← 이전 판		2025년 11월 17일 (월) 10:58 판
120번째 줄:		120번째 줄:
	# v의 모든 서브 트리가 v의 조상(ancestor)으로 연결되는 Back Edge를 가지지 않아야 한다.		# v의 모든 서브 트리가 v의 조상(ancestor)으로 연결되는 Back Edge를 가지지 않아야 한다.
	[[파일:Figure 4. A Faster DFS Algorithm.png\|섬네일\|200x200픽셀\|Figure 4. A Faster DFS Algorithm]]		[[파일:Figure 4. A Faster DFS Algorithm.png\|섬네일\|200x200픽셀\|Figure 4. A Faster DFS Algorithm]]
	위는 v의 서브트리가 ~~완전히~~ v에 ~~의존하고 있다면~~, ~~v를 지우면 그 부분이 고립된다는 것을 의미한다~~. ~~Figure 4는 이를 잘 보여주는데~~, ~~아래는 figure 4에 대한 설명이다:~~		Figure 4는 특정 노드 v의 서브트리가 얼마나 v에 의존하는지, 그리고 그로 인해 어떤 노드들이 단절점(articulation point) 이 되는지를 시각적으로 보여주는 그림이다. 즉, v 또는 특정 조상 노드를 제거했을 때 그래프가 어떻게 분리되는지를 나타낸 예시이다.
	# root cutnode(빨간색): DFS 트리의 루트가 여러 서브트리를 ~~가진다면~~, ~~그것도 단절점~~.		# root cutnode(빨간색): DFS 트리의 루트가 여러 개의 독립된 서브트리를 가지고 있다면, 루트를 제거하는 순간 이 서브트리들이 서로 완전히 분리된다. 따라서 루트 역시 단절점이 될 수 있음을 보여준다.
	# bridge cutnode(파란색): ~~서브트리가~~ 다른 ~~조상과 연결되지 않는~~ 경우.		# bridge cutnode(파란색): 파란 노드 아래에 있는 서브트리는 다른 조상 노드로 이어지는 back-edge가 전혀 없다. 즉, 이 서브트리는 해당 노드에 100% 의존해서만 그래프의 나머지 부분과 연결된다. 이런 경우 그 노드는 bridge(단절 간선)의 한쪽 끝점이며, 그 자체도 단절점이 된다.
	# parent cutnode(초록색): v의 ~~부모가 단절점일~~ 수 ~~있는 조건을 만족~~.		# parent cutnode(초록색): 특정 노드 v의 부모 노드가, v의 서브트리가 갖는 low-link 값 때문에 단절점 조건을 만족할 수 있음을 보여주는 예시다. 즉, 부모를 제거하면 v와 그 하위 서브트리 전체가 고립되므로 부모도 articulation point가 된다.
			이처럼 Figure 4는 v를 포함한 여러 서브트리가 어떻게 특정 노드에 구조적으로 의존하는지를 나타내며, 그 결과 어떤 노드들이 단절점이 되는지를 이해하기 쉽게 보여주는 그림이다.

	==Applications of DFS==		==Applications of DFS==

2025년 10월 16일 (목) 06:11에 Pinkgo님의 편집

2025-10-16T06:11:49Z

← 이전 판		2025년 10월 16일 (목) 06:11 판
63번째 줄:		63번째 줄:

	==DFS with Graph==		==DFS with Graph==
			[[파일:Figure 1. Graph to DFS tree.png\|섬네일\|Figure 1. Graph to DFS tree]]
	DFS 알고리즘은 탐색하는 그래프의 간선들의 구조를 조직화한다. DFS를 수행하면 그래프의 모든 간선이 “방문 순서”에 따라 방향성을 가진다. 즉, undirected 그래프를 탐색하더라도 “어떤 정점이 다른 정점을 처음 발견했는가”에 따라 간선의 방향이 결정된다. Figure 1은 원래의 undirected 그래프로부터 DFS 알고리즘을 수행하여 DFS 트리 자료구조를 만드는 것을 보여준다.		DFS 알고리즘은 탐색하는 그래프의 간선들의 구조를 조직화한다. DFS를 수행하면 그래프의 모든 간선이 “방문 순서”에 따라 방향성을 가진다. 즉, undirected 그래프를 탐색하더라도 “어떤 정점이 다른 정점을 처음 발견했는가”에 따라 간선의 방향이 결정된다. Figure 1은 원래의 undirected 그래프로부터 DFS 알고리즘을 수행하여 DFS 트리 자료구조를 만드는 것을 보여준다.

	===Edge Classification for DFS===		===Edge Classification for DFS===
			[[파일:Figure 2. Edge Classification for DFS.png\|섬네일\|Figure 2. Edge Classification for DFS]]
	DFS 알고리즘을 실행하여 어떤 그래프를 탐색하는 과정에서 탐색하는 그래프의 간선들은 아래와 같이 4가지로 분류된다:		DFS 알고리즘을 실행하여 어떤 그래프를 탐색하는 과정에서 탐색하는 그래프의 간선들은 아래와 같이 4가지로 분류된다:
	# Tree Edge: DFS 트리에서 새 정점을 발견하는 간선(해당 간선의 집합은 DFS 트리를 구성)		# Tree Edge: DFS 트리에서 새 정점을 발견하는 간선(해당 간선의 집합은 DFS 트리를 구성)
107번째 줄:		109번째 줄:

	===Articulation Vertices===		===Articulation Vertices===
			[[파일:Figure 3. Articulation Vertices.png\|섬네일\|Figure 3. Articulation Vertices]]
	Articulation Vertices 문제는 “어떤 노드를 제거하면 그래프가 분리되는가?”를 찾는 문제이다. 단절점(Articulation Vertex)란 특정 정점을 삭제했을 때 그래프가 둘 이상으로 분리되는 정점을 의미한다. Figure 3에서는 빨간색 정점이 단절점이며, 그 정점을 지우면 그래프가 왼쪽(파란 부분)과 오른쪽(초록 부분)으로 분리된다. 단절점 문제를 해결하는 가장 단순한 방법은 모든 정점에 대해 다음을 반복하는 것이다:		Articulation Vertices 문제는 “어떤 노드를 제거하면 그래프가 분리되는가?”를 찾는 문제이다. 단절점(Articulation Vertex)란 특정 정점을 삭제했을 때 그래프가 둘 이상으로 분리되는 정점을 의미한다. Figure 3에서는 빨간색 정점이 단절점이며, 그 정점을 지우면 그래프가 왼쪽(파란 부분)과 오른쪽(초록 부분)으로 분리된다. 단절점 문제를 해결하는 가장 단순한 방법은 모든 정점에 대해 다음을 반복하는 것이다:
	# 해당 정점을 제거한다.		# 해당 정점을 제거한다.
116번째 줄:		119번째 줄:
	# v는 루트가 아닌 정점이고,		# v는 루트가 아닌 정점이고,
	# v의 모든 서브 트리가 v의 조상(ancestor)으로 연결되는 Back Edge를 가지지 않아야 한다.		# v의 모든 서브 트리가 v의 조상(ancestor)으로 연결되는 Back Edge를 가지지 않아야 한다.
			[[파일:Figure 4. A Faster DFS Algorithm.png\|섬네일\|200x200픽셀\|Figure 4. A Faster DFS Algorithm]]
	위는 v의 서브트리가 완전히 v에 의존하고 있다면, v를 지우면 그 부분이 고립된다는 것을 의미한다. Figure 4는 이를 잘 보여주는데, 아래는 figure 4에 대한 설명이다:		위는 v의 서브트리가 완전히 v에 의존하고 있다면, v를 지우면 그 부분이 고립된다는 것을 의미한다. Figure 4는 이를 잘 보여주는데, 아래는 figure 4에 대한 설명이다:
	# root cutnode(빨간색): DFS 트리의 루트가 여러 서브트리를 가진다면, 그것도 단절점.		# root cutnode(빨간색): DFS 트리의 루트가 여러 서브트리를 가진다면, 그것도 단절점.
128번째 줄:		132번째 줄:
	===Strongly Connected Components===		===Strongly Connected Components===
	어떤 방향 그래프(directed graph) 가 strongly connected하다는 것은 모든 정점 쌍 (u, v)에 대해, u → v 경로와 v → u 경로가 모두 존재한다는 뜻이다. 이때 어떤 그래프의 SCC(Strongly Connected Component)란 그래프에 존재하는 strongly connected된 각 그룹들을 의미한다. 이때 SCC는 더 이상 합칠 수 없는 최대 단위로, Maximal subset이라고 볼 수 있다. 이에 따라 그래프의 모든 정점은 정확히 하나의 SCC에만 속하며, SCC들은 그래프의 정점을 서로 겹치지 않게 분할(partition) 한다.		어떤 방향 그래프(directed graph) 가 strongly connected하다는 것은 모든 정점 쌍 (u, v)에 대해, u → v 경로와 v → u 경로가 모두 존재한다는 뜻이다. 이때 어떤 그래프의 SCC(Strongly Connected Component)란 그래프에 존재하는 strongly connected된 각 그룹들을 의미한다. 이때 SCC는 더 이상 합칠 수 없는 최대 단위로, Maximal subset이라고 볼 수 있다. 이에 따라 그래프의 모든 정점은 정확히 하나의 SCC에만 속하며, SCC들은 그래프의 정점을 서로 겹치지 않게 분할(partition) 한다.
			[[파일:Figure 5. Finding SCC with DFS.png\|섬네일\|300x300픽셀\|Figure 5. Finding SCC with DFS]]
	가장 널리 쓰이는 SCC를 찾는 알고리즘은 DFS 기반의 Kosaraju’s Algorithm이다. 이는 figure 에 그 양상이 나타나 있다. Kosaraju’s Algorithm은 아래와 같은 과정을 통해서 SCC를 찾는다.:		가장 널리 쓰이는 SCC를 찾는 알고리즘은 DFS 기반의 Kosaraju’s Algorithm이다. 이는 figure 5에 그 양상이 나타나 있다. Kosaraju’s Algorithm은 아래와 같은 과정을 통해서 SCC를 찾는다.:
	# 1차 DFS on G: 모든 정점에 대해 DFS를 수행하고, 각 정점의 완료 순서를 스택에 저장.		# 1차 DFS on G: 모든 정점에 대해 DFS를 수행하고, 각 정점의 완료 순서를 스택에 저장.
	# Transpose Graph G<sup>t</sup> 생성: 모든 간선의 방향을 뒤집는다.		# Transpose Graph G<sup>t</sup> 생성: 모든 간선의 방향을 뒤집는다.

Pinkgo: /* Analyzing Graph with DFS */

2025-10-16T06:04:44Z

Analyzing Graph with DFS

@@ 88번째 줄: / 88번째 줄: @@
 * Cycle Detection: 그래프에 cycle이 존재하는가를 판별.
 * Articulation Vertices: 어떤 노드를 제거하면 그래프가 별개의 그래프들로 구분되는지.
 ===Finding Cycles===
@@ 120번째 줄: / 105번째 줄: @@
 </syntaxhighlight>
 위 코드에서 y가 x의 부모 노드가 아니라면 이는 back edge이므로<ref>이때 x와 y 사이의 간선이 처리되지 않았으므로 당연히 processed[y] == false이다.</ref> 이에 따라 사이클이 발견되었음을 출력한다. 또한 find_path() 함수가 활용되었는데, 이는 DFS 트리 상에서 y에서 x로 이어지는 경로를 따라가며 출력하는 역할을 한다. 그리고 cycle을 이미 찾았으므로, finished 변수를 true로 만들어 탐색을 종료한다.
 ==Applications of DFS==

Pinkgo: /* Applications of DFS */

2025-10-16T06:04:02Z

Applications of DFS

← 이전 판		2025년 10월 16일 (목) 06:04 판
84번째 줄:		84번째 줄:
	이때 DFS가 undirected 그래프를 탐색하는 경우, forward/cross edges는 존재하지 않는다.		이때 DFS가 undirected 그래프를 탐색하는 경우, forward/cross edges는 존재하지 않는다.

	==~~Applications of~~ DFS==		==Analyzing Graph with DFS==
	DFS는 단순히 “모든 노드를 탐색하는 알고리즘”에 그치지 않고, 그래프의 구조적 특성을 분석하는 도구로서 매우 강력하게 활용된다. 특히 Cycle Detection 문제와 Articulation Vertices 문제를 해결하는데에 자주 사용된다:		DFS는 단순히 “모든 노드를 탐색하는 알고리즘”에 그치지 않고, 그래프의 구조적 특성을 분석하는 도구로서 매우 강력하게 활용된다. 특히 Cycle Detection 문제와 Articulation Vertices 문제를 해결하는데에 자주 사용된다:
	* Cycle Detection: 그래프에 cycle이 존재하는가를 판별.		* Cycle Detection: 그래프에 cycle이 존재하는가를 판별.
	* Articulation Vertices: 어떤 노드를 제거하면 그래프가 별개의 그래프들로 구분되는지.		* Articulation Vertices: 어떤 노드를 제거하면 그래프가 별개의 그래프들로 구분되는지.

			===Articulation Vertices===
			Articulation Vertices 문제는 “어떤 노드를 제거하면 그래프가 분리되는가?”를 찾는 문제이다. 단절점(Articulation Vertex)란 특정 정점을 삭제했을 때 그래프가 둘 이상으로 분리되는 정점을 의미한다. Figure 3에서는 빨간색 정점이 단절점이며, 그 정점을 지우면 그래프가 왼쪽(파란 부분)과 오른쪽(초록 부분)으로 분리된다. 단절점 문제를 해결하는 가장 단순한 방법은 모든 정점에 대해 다음을 반복하는 것이다:
			# 해당 정점을 제거한다.
			# 남은 그래프에 DFS 또는 BFS를 수행한다.
			# 그래프가 여전히 연결되어 있는지 확인한다.
			위 알고리즘의 시간 복잡도는 정점의 개수가 n, 간선의 개수가 m일 때 정점을 하나 제거할 때마다 DFS를 한번 수행하므로 O(n × (m + n))이다. 이는 느리지만 개념적으로 articulation vertex의 정의를 충실히 따르는 방법이다.

			하지만, 이보다 더욱 빠르게 단절점을 탐색하는 알고리즘이 존재한다. 이 알고리즘은 Tarjan’s Algorithm으로, 한 번의 DFS 탐색 중에 단절점을 판별하는 방식이다. 이에 따라 O(n + m)의 시간복잡도를 가진다. Tarjan’s Algorithm의 핵심아이디어는 DFS 트리에서, 어떤 정점 v가 다음 조건을 만족하면 단절점이라는 것이다:
			# v는 루트가 아닌 정점이고,
			# v의 모든 서브 트리가 v의 조상(ancestor)으로 연결되는 Back Edge를 가지지 않아야 한다.
			위는 v의 서브트리가 완전히 v에 의존하고 있다면, v를 지우면 그 부분이 고립된다는 것을 의미한다. Figure 4는 이를 잘 보여주는데, 아래는 figure 4에 대한 설명이다:
			# root cutnode(빨간색): DFS 트리의 루트가 여러 서브트리를 가진다면, 그것도 단절점.
			# bridge cutnode(파란색): 서브트리가 다른 조상과 연결되지 않는 경우.
			# parent cutnode(초록색): v의 부모가 단절점일 수 있는 조건을 만족.

	===Finding Cycles===		===Finding Cycles===
105번째 줄:		120번째 줄:
	</syntaxhighlight>		</syntaxhighlight>
	위 코드에서 y가 x의 부모 노드가 아니라면 이는 back edge이므로<ref>이때 x와 y 사이의 간선이 처리되지 않았으므로 당연히 processed[y] == false이다.</ref> 이에 따라 사이클이 발견되었음을 출력한다. 또한 find_path() 함수가 활용되었는데, 이는 DFS 트리 상에서 y에서 x로 이어지는 경로를 따라가며 출력하는 역할을 한다. 그리고 cycle을 이미 찾았으므로, finished 변수를 true로 만들어 탐색을 종료한다.		위 코드에서 y가 x의 부모 노드가 아니라면 이는 back edge이므로<ref>이때 x와 y 사이의 간선이 처리되지 않았으므로 당연히 processed[y] == false이다.</ref> 이에 따라 사이클이 발견되었음을 출력한다. 또한 find_path() 함수가 활용되었는데, 이는 DFS 트리 상에서 y에서 x로 이어지는 경로를 따라가며 출력하는 역할을 한다. 그리고 cycle을 이미 찾았으므로, finished 변수를 true로 만들어 탐색을 종료한다.

			==Applications of DFS==

	===[[Topological Sorting]]===		===[[Topological Sorting]]===

Pinkgo: /* Articulation Vertices */

2025-10-16T06:03:27Z

Articulation Vertices

@@ 117번째 줄: / 117번째 줄: @@
 # 2차 DFS on G<sup>t</sup>: 스택의 “가장 나중에 완료된 정점”부터 DFS 시작.
 마지막 단계를 거친 후, 각 DFS 탐색이 하나의 SCC가 된다. 따라서 해당 알고리즘의 시간 복잡도는 O(V + E)(정점 + 간선 수에 선형 비례)이므로 매우 효율적이다.
 ==각주==

Pinkgo: /* Finding Cycles */

2025-10-16T06:02:50Z

Finding Cycles

@@ 105번째 줄: / 105번째 줄: @@
 </syntaxhighlight>
 위 코드에서 y가 x의 부모 노드가 아니라면 이는 back edge이므로<ref>이때 x와 y 사이의 간선이 처리되지 않았으므로 당연히 processed[y] == false이다.</ref> 이에 따라 사이클이 발견되었음을 출력한다. 또한 find_path() 함수가 활용되었는데, 이는 DFS 트리 상에서 y에서 x로 이어지는 경로를 따라가며 출력하는 역할을 한다. 그리고 cycle을 이미 찾았으므로, finished 변수를 true로 만들어 탐색을 종료한다.
 ===Articulation Vertices===

2025년 10월 16일 (목) 05:10에 Pinkgo님의 편집

2025-10-16T05:10:27Z

← 이전 판		2025년 10월 16일 (목) 05:10 판
1번째 줄:		1번째 줄:
	[[분류:알고리즘 설계와 분석]]		[[분류:알고리즘 설계와 분석]]
	[[분류:컴퓨터 공학]]		[[분류:컴퓨터 공학]]
	상위 문서: [[Graph\|~~알고리즘 설계와 분석~~]]		상위 문서: [[Graph#Graph Traversal\|Graph]]

	==개요==		==개요==