깊이 우선 탐색(Depth-First Search, DFS)

Subgraph(부분그래프)

그래프 G의 부분 그래프 S가 있다고 가정하자. 이 때,

- S의 정점은 G의 정점의 부분집합이다.

- S의 간선은 G의 간선의 부분집합이다.

Spanning subgraph

- G의 스패닝 서브그래프는 G의 모든 정점은 포함하지만, 모든 간선은 포함하지 않는 서브 그래프이다.

 

Connectivity(연결성)

- 모든 정점 쌍 사이에 경로가 있는 경우 그래프가 연결된다.

- 그래프 G의 연결된 구성 요소는 G의 최대 연결 부분 그래프이다.

- 정점을 추가해도 connective 그래프가 된다면, connected component가 아니다.

Tree & Forest

트리는 다음 속성을 가지는 undirected 그래프이다.

- 트리 T는 연결되어있다.

- 트리 T는 사이클이 없다.

포레스트는 사이클이 없는 undirected 그래프이다.

- 포레스트의 connected components는 트리이다.

 

Spanning Tree는 주어진 그래프에서 유일하지 않을 수 있다. 하지만 Tree 형태의 그래프로 주어진다면 Spanning Tree는 유일하게 존재하게 된다. 또한 스패닝 트리는 통신 네트워크 설계에 유용하게 사용된다.

 

Depth-First Search(깊이 우선 탐색)

DFS는 그래프를 순회하는 일반적인 기법이다.

- G의 모든 정점과 간선을 탐색한다.

- G가 연결되었는지 여부를 결정한다.

- G의 연결된 컴포넌트를 계산한다.

- G의 스패닝 포레스트를 계산한다.

- n개의 정점과 m개의 간선이 존재하는 그래프의 DFS는 O(n+m)시간이 걸린다. (인접 리스트로 구현했을 때 걸리는 시간)

- 깊이 우선 탐색은 미로 , 길찾기 등 문제 해결에 많이 사용되며, 이진 트리에 대한 오일러 순회가 무엇인지를 그래프로 표시하는 것이다.

 

DFS 알고리즘은 정점과 간선의 "labels"을 설정하고 얻기 위한 메커니즘을 사용한다.

Algorithm DFS(G)
	Input graph G
    Output labeling of the edges of G
    as discovery edges and back edges
    for all u ∈ G.vertices()	// O(n)
    	u.setLabel(UNEXPLORED)
    for all e ∈ G.edges()		// O(n+m)
    	e.setLabel(UNEXPLORED)
    for all v ∈ G.vertices()
    	if v.getLabel() == UNEXPLORED
        	DFS(G,v)
            
Algorithm DFS(G,v)
	Input graph G and a start vertex v of G
    Output labeling of t he edges of G
    in the connected component of v
    as discovery edges and back edges
    v.setLabel(VISITED)
    for all e ∈ G.incidentEdges(v)
    	if e.getLabel() == UNEXPLORED
        	w<- e.opposite(v)
            if w.getLabel() == UNEXPLORED
            	e.setLabel(DISCOVERY)
                DFS(G,w)
            else
            	e.setLabel(BACK)

DFS 알고리즘은 미로를 탐색하는 전략과 유사하다.

- 방문한 각 교차로,코너 및 막다른 골목(정점)을 표시한다.

- 순회된 각 간선을 표시한다.

- 재귀 스택을 이용하여 시작 정점으로 돌아가는 경로를 추적한다.

 

DFS 속성

1. DFS(G,v)는 v와 연결된 구성 요소의 모든 정점과 간선을 방문한다.

2. DFS(G,v)로 label이 지정된 탐색 간선은 v와 연결된 구성 요소에 스패닝 트리를 형성한다. ( 즉, discovery edge만 모으면 spanning tree가 된다.)

 

Performance(성능)

- 정점과 간선의 label(탐사 여부)를 설정하고 확인하는 데에 O(1) 시간이 걸린다.

- 각 정점은 두번의 label이 발생 ( 한번은 UNEXPLORED , 한번은 VISITED )

- 각 간선은 두번의 label이 발생 ( 한번은 UNEXPLORED , 한번은 DISCOVERY or BACK )

- incidentEdges() 메소드는 각 정점에 대해 한번 호출된다.

- 그래프가 인접 리스트 구조로 나타내는 경우 DFS는 O(n+m) 시간 내에 실행된다.