BFS와 DFS의 기초 개념 -2

오늘은 BFS와 DFS의 기초 개념부터 차근차근 설명하려고 합니다.

(해당 포스트는 BFS와 DFS의 개념을 모르는 초보분들을 초점으로한 포스팅입니다.) 

2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -1

오늘은 지난시간에 이어 DFS와 BFS를 코드레벨에서 살펴보겠습니다.

우선, 정점의 연결관계를 나타내는 가장 대표적인 방법은 인접 행렬과 인접 리스트로 나뉩니다.

1. 인접 행렬

위와 같은 노드와 간선을 연결하는 그래프가 있다고 가정하겠습니다.

이 그래프의 연결 정보를 인접 행렬로 표현한다면 어떻게 해야할까요????

결론부터 말씀드리면 아래 그림과 같은 2차원 배열에 연결 정보를 저장할 수 있습니다.

이 2차원 배열이 뜻하는 바를 살펴보면 행과 열의 데이터가 1이면 해당 노드들이 연결되어 있다는 뜻이고, 

0이면 연결되어 있지 않다는 것입니다.

위 그림과 같이 1번 노드는 2번, 6번 노드와 연결되어 있습니다. 이 뜻은 배열[1][2] = 1, 배열[1][6] = 1 이라는 뜻입니다.

마찬가지로 2번 노드 또한 1번, 6번 노드와 연결되어 있습니다. 이 뜻은 배열[2][1] =1, 배열[2][6] = 1 이라는 뜻입니다.

마지막으로 6번 노드 또한 1번, 2번 노드와 연결되어 있습니다. 이 뜻은 배열[6][1] = 1, 배열[6][2] = 1 이라는 뜻입니다.

나머지 노드들의 연결 정보와 인접행렬에 저장된 데이터 값을 비교해보시면  6 * 6 행렬에 모든 노드들의 연결 정보가 저장되어 있는 것을 확인할 수 있습니다.

인접행렬로 노드들의 연결정보를 저장했을 경우의 장단점에 대해서 알아봅시다.

장점)

해당 노드와의 연결 여부를 알기위한 시간 복잡도는 O(1)입니다.

예를 들어 1번 노드와 2번 노드가 연결되었는지 확인하기 위해서 해야할 일은 단순히 2차원 배열의 인덱스를 통해 접근하는 것입니다.

if(map[1][2] == 1)
    System.out.println("1번 노드와 2번 노드는 연결되었다.");
else
    System.out.println("1번 노드와 2번 노드는 연결되지 않았다.");
 
 


단점 - 1)
해당 노드와 어떤 노드들이 연결되어 있는지 알기 위한 시간 복잡도는 O(N)입니다.
예를 들어 1번 노드와 연결된 모든 노드들을 알고 싶다고 생각해봅시다.
연결정보를 2차원 배열에 저장했을 경우 배열[1][1] ~ 배열[1][6]까지 총 6개의 데이터를 확인하면서 해당하는 값이 1인지 0인지 확인하는 것입니다.

for(int i = 0 ; i < N; i++){
    if(map[1][i] == 1){
        count += 1;
    }
}

이 방법은 1번 노드와 연결된 노드가 2번, 6번 노드밖에 없음에도 불구하고 1번 ~ N번까지의 열을 모두 확인해야 한다는 단점이 있습니다.

단점 - 2)
1번부터 6번까지의 노드간의 연결정보를 저장하기 위해 6 x 6 2차원 배열을 사용한것 처럼 N^2 만큼의 저장공간을 필요로 한다는 것입니다.

[인접행렬로 연결정보 저장하기]

1. 사용자로부터 정점의 갯수 N과 간선의 갯수 M을 입력받는다.

2. 사용자로부터 연결관계에 있는 노드 A와 B를 입력받아 2차원 배열에 입력정보를 저장한다.

#include <iostream>

 

using namespace std;

 

#define MAX 10

 

int main(void) {

 

    int map[MAX][MAX] = { 0, };

    int a, b, n, m;

 

    cin >> n >> m;

 

    // 노드의 연결정보를 입력받는다.

    for (int i = 0; i < m; i++) {

        cin >> a >> b;

        map[a][b] = 1;

        map[b][a] = 1;

    }

 

    //인접행렬에 저장된 연결정보를 출력한다.

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= n; j++) {

            cout << map[i][j] << " ";

        }

        cout << endl;

    }

 

}

2. 인접 리스트

인접행렬을 살펴보았다면, 연결정보를 인접리스트로는 어떻게 표현할 수 있을까요?

바로 아래와 같이 표현할 수 있습니다.

이 리스트가 뜻하는 것은

1번 노드에 2번, 6번 노드가 연결되어있다.

2번 노드에 1번, 3번, 4번, 6번 노드가 연결되어있다.

3번 노드에 2번, 5번 노드가 연결되어있다.

.....................

장점)

인접리스트는 N*N개의 2차원 배열을 선언하는 것과 다르게 실제로 연결된 노드들의 정보만을 담고 있습니다.

그렇기 때문에 인접행렬처럼 N^2만큼의 배열을 선언할 필요도 없고, 각 노드에 연결된 모든 노드들을 살펴보기

위해 O(N) 시간복잡도가 아닌 실제 연결된 노드의 갯수만큼의 시간복잡도를 지닙니다.

단점)

각각의 노드가 연결되어있는지 확인하기 위해서는 인접행렬은 map[row][col] == 1 을 통해 바로 확인할 수 있어서

 O(1)의 시간복잡도가걸렸습니다.

하지만, 연결리스트에서는 실제로 연결된 노드들만 리스트에 추가되기 때문에 O(1)의 시간복잡도가 아닌 

해당 리스트의 길이만큼 탐색하여 연결여부를 확인해야 합니다.

[연결리스트로 연결정보 저장하기]

1. 사용자로부터 정점의 갯수 N과 간선의 갯수 M을 입력받는다.

2. 사용자로부터 연결관계에 있는 노드 A와 B를 입력받아 vector에 저장한다.

#include <iostream>
#include <vector>
 
using namespace std;
 
#define MAX 10
 
int n, m, a, b;
vector<int> v[MAX];
 
int main(){
    
    cin >> n >> m;
 
    // 노드의 연결정보를 입력받는다.
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        
        v[a].push_back(b);
        v[b].push_back(a); 
    }
    
    //인접행렬에 저장된 연결정보를 출력한다.
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= v[i].size(); j++) {
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
    
}
 

다음 포스팅에서는 연결정보를 바탕으로 직접 BFS와 DFS를 구현하겠습니다.

2019/02/11 - [알고리즘 이론] - BFS와 DFS의 기초 개념 -3