PAT 05-1 List Components （简单DFS与BFS）

刚一拿到这道题把他想的太复杂了

明明是长度最大为十的顺序结构就能解决的问题，竟然优先想到用链表。

BFS牵扯到一个队列的操作，在这种小规模数据里面 用顺序结构好很多

题目如下：

For a given undirected graph with N vertices and E edges, please list all the connected components by both DFS and BFS. Assume that all the vertices are numbered from 0 to N-1. While searching, assume that we always start from the vertex with the smallest index, and visit its adjacent vertices in ascending order of their indices.

Input Specification:

Each input file contains one test case. For each case, the first line gives two integers N (0<N<=10) and E, which are the number of vertices and the number of edges, respectively. Then E lines follow, each described an edge by giving the two ends. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in each line a connected component in the format "{ v1 v2 ... vk }". First print the result obtained by DFS, then by 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>
void DFS(int i);
void BFS(int i);int vertice[10][10];   
int flag[10];          
int n,e; int main()
{int i,j,k;scanf("%d%d",&n,&e);int a,b;for (i=0;i<e;i++){scanf("%d%d",&a,&b);vertice[a][b] = vertice[b][a] = 1;}for (i=0;i<n;i++){if (flag[i]==1) continue;else  printf("{ "),DFS(i),printf("}\n");}for(i=0;i<10;i++)flag[i] = 0;for (i=0;i<n;i++){if (flag[i]==1) continue;else printf("{ "),BFS(i),printf("}\n");}
}void DFS(int i)
{printf("%d ",i),flag[i] = 1;int j;for (j=0;j<n;j++)if (vertice[i][j]==1&&flag[j]==0){DFS(j);}
}void BFS(int i)
{int start,end,Q[100];start = end = 0;Q[end++] = i;flag[i] = 1;int temp,j;while (start<end){temp = Q[start++];printf("%d ",temp);for (j=0;j<n;j++)if (vertice[temp][j]==1&&flag[j]==0){Q[end++] = j;flag[j] = 1;}}
}