알고리즘) DFS [깊이 우선 탐색] 간단정리

 

• 정의

• 하나의 정점으로부터 시작, 차례대로 모든 정점을 한 번씩 방문.
• 다음 분기로 넘어가기 전에 해당 분기를 완벽히 탐색한다.
• 맹목적 탐색의 방법, 모든 노드를 방문

• 특징

• 자기자신을 호출하는 순환 알고리즘의 형태
• 한 번씩만 방문하는것이기 때문에 방문한 노드인지 검사하는 과정 필요
• 탐색과정에서 깊이제한, 부모노드로 다시 돌아오는 백트래킹.

• 구현

• 인접행렬 혹은 인접 리스트로 구현가능.
• 재귀 호출 혹은 스택을 이용하여 구현.

 

• 인접 리스트를 이용하여 코드 구현

public class Dfs {
	private int V;
	private LinkedList<Integer> adj[];
	
	public Dfs(int v) {
		this.V = v+1;
		adj = new LinkedList[V];
		
		for(int i = 1 ; i <= v; i++ ) {
			adj[i] = new LinkedList();
		}
	}
	
	public void addEdge(int v, int w) {
		adj[v].add(w);
		adj[w].add(v);
	}
	
	public void DfsR(int v, boolean visited[]) {
		visited[v] = true;
		System.out.println(v+" ");
		
		Iterator<Integer> iter = adj[v].iterator();
		while(iter.hasNext()) {
			int n = iter.next();
			if(!visited[n]) {
				visited[n] = true;
				DfsR(n, visited);
			}
		}
	}
	
	public void DFS(int v) {
		boolean[] visited = new boolean [V];
		
		DfsR(v, visited);
	}
}