깊이우선 탐색(DFS)와 너비우선 탐색(BFS), 응용 ; 연결 성분 찾기

그래프 탐색

: 그래프의 기본 연산 중 하나. 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문. 특정 정점에서 특정 정점까지 갈 수 있는지 없는지를 탐색

 

 

 

1. 깊이우선 탐색(DFS)

 

○ 개념

: 임의의 한쪽 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 그곳으로부터 다른 방향으로 다시 탐색을 진행. 갈림길로 다시 돌아가는 과정에서는 스택을 사용하거나 재귀 함수 호출을 이용.

 

 

 

○ 알고리즘

: 정점 v를 방문한 후 해당 정점이 방문되었다고 표시하고 v의 모든 인접 정점에 대해 방문되지 않은 정점이라면 재귀 함수 호출. 

 

 

 

○ 프로그램

int visited[8];
vector<int> adj_list[8]; //adj_list[i]에는 i의 인접 정점들의 리스트를 저장

void dfs(int v) {
    if(visited[8]) return;
    
    cout << v; //정점 v 방문하고 출력
    visited[v] = true; //정점 v 방문 표시
    
    for (int i = 0; i < adj_list[v].size(); i++) { //인접 정점 탐색
        int w = a[v][i];
        dfs(w);
}

 

 

 

 

2. 너비우선 탐색(BFS)

 

○ 개념

: 시작 정점으로부터 거리가 가까운 정점들을 먼저 차례로 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 운행 방법. 큐를 사용해 구현 가능.

 

 

 

○  알고리즘

: 정점 v를 방문한 후 방문되었다고 표시하고 v를 큐에 삽입. 큐가 빌 때까지 반복문을 돌며 큐에서 정점을 하나 꺼내어 그 정점과 인접하며 아직 방문되지 않은 모든 정점에 대해 방문을 시행. 방문한 후에는 방문되었다고 표시하고 해당 정점을 큐에 삽입.

 

 

 

○ 프로그램

int visited[8];
vector<int> adj_list[8];

void bfs(int v){
    queue<int> q;
    visited[v] = true;
    q.push(v);
    
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x;
        for (int i = 0; i<adj_list[x].size(); i++) {
            int w = adj_list[x][i];
            if (!visited[w]) {
                visited[w] = true;
                q.push(w);
            }
        }
    }
}
    

 

 

 

 

 

3. 응용 ; 연결 성분 찾기

 

○ 개념

연결 성분 : 최대로 연결된 부분 그래프. maximal connected subgraph.

 

 

 

○ 알고리즘

: DFS 또는 BFS를 시작하여 같은 연결 성분에 해당되는 것은 방문되었다고 기록할 때 같은 번호를 붙여줌. 이어져 있지 않은 정점에는 방문할 수 없기 때문. 번호를 하나 증가시킨 후 방문하지 않은 정점을 선택해 다시 탐색을 반복함. 그래프의 모든 정점이 방문될 때까지 반복.

 

 

 

○ 프로그램

int visited[8];
vector<int> adj_list[8]; //adj_list[i]에는 i의 인접 정점들의 리스트를 저장
int count;

void dfs(int v) {
    if(visited[8]) return;
    
    cout << v; //정점 v 방문하고 출력
    visited[v] = count; //정점 v이 속한 연결 성분의 번호 저장
    
    for (int i = 0; i < adj_list[v].size(); i++) { //인접 정점 탐색
        int w = a[v][i];
        dfs(w);
}

void find_connected_component() {
    for (int i = 0; i < 8; i++) {
        if (!visited[i]) { //방문하지 않은 정점을 선택해서 다시 탐색
            count++;
            dfs(i);
        }
    }
}