06-图1 列出连通集（25 分）邻接矩阵

给定一个有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 }


我的答案 邻接矩阵的方法

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

#define MaxVertexNum 100
#define INFINITY     65535
#define MaxSize 100

typedef int Vertex;
typedef int WeightType;
typedef char DataType;

typedef struct ENode *PtrToENode;
struct ENode {
    Vertex V1, V2;
    WeightType Weight;
};
typedef PtrToENode Edge;

typedef struct GNode *PtrToGNode;
struct GNode {
    int Nv;
    int Ne;
    WeightType G[MaxVertexNum][MaxVertexNum];
    DataType Data[MaxVertexNum];
};
typedef PtrToGNode MGraph;

struct QNode {
    Vertex Data[MaxSize];
    int rear;
    int front;
};
typedef struct QNode *Queue;

MGraph CreateGraph(int VertexNum)
{
    Vertex V, W;
    MGraph Graph;

    Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    for(V=0;V<Graph->Nv;V++)
        for(W=0;W<Graph->Nv;W++)
            Graph->G[V][W] = INFINITY;

    return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2] = E->Weight;
    Graph->G[E->V2][E->V1] = E->Weight;
}

MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    // Vertex V;
    int Nv, i;

    scanf("%d ", &Nv);
    Graph = CreateGraph(Nv);

    scanf("%d
", &(Graph->Ne));
    if(Graph->Ne != 0) {
        E = (Edge)malloc(sizeof(struct ENode));
        for(i=0;i<Graph->Ne;i++) {
            scanf("%d %d
", &E->V1, &E->V2);
            E->Weight = 1;
            InsertEdge(Graph, E);
        }
    }

    // for(V=0;V<Graph->Nv;V++)
    //     scanf(" %c", &(Graph->Data[V]));

    return Graph;
}

//DFS
void Visit(Vertex V)
{
    // printf("Now visit Vertex %d
", V);
    printf(" %d", V);
}

void DFS(MGraph Graph, Vertex V, int *Visited)
{
    Vertex W;

    Visit(V);
    Visited[V] = 1;         //已访问

    for(W=0;W<Graph->Nv;W++)
        if(Graph->G[V][W]==1 && Visited[W]==0)
            DFS(Graph, W, Visited);
}

//BFS
int IsEmpty(Queue Q)
{
    return (Q->rear == Q->front);   //1:empty 0:not empty
}

void AddQ(Queue PtrQ, Vertex item)
{
    if((PtrQ->rear+1)%MaxSize == PtrQ->front) {
        printf("Queue full");
        return;
    }
    PtrQ->rear = (PtrQ->rear+1)%MaxSize;
    PtrQ->Data[PtrQ->rear] = item;
}

Vertex DeleteQ(Queue PtrQ)
{
    if(PtrQ->front == PtrQ->rear) {
        printf("Queue empty");
        return -1;
    } else {
        PtrQ->front = (PtrQ->front+1)%MaxSize;
        return PtrQ->Data[PtrQ->front];
    } 
}

int IsEdge(MGraph Graph, Vertex V, Vertex W)
{
    return Graph->G[V][W]<INFINITY?1:0;
}

void BFS(MGraph Graph, Vertex S, int *Visited)
{
    Queue Q;
    Vertex V, W;
    Q = (Queue)malloc(sizeof(struct QNode));
    Visit(S);
    Visited[S] = 1;
    AddQ(Q, S);

    while(!IsEmpty(Q)) {
        V = DeleteQ(Q);
        for(W=0;W<Graph->Nv;W++)
            if(!Visited[W] && IsEdge(Graph, V, W)) {
                Visit(W);
                Visited[W] = 1;
                AddQ(Q, W);
            }
    }
}

void PrintGraph(MGraph Graph)
{
    Vertex V, W;
    printf("Graph:
");
    for(V=0;V<Graph->Nv;V++) {
        for(W=0;W<Graph->Nv;W++) 
            printf("%5d " ,Graph->G[V][W]);
        printf("
");
    }
    printf("-----------------------
");
}

int main()
{
    MGraph Graph;
    int *Visited, i;

    Graph = BuildGraph();
    Visited = (int *)malloc(sizeof(int)*(Graph->Nv));
    for(i=0;i<Graph->Nv;i++)
        Visited[i] = 0;
    // PrintGraph(Graph);

    //DFS
    for(i=0;i<Graph->Nv;i++) {
        if(Visited[i] == 0) {
            printf("{");
            DFS(Graph, i, Visited);
            printf(" }
");
        }
    }

    //BFS
    for(i=0;i<Graph->Nv;i++)
        Visited[i] = 0;
    for(i=0;i<Graph->Nv;i++) {
        if(!Visited[i]) {
            printf("{");
            BFS(Graph, i, Visited);
            printf(" }
");
        }
    }

    return 0;
}