그래프 (DFS, BFS)

 

그래프 (DFS, BFS)

 

 

그래프의 표현 방법

1. 인접 리스트

 - vector<list<int>> adjacent;

 - vector<vector<int>> adjacent;

adjacent[i]는 정점 i와 인접한 정점들의 번호를 저장하는 연결리스트(혹은 동적배열)임

 

여기서 추가적 속성을 갖는 그래프를 표현하려면?

 → pair<int, int> 사용

 

 

 

2. 인접 행렬

 - vector<vector<bool>> adjacent;

adjacent[i,j]는 정점 i에서 j로 가는 간선이 있는지를 나타내는 bool값 변수임

 

가중치 그래프를 인접 행렬로 표현하려면?

 → bool이 아닌, int나 float으로 두면 됨

 → 두 정점 사이에 간선이 없는 경우에는 이 값을 -1 혹은 아주 큰 값으로 설정

 

 

 

 

 

 

 

 

그래프는 트리보다 구조가 훨씬 복잡할 수 있기 때문에 탐색 과정에서 얻어지는 정보가 아주 중요하다

탐색과정에서 어떤 간선이 사용되었는지, 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다.

탐색 알고리즘 중 가장 널리 사용되는 두가지가 깊이 우선 탐색과 너비 우선 탐색이다.

 

 

 

 

 

1. 깊이 우선 탐색 (depth-first search, DFS)

깊이 우선 탐색은 말그대로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않는다.

 

 

구현

// 그래프의 인접 리스트 표현
vector<vector<int>> adj;
// 각 정점을 방문했는지 여부를 나타낸다.
vector<bool> visited;
// 깊이 우선 탐색 구현
void dfs(int here) {
    // 방문한 노드 출력
    cout << "DFS visits " << here << endl;
    // 방문했다는 것을 기록
    visited[here] = true;
 
    // 모든 인접 정점을 순회하면서
    int size = adj[here].size();
    for (int i = 0; i < size; ++i) {
        int there = adj[here][i];
        // 아직 방문한 적 없다면 방문
        if (!visited[there])
            dfs(there);
    }
    // 더이상 방문할 정점이 없으니,
    // 재귀 호출을 종료하고 이전 정점으로 돌아간다.
}
 
//모든 정점 방문
void dfsAll() {
    // visited를 모두 false로 초기화한다.
    visited = vector<bool>(adj.size(), false);
    // 모든 정점을 순회하면서, 아직 방문한 적 없으면 방문
    int size = adj.size();
    for (int i = 0; i < size; ++i) {
        if (!visited[i])
            dfs(i);
    }
}

먼저 dfs 함수를 살펴보자. 재귀로 구현되었다.

dfs 함수에 들어왔다는 것 = 방문했다는 것

 

1. 방문했으니 현재 번호 (here) 출력해주고

2. 방문했음을 기록

3. 그리고 모든 인접 정점을 순회하면서 방문했는지 검사

4. 아직 방문한 적이 없다면 dfs 함수에 들어가기 (방문하기)

5. 인접 정점 순회가 끝났으면 재귀 빠져나오기 (이전으로 돌아가기)

 

 

그리고 유의할 점은 모든 정점에 대해 순서대로 dfs()를 호출하는 dfsAll() 함수임

그래프에서는 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없다.

그래서 dfs 함수로만 모든 정점을 순서대로 발견 못 할 수 있다.

 

깊이 우선 탐색은 그래프 전체의 구조를 파악하기 위해 사용된다.

그래프의 구조상 한번에 모든 정점을 다 볼 수 없는 경우에도 모든 정점을 다 방문할 필요가 있다.

 

 

 

시간 복잡도

1. 인접 리스트 사용 (위 코드)

● dfs()는 한 정점마다 한 번씩 호출된다.

 => V번 호출됨

● dfs() 한 번의 수행 시간은 인접 노드를 순회하는 for문에 의해 결정된다.

 => 모든 정점에 대해 dfs()를 수행하고 나면 모든 간선을 한번(방향 그래프) 또는 두번(무향 그래프) 확인함을 알 수 있다. ( E )

 

→ 시간복잡도는 O(V+E)

 

 

2. 인접 행렬 사용

● dfs()는 한 정점마다 한 번씩 호출된다.

 => V번 호출됨

● dfs() 한번 실행에 다른 모든 정점을 순회해야한다. (두 정점 사이에 간선이 있는지 확인 위해서)

 => V번 호출됨

 

→ 시간복잡도는 O(V^2)

 

 

 

 

 

 

2. 너비 우선 탐색 (Breadth First Search, BFS)

시작점에서 가까운 정점부터 순서대로 방문한다.

 

 

구현

// 그래프의 인접 리스트 표현
vector<vector<int>> adj;
// start에서 시작해 그래프를 너비 우선 탐색하고
// 각 정점의 방문 순서를 반환
vector<int> bfs(int start) {
    // 각 정점의 방문 여부
    vector<bool> discovered(adj.size(), false);
    // 방문할 정점 목록을 유지하는 큐
    queue<int> q;
    // 정점의 방문 순서
    vector<int> order;
    discovered[start] = true;
    q.push(start);
    while (!q.empty()) {
        int here = q.front();
        q.pop();
        // here를 방문한다
        order.push_back(here);
        // 모든 인접한 정점을 검사한다
        int size = adj[here].size();
        for (int i = 0; i < size; ++i) {
            int there = adj[here][i];
            // 처음 보는 정점이면 방문 목록에 집어넣는다
            if (!discovered[there]) {
                q.push(there);
                discovered[there] = true;
            }
        }
    }
    return order;
}

bfs 함수를 살펴보자.

1. 한 정점을 order에 넣고

2. 이와 인접하고 방문하지 않은 정점을 큐에 넣기

3. 방문했음을 기록

4. 1, 2, 3을 반복

5. 순서대로 쌓인 order를 반환

 

 

너비 우선 탐색의 모든 정점은 다음과 같은 세개의 상태를 순서대로 거치게 된다.

1. 아직 발견되지 않은 상태

2. 발견되었지만 아직 방문되지는 않는 상태 (이 상태의 정점들은 큐에 저장되어 있음)

3. 방문된 상태

 

 

 

시간 복잡도 - DFS와 같음

1. 인접 리스트 사용 (위 코드)

→ 시간복잡도는 O(V+E)

 

2. 인접 행렬 사용

→ 시간복잡도는 O(V^2)