06 - 그림 1 목록 연결 집합 (25 점) DFS BFS

N 개의 정점 과 E 개의 변 이 있 는 무 방향 그림 을 지정 합 니 다. DFS 와 BFS 로 각각 모든 연결 집합 을 보 여 주 십시오.정점 을 0 에서 N - 1 번 으로 가정 하 다.검색 을 할 때, 우리 가 항상 번호 가 가장 작은 정점 에서 출발 하여 번호 가 증가 하 는 순서에 따라 인접 지점 에 접근한다 고 가정 합 니 다.
입력 형식:
첫 번 째 줄 을 입력 하여 정수 N 2 개 주기 (0)
출력 형식:
"{v1 v2... v k}" 형식 으로 줄 마다 연결 집합 을 출력 합 니 다. DFS 결 과 를 먼저 출력 하고 BFS 결 과 를 출력 합 니 다.
입력 예시:
8 6 0 7 0 1 2 0 4 1 2 4 3 5
출력 예시:
{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 } { 6 }

#include
#include
#include
#define MAXN 10

using namespace std;

queue<int> q;
int Graphic[MAXN][MAXN];
bool visited[MAXN];
void DFS(int v);
void BFS(int v);
int N,E;

int main(){
    int i, v1, v2;
    scanf("%d %d", &N, &E);
    memset(Graphic,0,sizeof(Graphic));
    memset(visited,0,sizeof(visited));
    for(i = 0; i < E; i++){
        scanf("%d %d", &v1, &v2);
        Graphic[v1][v2] = Graphic[v2][v1] = 1;
    }
    for(i=0;i<N;i++){
        if(!visited[i]){
            printf("{ ");
            DFS(i);
            printf("}
");
        }
    }
    memset(visited,0,sizeof(visited));
    for(i = 0; i < N; i++){
        if(!visited[i]){
            printf("{ ");
            BFS(i);
            printf("}
");
        }
    }
    return 0;
}

void DFS(int v){
    int i;
    visited[v] = true;
    printf("%d ", v);
    for(i = 0; i < N; i++){
        if(!visited[i] && Graphic[v][i] == 1){
            DFS(i);
        }
    }
}

void BFS(int v){
    int i;
    visited[v] = true;
    printf("%d ", v);
    q.push(v);
    while(!q.empty()){
        int front = q.front();
        q.pop();
        for(i = 0; i < N; i++){
            if(!visited[i] && Graphic[front][i] == 1){
                visited[i] = true;
                printf("%d ", i);
                q.push(i);
            }
        }
    }
}

DFS: 깊이 우선 검색 은 먼저 어두 운 길 로 가 는 것 입 니 다. 다시 철수 할 수 없습니다. 바로 for 순환 입 니 다. 방문 하지 않 고 연 결 된 노드 는 DFS 입 니 다.
BFS: 모든 단 계 는 주위 에 어떤 정점 이 있 는 지 보 는 것 입 니 다. 바로 나무의 층 차 를 옮 겨 다 니 며 대기 열 을 사용 하 는 것 입 니 다. 한 노드 를 넣 고 그의 값 을 출력 하고 팝 업 합 니 다. 그녀 와 관련 된 정점 을 찾 아 그의 좌 표를 출력 한 다음 에 스 택 에 눌 러 넣 습 니 다.