[중급] DFS와 BFS

DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다.

*탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말함

 

깊이 우선 탐색 DFS(DEPTH - FIRST SEARCH)

: 탐색 노드(루트 노드 or 다른 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

 

DFS 구현 방법

- 재귀함수

- 스택  (되돌아가기 위해 스택 필요)

 

 

1) 재귀함수

-Linkedlist 이용

package dd;
import java.util.*;
public class Main {
	public static void dfs_list(int v,LinkedList<Integer>[] adjList,boolean[] visited)
	{
		visited[v]=true;
		System.out.print(v+" ");
		Iterator<Integer> iter = adjList[v].listIterator(); //정점 인접리스트
		while(iter.hasNext()) {
			int w= iter.next();
			if(!visited[w]) {
				dfs_list(w,adjList,visited);
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(); //정점
		int m=sc.nextInt(); //간선
		int v= sc.nextInt(); //탐색을 시작할 정점의 번호
		boolean visited[] = new boolean[n+1]; //방문 여부를 검사할 배열
		LinkedList<Integer>[] adjList = new LinkedList[n+1];
		for(int i=0;i<=n;i++) {
			adjList[i]=new LinkedList<Integer>();
		}
		//두 정점 사이에 여러개 간선이 있을 수 있음
		// 입력으로 주어지는 간선은 양방향
		for(int i=0;i<m;i++) {
			int v1 = sc.nextInt();
			int v2= sc.nextInt();
			adjList[v1].add(v2);
			adjList[v2].add(v1);
		}
		for(int i=1;i<=n;i++) {
			Collections.sort(adjList[i]);
		}
		boolean[] check = new boolean[n+1];
		System.out.println("DFS-인접리스트");
		dfs_list(v,adjList,check);
	}

}

2) 스택

 

public void DFS(int start){
    boolean[] visited = new boolean[vertex];
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(start);
    while (!stack.isEmpty()){
        int v = stack.pop();
        if (!visited[v]){
            visited[v] = true;
            for (int i = 0; i < list[v].size(); i++){
                int dest = list[v].get(i);
                if (!visited[dest])
                    stack.push(dest);
            }
        }
    }
}

 

너비 우선 탐색 BFS(Breadth-First Search)

: 탐색 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법, 즉 거리가 d인 정점들을 모두 방문하고 d+1의 거리를 갖는 노드들 방문

 

BFS 구현 방법

- 큐를 사용하여 구현됨

 

큐를 이용한 BFS

1) 큐

public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited) {
	Queue<Integer> queue = new LinkedList<Integer>();
	visited[v] = true; 
	queue.add(v);

	while(queue.size() != 0) { 
		v = queue.poll(); 
		System.out.print(v + " ");

		Iterator<Integer> iter = adjList[v].listIterator();
		while(iter.hasNext()) { 
			int w = iter.next(); 
			if(!visited[w]) { 
				visited[w] = true; 
				queue.add(w); 
			} 
		}
	}
}

+) 인접행렬

public static void bfs_array(int v, int[][] adjArray, boolean[] visited) {
	Queue<Integer> q = new LinkedList<>();
	int n = adjArray.length - 1;

	q.add(v);
	visited[v] = true;

	while (!q.isEmpty()) {
		v = q.poll();
		System.out.print(v + " ");

		for (int i = 1; i <= n; i++) {
			if (adjArray[v][i] == 1 && !visited[i]) {
				q.add(i);
				visited[i] = true;
			}
		}
	}
}

* 인접행렬은 간선들을 저장하는 방식의 일부인거지 bfs를 구현하는 방식이 아님

 

 

🙌 참고 및 출처

https://minhamina.tistory.com/36

[Java] BFS 너비 우선 탐색 - 인접리스트 / 인접행렬로 구현