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 }

Code

#include <stdio.h>
#include <stdlib.h>
#define MaxVertexNum 10

int Visited[MaxVertexNum];
int N;
typedef int Vertex; /* 用顶点下标表示顶点,为整型 */
/*边的定义*/
typedef struct ENode *Edge;
struct ENode{
    Vertex V1,V2;
};

/*邻接点的定义*/
typedef struct AdjNode *PtrToAdjNode;
struct AdjNode{
    Vertex AdjV;
    PtrToAdjNode Next;
};

/*邻接表头结点定义*/
typedef struct VNode{
    PtrToAdjNode FirstEdge;
}AdjList[MaxVertexNum];

/*图结点的定义*/
typedef struct GNode *LGraph;
struct GNode{
    int Nv,Ne;
    AdjList G;
};

typedef struct QueueNode *Queue;
struct QueueNode{
    int Front,Rear;
    Vertex *Elements;
};

LGraph CreatGraph(int VexterNum);
void InsertEdge(LGraph Graph,Edge E);
LGraph BuildGraph();
void DFS(LGraph Graph,Vertex V,void (*Visit)(Vertex));
void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex));
Queue CreatQuene(int MaxSize);
void AddQ(Queue Q,Vertex V);
Vertex DeleteQ(Queue Q);
int IsEmpty(Queue Q);
void Visit(Vertex V);

int main()
{
    Vertex V;
    LGraph Graph = BuildGraph();
    for(V=0;V<MaxVertexNum;V++) Visited[V] = 0;
    for(V=0;V<N;V++)
    {
        if(!Visited[V])
        {
            printf("{ ");
            DFS(Graph,V,Visit);
            printf("}\n");
        }
    }

    for(V=0;V<MaxVertexNum;V++) Visited[V] = 0;
    for(V=0;V<N;V++)
    {
        if(!Visited[V])
        {
            printf("{ ");
            BFS(Graph,V,Visit);
            printf("}\n");
        }
    }
    return 0;
}

LGraph CreatGraph(int VexterNum)
{/* 初始化一个有VertexNum个顶点但没有边的图 */
    LGraph Graph;
    Graph = (LGraph)malloc(sizeof(struct GNode));
    Graph->Ne = 0;
    Graph->Nv = VexterNum;
    for(int V=0;V<Graph->Nv;V++)
    {
        Graph->G[V].FirstEdge = NULL;
    }
    return Graph;
}

void InsertEdge(LGraph Graph,Edge E)
{
    PtrToAdjNode NewNode,W;
    /* 插入边 <V1, V2> ,在V1为下标的链表中，插入结点V2,表示v1->v2*/
    NewNode = (PtrToAdjNode)malloc(sizeof(struct AdjNode));
    NewNode->AdjV = E->V2;
    /*remark:注意题目要求是按照编号递增的顺序访问邻接点， 所以邻接表插入新结点的时候要注意按照下标从小到大插入； 这部分用邻接矩阵存储的话会比较简便*/
    if(!Graph->G[E->V1].FirstEdge)
    {

        NewNode->Next = Graph->G[E->V1].FirstEdge;
        Graph->G[E->V1].FirstEdge = NewNode;
    }
    else if(Graph->G[E->V1].FirstEdge&&!Graph->G[E->V1].FirstEdge->Next)
    {
        if(NewNode->AdjV < Graph->G[E->V1].FirstEdge->AdjV)
        {
            NewNode->Next = Graph->G[E->V1].FirstEdge;
            Graph->G[E->V1].FirstEdge = NewNode;
        }else{
            NewNode->Next = Graph->G[E->V1].FirstEdge->Next;
            Graph->G[E->V1].FirstEdge->Next = NewNode;
        }
    }
    else{
        for(W = Graph->G[E->V1].FirstEdge;W;W=W->Next)
        {
            if(!W->Next||(W->Next->AdjV > NewNode->AdjV))
            {
                NewNode->Next = W->Next;
                W->Next = NewNode;
                break;
            }
        }
    }
}

LGraph BuildGraph()
{
    Edge E1,E2;
    scanf("%d",&N);
    LGraph Graph = CreatGraph(N);
    scanf("%d",&Graph->Ne);
    E1 = (Edge)malloc(sizeof(struct ENode));
    E2 = (Edge)malloc(sizeof(struct ENode));
    for(int i=0;i<Graph->Ne;i++)
    {
        scanf("%d %d",&E1->V1,&E1->V2);
        InsertEdge(Graph,E1);
        E2->V1 = E1->V2;
        E2->V2 = E1->V1;
        InsertEdge(Graph,E2);
    }
    return Graph;
}
void Visit(Vertex V)
{
    printf("%d ",V);
}
void DFS(LGraph Graph,Vertex V,void (*Visit)(Vertex))
{
    PtrToAdjNode W;
    Visit(V);
    Visited[V] = 1;
    for(W = Graph->G[V].FirstEdge;W;W = W->Next)
    {
        if(!Visited[W->AdjV])
            DFS(Graph,W->AdjV,Visit);
    }
}

void BFS(LGraph Graph,Vertex S,void (*Visit)(Vertex))
{
    Vertex V;
    PtrToAdjNode W;
    Queue Q = CreatQuene(MaxVertexNum);

    Visit(S);
    Visited[S] = 1;
    AddQ(Q,S);

    while(!IsEmpty(Q))
    {
        V = DeleteQ(Q);
        for(W = Graph->G[V].FirstEdge;W;W = W->Next)
        {
            if(!Visited[W->AdjV])
            {
                Visit(W->AdjV);
                Visited[W->AdjV] = 1;
                AddQ(Q,W->AdjV);
            }
        }
    }
}

Queue CreatQuene(int MaxSize)
{
    Queue Q = (Queue)malloc(sizeof(struct QueueNode));
    Q->Elements = (int *)malloc(sizeof(int)*MaxSize);
    Q->Front = Q->Rear = 0;
    return Q;
}

void AddQ(Queue Q,Vertex V)
{
    Q->Elements[Q->Rear++] = V;
}

Vertex DeleteQ(Queue Q)
{
    return Q->Elements[Q->Front++];
}

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