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

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

---

https://en.wikipedia.org/wiki/Depth-first_search

 

깊이 우선 탐색(depth-first search: DFS)은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다.

 

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

💊 알고리즘 장단점 (Algorithm Advantage/Disadvantage)

😺 장점 (Advantage)	현 경로상의 노드들만을 기억하면 되므로 저장 공간의 수요가 비교적 적다. 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
😿 단점 (Disadvantage)	해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수도 있다.

💊 알고리즘 복잡도 (Algorithm Complcomplexity)

⏰ 시간 복잡도 (Time Complcomplexity)	O (|V| + |E|)
📦 공간 복잡도 (Space Complcomplexity)	O (|V|)

---

📄 [자료구조] Reculsive DFS C++ / Pseudo Source Code

void recalsiveDFS(int index, int length) {
	isVisit[index] = true;
	cout << index << endl;

	for (int ii = 0; ii < length; ii++) {
		if (!isVisit[ii] && vertaxs[index][ii] == 1) { recalsiveDFS(ii, length); }
	}
}

  procedure DFS(G,v):
      label v as discovered
      for all directed edges from v to w that are in G.adjacentEdges(v) do
          if vertex w is not labeled as discovered then
              recursively call DFS(G,w)

---

📄 [자료구조] Stack DFS Mode C++ / Pseudo Source Code

void stackDFS(int index, int length) {
	
	stack<int> stx;

	stx.push(index);
	isVisit[index] = true;

	while (!stx.empty()) {
		
		const int box = stx.top(); stx.pop();

		for (int ii = 0; ii < length; ii++) {
			if (!isVisit[ii] && vertaxs[box][ii] == 1) {
				stx.push(ii);
				isVisit[ii] = true;
			}
		}

		// Output
		cout << box << endl;
	}
}

  procedure DFS-iterative(G,v):
      let S be a stack
      S.push(v)
      while S is not empty
          v = S.pop()
          if v is not labeled as discovered:
              label v as discovered
              for all edges from v to w in G.adjacentEdges(v) do 
                  S.push(w)

---

🚀 REFERENCE

Depth-first search - Wikipedia