题目

给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序访问邻接点。

输入格式

输入第1行给出2个整数N(0<N≤10)和E，分别是图的顶点数和边数。随后E行，每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式

按照”{ v1 v2 … vk}”的格式，每行输出一个连通集。先输出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 }

思路

没什么好说的，DFS和BSF的基础题，没有任何其余考点

  1. flag数组用来标记是否遍历
  2. 邻接矩阵存储图
  3. 通过循环在一次遍历后查找其余的连通子图

DFS

  1. 0结点flag置为1，输出
  2. 循环，寻找和它相邻的最小结点
  3. 递归调用DFS

BFS

  1. 0结点入队，flag置为1
  2. 队头出队，循环查找与它相邻的结点，并插入队列
  3. 队列不为空则循环执行步骤2

源码实现

#include <stdio.h>

int G[10][10]={0};  //图
int flag[10]={0};  //flag是否出队

struct Qnode{  //队列
    int data[11];
    int rear;
    int front;
}Q;

void init(int N);  //flag数组初始化
void list_dfs(int N);  //在一次遍历后寻找其他的连通子图
void DFS(int N,int v);  //DFS
void list_bfs(int N);
void BFS(int N,int v);
void add(int v);  //入队
int enqueue();  //出队

int main()
{
    int N,E;
    int v1,v2;
    Q.rear=Q.front=0;
    scanf("%d %d",&N,&E);
    for(int i=0;i<E;i++){
        scanf("%d %d",&v1,&v2);
        G[v1][v2]=1;
        G[v2][v1]=1;
    }
    list_dfs(N);
    init(N);
    list_bfs(N);
    return 0;
}

void init(int N){
    for(int i=0;i<N;i++){
        flag[i]=0;
    }
}

void list_dfs(int N){
    for(int i=0;i<N;i++){
        if(flag[i]==0){
            printf("{ ");
            DFS(N,i);
            printf("}\n");
        }
    }
}

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

void list_bfs(int N){
    for(int i=0;i<N;i++){
        if(flag[i]==0){
            printf("{ ");
            BFS(N,i);
            printf("}\n");
        }
    }
}

void BFS(int N,int v){
    add(v);
    flag[v]=1;
    while(Q.rear!=Q.front){
        v=enqueue();
        printf("%d ",v);
        for(int i=0;i<N;i++){
            if(flag[i]==0&&G[v][i]==1){
                add(i);
                flag[i]=1;
            }
        }
    }
}

void add(int v){
    Q.data[Q.rear++]=v;
}

int enqueue(){
    return Q.data[Q.front++];
}