(C++)DFS,BFS

그래프 탐색

위와 같이 정점끼리 연결된 그래프가 있다고 했을 떄 각각을 인접행렬과 인접리스트로 모든 그래프를 탐색하는 코드를 구현해보면

인접행렬

#include<iostream>
#include<vector>

using namespace std;

const int v = 4;
int a[v][v];
int visited[v];

void search(int old) {
    cout << old << ' ';
    visited[old] = 1;
    for (int i = 0; i < v; i++) {
        if (a[old][i] && !visited[i]) {
            search(i);
        }
    }

}

int main() {
    a[0][1] = 1; a[1][0] = 1;
    a[0][2] = 1; a[2][0] = 1;
    a[1][2] = 1; a[2][1] = 1;
    a[2][3] = 1; a[3][2] = 1;

    for (int i = 0; i < v; i++) {
        for (int j = 0; j < v; j++) {
            if (a[i][j] && !visited[i]) {
                search(i);
            }
        }
    }

    return 0;
}
//출력
0 1 2 3 

인접리스트

#include<iostream>
#include<vector>

using namespace std;

const int v = 4;
vector<int> adj[v];
int visited[v];

void search(int old) {
    cout << old << ' ';
    visited[old] = 1;
    for (auto ele : adj[old]) {
        if (!visited[ele] && adj[ele].size() != 0){
            search(ele);
        }  
    }
}

int main() {
    adj[0].push_back(1);
    adj[1].push_back(0);

    adj[0].push_back(2);
    adj[2].push_back(0);

    adj[1].push_back(2);
    adj[2].push_back(1);

    adj[2].push_back(3);
    adj[3].push_back(2);

    for (int i = 0; i < v; i++) {
        cout << i << " : ";
        for (auto ele : adj[i]) {
            cout << ele << ' ';
        }
        cout << '\n';
    }   
    cout << '\n';

    for (int i = 0; i < v; i++) {
        if (adj[i].size() != 0 && !visited[i]) {
            search(i);
        }
    }

    return 0;
}
//출력
0 : 1 2 
1 : 0 2 
2 : 0 1 3 
3 : 2 

0 1 2 3

인접행렬의 경우에는 그래프에 연결된 엣지가 많을 때 사용하기에 효율적이다. 왜냐하면 인접리스트의 경우에 연결된 정점을 넣어주기만 하면되는데 인접행렬은 엣지가 없더라도 모든 그래프를 탐색해야하기 때문이다.

DFS (깊이우선탐색)

시작노드부터 인접한 노드를 재귀함수를 통해 반복적으로 방문하여 가장 멀리있는 노드까지 탐색하는 알고리즘

수도코드

dfs(vertex,adj)
    vertex.visited=true
    for each_vertex in adj[vertex]
        if each_vertex.visited=false
            dfs(each_vertex,adj)

탐색순서

10 - 5 - 1 - 6 - 17 - 14 - 21

BFS (너비우선탐색)

수도코드

bfs(vertex,adj)
    vertex.visited=true
    q.push(vertex)
    while(q.size())
        vertex=q.front();
        q.pop()
        for each_vertex in adj[vertex]
            if each_vertex.visited=false
                each_vertex.visted=true   or  each_vertex.visited=vertex.visited+1
                q.push(each_vertex)

탐색순서

10 - 5 - 17 - 1 - 6 - 14 - 21

예제 (정점간의 최단거리)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;


vector<int> adj[100];
int visited[100];
int nodeList[] = { 10,12,14,16,18,20,22,24 };

void bfs(int v) {
    queue<int> q;
    visited[v] = 1;
    q.push(v);
    while (q.size()) {
        v = q.front();
        q.pop();
        for (auto ele : adj[v]) {
            if (!visited[ele]) {
                visited[ele] = visited[v] + 1;
                q.push(ele);

            }
        }
    }
}

int main() {
    adj[10].push_back(12);
    adj[10].push_back(14);
    adj[10].push_back(16);

    adj[12].push_back(18);
    adj[12].push_back(20);

    adj[20].push_back(22);
    adj[20].push_back(24);
    bfs(10);

    for (auto ele : nodeList) {
        cout << ele << ' ' << visited[ele] << '\n';
    }
    return 0;
}
//출력
10 1
12 2
14 2
16 2
18 3
20 3
22 4
24 4