[JAVA] 깊이 우선 탐색 (DFS)

[JAVA] 깊이 우선 탐색 (DFS)

깊이 우선 탐색은 한 그래프의 정점들을 유용한 순서로 방문하는 한 방법이다

주어진 그래프의 한 정점에서 탐색을 시작하여 그 정점을 방문했다고 표시하고,

그 정점에 인접한 정점들 중 방문 안한 정점을 임의로 선택하여 방문한다

선택된 정점에 대해 같은 탐색과정을 반복한다.

더 이상 방문하지않은 인접한 정점이 없으면 바로 전에 방문했던 정점으로 돌아간다.

탐색을 반복하다가 시작 정점으로 돌아간 후 그 시작 정점에 인접한 정점들 중 방문하지 않은 정점이 없으면 종료한다.

시간복잡도

- 인접 리스트: O(V^2)

- 인접 행렬: O(V+E)

알고리즘

알고리즘 DFSearch(G) 1 V에 있는 각 정점을 '방문 안함'으로 표시한다. 2 각 정점 v에 대해 v가 '방문 안함'으로 표시되어 있다면 DFS(v)를 호출한다 DFS(v) 1 v의 데이터를 출력한다 2 v를 '방문함'으로 표시한다. 3 v에 인접한 모든 정점 w에 대해 w가 '방문 안함'으로 표시되어 있다면 DFS(w)를 호출한다

JAVA

import java.util.ArrayList; import java.util.List; class Node { int info; boolean visited; List neighbors; public Node(int info) { this.info = info; this.visited = false; this.neighbors = new ArrayList<>(); } public void addNeighbors(Node neighborsNode) { this.neighbors.add(neighborsNode); } public List getNeighbors() { return neighbors; } public void setNeighbors(List neighbors) { this.neighbors = neighbors; } public String toString() { return "" + info; } } public class DepthFirstSearch { public static void DFS(Node v) { System.out.print(v.info + " "); v.visited = true; List neighbors = v.getNeighbors(); for (int i = 0; i < neighbors.size(); i++) { Node w = neighbors.get(i); if (w != null && !w.visited) DFS(w); } } public static void main(String[] args) { Node[] node = new Node[6]; for (int i = 0; i < 6; i++) { node[i] = new Node(i + 1); } node[0].addNeighbors(node[1]); node[0].addNeighbors(node[2]); node[0].addNeighbors(node[4]); node[1].addNeighbors(node[0]); node[1].addNeighbors(node[2]); node[2].addNeighbors(node[0]); node[2].addNeighbors(node[1]); node[2].addNeighbors(node[3]); node[2].addNeighbors(node[4]); node[3].addNeighbors(node[2]); node[3].addNeighbors(node[5]); node[4].addNeighbors(node[0]); node[4].addNeighbors(node[2]); node[5].addNeighbors(node[2]); node[5].addNeighbors(node[3]); System.out.println("재귀를 사용한 깊이 우선 탐색 실행 결과"); DFS(node[0]); } }

from http://pekahblog.tistory.com/183 by ccl(S) rewrite - 2021-12-13 04:02:15