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 }

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

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<stdio.h>
  3 #include<stdlib.h>
  4 #include<malloc.h>
  5 #define MaxVertexNum 100
  6
  7 typedef struct ENode* Edge;
  8 struct ENode
  9 {
 10     int V1, V2;
 11 };
 12 typedef struct GNode* Graph;
 13 struct GNode
 14 {
 15     int Nv;
 16     int Ne;
 17     int G[MaxVertexNum][MaxVertexNum];
 18 };
 19
 20 Graph BuildGraph(int VertexNum)
 21 {
 22     Graph Gra;
 23     Gra = (Graph)malloc(sizeof(struct GNode));
 24     Gra->Ne = 0;
 25     Gra->Nv = VertexNum;
 26     for (int i = 0; i < VertexNum; i++)
 27         for (int j = 0; j < VertexNum; j++)
 28             Gra->G[i][j] = 0;
 29     return Gra;
 30 }
 31 void InsertEdge(Edge E, Graph Gra)
 32 {
 33     Gra->G[E->V1][E->V2] = 1;
 34     Gra->G[E->V2][E->V1] = 1;
 35 }
 36 Graph CreatGraph()
 37 {
 38     Edge E;
 39     int N, M;
 40     scanf("%d%d", &N, &M);
 41     Graph G = BuildGraph(N);
 42     G->Ne = M;
 43     for (int i = 0; i < M; i++)
 44     {
 45         E = (Edge)malloc(sizeof(struct ENode));
 46         int V1, V2;
 47         scanf("%d%d", &V1, &V2);
 48         E->V1 = V1;
 49         E->V2 = V2;
 50         InsertEdge(E, G);
 51     }
 52     return G;
 53 }
 54 int IsEdge(Graph G, int V1, int V2)
 55 {
 56     return G->G[V1][V2] == 1;
 57 }
 58 int Collected[MaxVertexNum];
 59 void Initialize()
 60 {
 61     for (int i = 0; i < MaxVertexNum; i++)
 62         Collected[i] = 0;
 63 }
 64 void DFS(Graph G,int i)
 65 {
 66     printf("%d ", i);
 67     Collected[i] = 1;
 68     for (int j = 0; j < G->Nv; j++)
 69     {
 70         if (!Collected[j]&&IsEdge(G,i,j))
 71             DFS(G, j);
 72     }
 73 }
 74
 75 int Queue[10];
 76 int Front = 1;
 77 int Rear = 0;
 78 int Size = 0;
 79 int Succ(int num)
 80 {
 81     if (num == 10)
 82         return 0;
 83     else
 84         return num;
 85 }
 86 void EnQueue(int num)
 87 {
 88     Rear = Succ(Rear + 1);
 89     Queue[Rear] = num;
 90     Size++;
 91 }
 92 int DeQueue()
 93 {
 94     int Value = Queue[Front];
 95     Front = Succ(Front + 1);
 96     Size--;
 97     return Value;
 98 }
 99 int IsEmpty()
100 {
101     return Size == 0;
102 }
103 void BFS(Graph G,int i)
104 {
105     EnQueue(i);
106     Collected[i] = 1;
107     while (!IsEmpty())
108     {
109         int Tmp = DeQueue();
110         printf("%d ", Tmp);
111         for (int j = 0; j < G->Nv; j++)
112         {
113             if (!Collected[j] && IsEdge(G, Tmp, j))
114             {
115                 EnQueue(j);
116                 Collected[j] = 1;
117             }
118         }
119     }
120 }
121 int main()
122 {
123     Graph G=CreatGraph();
124     for (int i = 0; i < G->Nv; i++)
125     {
126         if (!Collected[i])
127         {
128             printf("{ ");
129             DFS(G, i);
130             printf("}");
131             printf("\n");
132         }
133     }
134     Initialize();
135     for (int i = 0; i < G->Nv; i++)
136     {
137         if (!Collected[i])
138         {
139             printf("{ ");
140             BFS(G, i);
141             printf("}");
142             printf("\n");
143         }
144     }
145     return 0;
146 }

View Code