백준 1260 DFS와 BFS

 

 

 

 

DFS와 BFS를 구현하는 문제이다. 

 

DFS의 경우 

DFS(깊이우선탐색)은 자기자신을 호출하는 순환알고리즘의 형태를 갖는다.

재귀를 이용해서 구현!!

• 1번 노드에 인접한 모든 노드들에 대해서 간선이 있고, 방문하지 않았던 지점이라면 방문한다.
• 같은 방식으로 n개의 노드에 대해서 진행.

 

BFS의 경우

BFS(너비우선탐색)은 재귀적으로 동작하지 않는다.

일반적으로 큐를 사용해서 반복적으로 구현한다.

Prim, Dijkstra알고리즘과 유사하다.

큐를 이용해서 구현!!(FIFO방식)

• 1번노드에 인접한 모든 노드들에 대해서 간선이 있고 방문하지 않았던 지점이라면 방문하여 큐에 넣는다.
• 큐가 empty가 될 때까지 반복해서 진행. 

 

Code

#include <iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;
//dfs-->재귀 사용
//bfs-->큐 사용
 
bool visited[1001];
int graph[1001][1001];
queue<int> q;
int m, n, v;
 
void dfs(int node)
{
    visited[node] = true;
    cout << node << " ";
    
    for (int i = 0; i <= n; i++)
    {
        if (graph[node][i] && !visited[i])
        {
            visited[i] = true;
            dfs(i);
        }
    }
    
}
 
void bfs(int node)
{
    q.push(node);
    visited[node] = true;
    
    while (!q.empty())
    {
        int node_q = q.front();
        q.pop();
        cout << node_q << " ";
 
        for (int i = 0; i <= n; i++)
        {
            if (graph[node_q][i] && !visited[i])
            {
                visited[i] = true;
                q.push(i);
            }
        }
    }
}
 
int main()
{
    cin >> n >> m >> v;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a][b] = 1;
        graph[b][a] = 1;
    }
 
    dfs(v);
    memset(visited, false, sizeof(visited));
    cout << endl;
    bfs(v);
 
    return 0;
}