그래프의 탐색(DFS, BFS)

그래프 탐색의 목적 : 임의의 시작점 x에서 시작해서 모든 정점을 한번씩 반복하는 것

 

1. DFS(깊이우선탐색) 

- 한 시작점에서 갈 수 있을때 까지 계속진행하다 뒤도돌아오고 다시 갈수있는데 까지 감

- 스택사용해서 갈 수 있는 만큼 최대한 많이가고

- 갈 수 없으면 이전 정점으로 돌아간다.

- 재귀호출을 이용해서 구현할 수 있다.

// dfs(x) : x에 방문했다는 의미
// 인접 행렬
void dfs(int x){
    check[x] = true;
    printf("%d",x);
    for(int i=1; i<=n; i++){
        if(a[x][i] == 1 && check[i] == false){
            dfs(i);
        }
    }
}

 

// dfs(x) : x에 방문했다는 의미
// 인접 리스트
void dfs(int x){
    check[x] = true;
    printf("%d",x);
    for(int i=0; i<=a[x].size(); i++){
        int y = a[x][i];
        if(check[y] == false){
            dfs(y);
        }
    }
}

 

 

2. BFS(너비우선탐색)

- 한 정점에서 갈수 있는 걸 다 동시에 감, 쭉쭉퍼져나감

- Queue를 이용해서 할 수 있다.

//인접 행렬
queue<int> q;
check[1] = true; q.push(1);
while(!q.empty()){
    int x = q.front(); q.pop();
    printf("%d",x);
    for(int i=1; i<=n; i++){
        if(a[x][i] == 1 && check[i] == false){
            check[i] = true;
            q.push(i);
        }
    }
}

 

//인접 리스트
queue<int> q;
check[1] = true; q.push(1);
while(!q.empty()){
    int x = q.front(); q.pop();
    printf("%d",x);
    for(int i=0; i<a[x].size(); i++){
        int y = a[x][i];
        if(a[y] == false){
            check[y] = true; q.push(y);
        }
    }
}

 

 

 

이분그래프

그래프의 정점을 이분으로 나누어 논 그래프

어떠한 조건? A에 들어있는 정점끼리는 서로 연결하는 간선이 없어야함

DFS 또는 BFS 탐색으로 이분 그래프인지 아닌지 알아낼 수 있다.