[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<Node> 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<Node> getNeighbors() {
		return neighbors;
	}
	
	public void setNeighbors(List<Node> 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<Node> 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]);
	}
}