PTA数据结构与算法题目集(中文) 7-6

7-6 列出连通集 (25 分)

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

输入格式:

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

输出格式:

按照"{ v1 v2 ... vk }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:

输出样例:

{ 0 1 4 2 7 }

{ 3 5 }

{ 6 }

{ 0 1 2 7 4 }

{ 3 5 }

{ 6 }

题目分析:考察图基本功能的实现 深度优先遍历和广度优先遍历的实现 注意因为有的点不连通 所以要遍历一边 所有图节点看是否还有未被收录的
深度优先遍历使用递归访问 广度优先遍历利用队列来进行访问

 #define _CRT_SECURE_NO_WARNINGS

 #include<stdio.h>

 #include<stdlib.h>

 #include<malloc.h>

 #define MaxVertexNum 100

 typedef struct ENode* Edge;

 struct ENode

 {

     int V1, V2;

 };

 typedef struct GNode* Graph;

 struct GNode

 {

     int Nv;

     int Ne;

     int G[MaxVertexNum][MaxVertexNum];

 };

 Graph BuildGraph(int VertexNum)

 {

     Graph Gra;

     Gra = (Graph)malloc(sizeof(struct GNode));

     Gra->Ne = ;

     Gra->Nv = VertexNum;

     for (int i = ; i < VertexNum; i++)

         for (int j = ; j < VertexNum; j++)

             Gra->G[i][j] = ;

     return Gra;

 }

 void InsertEdge(Edge E, Graph Gra)

 {

     Gra->G[E->V1][E->V2] = ;

     Gra->G[E->V2][E->V1] = ;

 }

 Graph CreatGraph()

 {

     Edge E;

     int N, M;

     scanf("%d%d", &N, &M);

     Graph G = BuildGraph(N);

     G->Ne = M;

     for (int i = ; i < M; i++)

     {

         E = (Edge)malloc(sizeof(struct ENode));

         int V1, V2;

         scanf("%d%d", &V1, &V2);

         E->V1 = V1;

         E->V2 = V2;

         InsertEdge(E, G);

     }

     return G;

 }

 int IsEdge(Graph G, int V1, int V2)

 {

     return G->G[V1][V2] == ;

 }

 int Collected[MaxVertexNum];

 void Initialize()

 {

     for (int i = ; i < MaxVertexNum; i++)

         Collected[i] = ;

 }

 void DFS(Graph G,int i)

 {

     printf("%d ", i);

     Collected[i] = ;

     for (int j = ; j < G->Nv; j++)

     {

         if (!Collected[j]&&IsEdge(G,i,j))

             DFS(G, j);

     }

 }

 int Queue[];

 int Front = ;

 int Rear = ;

 int Size = ;

 int Succ(int num)

 {

     if (num == )

         return ;

     else

         return num;

 }

 void EnQueue(int num)

 {

     Rear = Succ(Rear + );

     Queue[Rear] = num;

     Size++;

 }

 int DeQueue()

 {

     int Value = Queue[Front];

     Front = Succ(Front + );

     Size--;

     return Value;

 }

 int IsEmpty()

 {

     return Size == ;

 }

 void BFS(Graph G,int i)

 {

     EnQueue(i);

     Collected[i] = ;

     while (!IsEmpty())

     {

         int Tmp = DeQueue();

         printf("%d ", Tmp);

         for (int j = ; j < G->Nv; j++)

         {

             if (!Collected[j] && IsEdge(G, Tmp, j))

             {

                 EnQueue(j);

                 Collected[j] = ;

             }

         }

     }

 }

 int main()

 {

     Graph G=CreatGraph();

     for (int i = ; i < G->Nv; i++)

     {

         if (!Collected[i])

         {

             printf("{ ");

             DFS(G, i);

             printf("}");

             printf("\n");

         }

     }

     Initialize();

     for (int i = ; i < G->Nv; i++)

     {

         if (!Collected[i])

         {

             printf("{ ");

             BFS(G, i);

             printf("}");

             printf("\n");

         }

     }

     return ;

 }