题目：

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

输入格式:

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

输出格式:

按照"{ v​1​​ v​2​​ ... v​k​​ }"的格式，每行输出一个连通集。先输出DFS的结果，再输出BFS的结果。

输入样例:

8 60 70 12 04 12 43 5

输出样例:

{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 } 心得体会： 这道题的解题思路还是比较清晰的 即对于两个遍历的运用 解决这道题的思路是： ①建立起一个图并且填充 ②完成DFS遍历 ③完成BFS遍历 ① 根据题意可以选择以邻接矩阵的数据结构来建立图 首先是根据题意定义一个图的结构体

struct graph{
        int arcs[mvnum][mvnum];//邻接矩阵    int vexnum, arcnum;//顶点数 边数};

然后是图的填充

void creategraph(graph &g){    cin >> g.vexnum >> g.arcnum;//输入顶点与边数    int a, b;//端点编号    for (int i = 0; i < g.arcnum; ++i)    {        cin >> a >> b;//输入相连的端点编号        g.arcs[a][b] = g.arcs[b][a] = 1;//在邻接矩阵中将两端点状态赋值为相连    }}

 ②

  DFS遍历

  首先是定义一个访问数组

bool visited[mvnum];//访问数组

     然后为完成遍历连通图部分

void dfs(graph g, int v){    cout << " "<

 

  最后为完成非连通图部分

void dfss(graph g){    for (int j = 0; j < g.vexnum; ++j)    {        if (!visited[j])//若有端点未被访问        {            cout << "{
    ";            dfs(g, j);            cout << " }"<

 

 ③

 BFS遍历

 首先还是定义一个访问数组

bool visit[mvnum];

    

 然后为完成遍历连通图部分

void bfs(graph g,int v){    int x;//队头元素    cout << " " << v; //输出当前访问端点编号    visit[v] = 1; //将其作为访问数组下标，赋值其状态为已访问    queue
     
       q; //存放端点编号队列    q.push(v);//v入队    while(!q.empty()) //当队列为空时结束循环    {        x = q.front();//取队头元素        q.pop();//队头元素出队        for (int i = 0; i < g.vexnum; ++i)        {            if (!visit[i] && g.arcs[x][i] == 1)//若该端点编号i未被访问过，且其与当前所访问端点x相连            {                cout << " "<
     

 

  最后最后为完成非连通图部分

void bfss(graph g){    for (int i = 0; i < g.vexnum; ++i)    {                if (!visit[i])//若有端点未被访问        {            cout << "{
    ";            bfs(g, i);            cout << " }" << endl;        }    }}

 

 需要注意的地方：

  弄清循环条件，究竟是图的边数还是顶点数

 

目标完成情况： 与之前相比，找出入手点能力有所提高

目标：

提高对“图”方面知识的认识与理解，并能运用