자바 - DFS(Depth First Search) 구현

1.이해

예를 들어서 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

 

모든 노드를 방문하고자 하는 경우에 DFS 알고리즘을 이용하면 된다.

 

또한 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 다소 느리다.

 

 

 

DFS

그림과 같이 12에서 13 -> 12로 돌아와 가지 않았던 길이 있는지 파악후 14로 이동한다.

 

 

 

 

 

2.구현코드

일단 정점과 간선을 표현해야 한다. 

대표적으로 2가지 방법이 존재한다.

• 인접행렬 - 2차원 배열로 표현
• 인접리스트 - 배열안에 list 만들어 표현

우리가 구현한 소스에서는 인접리스트로 만들어 볼것이다.

---

 

 

 

노드를 구성하는 코드

class Graph{
	
	class Node{
		int data; 
		LinkedList<Node> adj;
		boolean marked;
		
		public Node(int data ) {
			this.data = data;
			this.marked  = false;
			adj = new LinkedList<Node>();
		}
	}
    
	Node[] nodes; 
	
	Graph(int size) {
		nodes =new Node[size];
		for (int i = 0; i < size; i++) {
			nodes[i] = new Node(i);
		}
	}
    
	void anddEdge(int i1 , int i2){
		Node n1 = nodes[i1];
		Node n2 = nodes[i2];
		if(!n1.adj.contains(n2)){
			n1.adj.add(n2);
		}
		if(!n2.adj.contains(n1)){
			n2.adj.add(n1);
		}
	}

 

DFS 구현

	void dfs(){ //인자없이 호출한다면 0이 기준
		dfs(0);
	}
	
	void dfs(int index) {
		Node root = nodes[index];
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		root.marked = true;
		
		while (!stack.isEmpty()) {
			Node r = stack.pop();
			for (Node n : r.adj) {
				if(n.marked == false){
					n.marked = true;
					stack.push(n);
				}
			}
			visit(r);
		}
	}

 

실행

public class L_43165 {
	public static void main(String[] args) {
		Graph g = new Graph(6);
		g.anddEdge(0, 1);
		g.anddEdge(0, 2);
		g.anddEdge(1, 3);
		g.anddEdge(1, 4);
		g.anddEdge(2, 5);
		
		g.dfs(0);
	}
}

 

결과

0 2 5 1 4 3 

 

 

 

 

 

---

또 다른 사람의 풀이

 

public class L_43165 {
	private int V; //노드 갯수	
	private LinkedList<Integer> adj[]; //인접리스트
	
	public L_43165(int v){
		V = v;
		adj = new LinkedList[v];
		
		for (int i = 0; i < v; i++) { // 인접리스트 초기화
			adj[i] = new LinkedList<>();
		}
	}
	
	void addEdge(int v , int w){ //노드를 연결
		adj[v].add(w);
	}
	
	
	
	void DFSUtil(int v , boolean visited[]){
		visited[v] = true ;
		System.out.println(v + " ");
		
		Iterator<Integer> i = adj[v].listIterator();
		while(i.hasNext()) {
			int n= i.next();
			if(!visited[n]){
				DFSUtil(n, visited);
			}
		}
	}
	
	void DFS(int v) {
		boolean visited[] = new boolean[V];
		DFSUtil(v, visited);
	}
	
	void DFS(){
		boolean visited[] = new boolean[V];
		
		//비연결형 그래프의 경우 모든 정점을 하나씩 방문
		for (int i = 0; i < visited.length; i++) {
			if(visited[i] == false) {
				DFSUtil(i, visited);
			}
		}
	}
	
	public static void main(String[] args) {	
		L_43165 l = new L_43165(6);
		l.addEdge(0, 1);
		l.addEdge(0, 2);
		l.addEdge(1, 3);
		l.addEdge(1, 4);
		l.addEdge(2, 5);
		
		l.DFS();
	}

}