7-6 列出连通集

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

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

输出格式:
按照"{ v
​1
​​  v
​2
​​  ... 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 }


很显然 告诉边 ，就利用边求邻接矩阵 来判断是否相邻 
对DFS BFS都有用一个矩阵来标记是否已经访问过了 ，DFS就递归 BFS就队列 




#include <stdio.h>
#include <stdlib.h>

#define MAXN 10
int graph[MAXN][MAXN] = {0};
int visitedDFS[MAXN] = {0};
int visitedBFS[MAXN] = {0};

/* 队列定义开始 */
#define MaxSize 11
#define ERROR -1
typedef int Position;
struct QNode {
    int *Data;     /* 存储元素的数组 */
    Position Front, Rear;  /* 队列的头、尾指针 */
};
typedef struct QNode *Queue;

Queue CreateQueue()
{
    Queue Q = (Queue)malloc(sizeof(struct QNode));
    Q->Data = (int *)malloc(MaxSize * sizeof(int));
    Q->Front = Q->Rear = 0;
    return Q;
}

void DestoryQueue( Queue Q )
{
    if (Q->Data) free(Q->Data);
    free(Q);
}

int IsFull( Queue Q )
{
    return ((Q->Rear+1)%MaxSize == Q->Front);
}

void Enqueue( Queue Q, int X )
{
    if ( IsFull(Q) ) return;
    else {
        Q->Rear = (Q->Rear+1)%MaxSize;
        Q->Data[Q->Rear] = X;
    }
}

int IsEmpty( Queue Q )
{
    return (Q->Front == Q->Rear);
}

int Dequeue( Queue Q )
{
    if ( IsEmpty(Q) ) return ERROR;
    else  {
        Q->Front =(Q->Front+1)%MaxSize;
        return  Q->Data[Q->Front];
    }
}
/* 队列定义结束 */

void createGraph(int edges)
{
    int i, j, k;
    for (k = 0; k < edges; ++k) {
        scanf("%d %d", &i, &j);
        graph[i][j] = 1;
        graph[j][i] = 1;
    }
}

void DFS(int vertex, int nodes)
{
    int i, j;
    visitedDFS[vertex] = 1;
    printf("%d ", vertex);
    for (i = vertex, j = 0; j < nodes; ++j) {
        if (graph[i][j] == 1 && !visitedDFS[j])
            DFS(j, nodes);
    }
}

void BFS(int vertex, int nodes)
{
    int tmp, i, j;
    Queue Q;
    Q = CreateQueue();
    visitedBFS[vertex] = 1;
    printf("%d ", vertex);
    Enqueue(Q, vertex);
    while(!IsEmpty(Q)) {
        tmp = Dequeue(Q);
        for (i = tmp, j = 0; j < nodes; ++j) {
            if (graph[i][j] == 1 && !visitedBFS[j]) {
                visitedBFS[j] = 1;
                printf("%d ", j);
                Enqueue(Q, j);
            }
        }
    }

    DestoryQueue(Q);
}

void ListComponents (int nodes)
{
    int i;
    for (i = 0; i < nodes; ++i) {
        if (!visitedDFS[i]) {
            printf("{ ");
            DFS(i, nodes);
            printf("}\n");
        }
    }
    for (i = 0; i < nodes; ++i) {
        if (!visitedBFS[i]) {
            printf("{ ");
            BFS(i, nodes);
            printf("}\n");
        }
    }
}

int main()
{
    int N, E;
    scanf("%d %d", &N, &E);

    createGraph(E);
    ListComponents(N);

    return 0;
}