[Algorithm] 📈 DFS(깊이 우선 탐색)와 BFS(넓이 우선 탐색)

📘 그래프를 탐색하는 방법

그래프란 노드와 간선으로 이루어진 자료구조의 일종이다.
이 그래프를 탐색하는 방법에는 DFS(Depth-First Search) 즉, 깊이 우선 탐색 방법과 BFS(Breadth-First Search) 즉, 넓이 우선 탐색 방법이 있다.
이때, 구현방법은 인접행렬과 인접리스트를 사용하여 구현하는데, 이에 대해 더 알아보고 싶으면 다음 링크를 살펴보길 바란다.

링크

📖 DFS(깊이 우선 탐색)

다음은 DFS의 정의이다.

그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

DFS는 다음 그림과 같이 작동을 하며 일반적으로 Stack이나 재귀함수를 통해 구현한다.

출처:https://developer-mac.tistory.com/64

• 탐색 시작 노드를 Stack에 삽입하고 방문 처리한다.
• Stack의 top에 있는 노드에 인접한 노드가 하나라도 있으면, 그 노드를 방문 처리하고, Stack에 넣는다.
• 방문하지 않은 노드가 없으면 Top에서 노드를 꺼낸다.
• 2와 3을 수행할 수 없을 떄까지 반복한다.

📖 구현

📋 재귀 호출

static Stack<Integer> stack = new Stack<>();
static StringBuilder sb = new StringBuilder();
static boolean node[][] = new boolean[n+1][n+1], visited[] = new boolean[n+1];
static void dfs(int v) {
	if(visited[v])
    	return;
	sb.append(v+" ");
	for(int i=1; i<=n; i++)
		if(node[v][i] && !visited[i]) {
			visited[i] = true;
			dfs(i);
		}
}

📋 스택 사용

public static String dfs(int v, boolean node[][]) {
    StringBuilder sb = new StringBuilder();
    Stack<Integer> stack = new Stack<>();
    boolean visited[] = new boolean[n+1];
    stack.add(v);
    int idx;
    while(!stack.isEmpty()) {
        idx = stack.pop();
        if(visited[idx])
            continue;
        visited[idx] = true;
        sb.append(idx+" ");
        for(int i=0; i<n; i++)
            if(node[idx][i] && !visited[i])
                stack.add(i);
    }
    return sb.toString();
}

📖 BFS(넓이 우선 탐색)

다음은 BFS의 정의이다.

그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

BFS는 다음 그림과 같이 작동을 하며, 일반적으로 Queue를 사용하여 구현한다.

출처:https://developer-mac.tistory.com/64

• 탐색 시작 노드를 Queue에 삽입하고 방문 처리한다.
• Queue에서 노드를 꺼낸후 인접 노드중 방문하지 않은 노드를 모드 Queue에 삽입하고 방문 처리한다.
• 2을 수행할 수 없을 떄까지 반복한다.

📋 인접 행렬

void BFS(int V, int start)
{
    queue<int> q;
    bool check[V+1] = {false};
    
    check[start] = true;
    q.push(start);
    
    while(!q.empty())
    {
    	int now = q.front();
        q.pop();
        
        for(int i = 1; i <= V; i++)
        {
        	if(graph[now][i] == 1 && !check[i])
            {
            	check[i] = true;
                q.push(i);
            }
        }
    }
}

📋 인접 리스트

void BFS(vector<int> *graph,int V, int start)
{
    queue<int> q;
    bool check[V+1] = {false};
    
    check[start] = true;
    q.push(start);
    
    while(!q.empty())
    {
    	int now = q.front();
        q.pop();
        
        for(int i = 0; i < graph[now].size(); i++)
        {
            int next = graph[now][i];
            if(!check[next])
            {
            	check[next] = true;
                q.push(next);
            }
        }
    }
}

🔗 관련 예시

tag:DFS tag:BFS

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁