11月29日星期六9:00-12:00

S+02L01【入门】图的dfs遍历

描述

一个有n个结点的无向连通图，这些结点以编号：1、2、……n进行编号，现给出结点间的连接关系。请以结点1为起点，按dfs（深度优先搜索）、优先访问小编号结点的顺序遍历并输出该图。

输入描述

第一行为两整数，n和e，表示n个顶点，e条边。（2<=n,e<=10）

以下e行每行两个数，表示两个结点是联通的。

输出描述

只有一行，为按照优先访问小编号结点的dfs的结果。

用例输入 1

5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5

用例输出 1

1 2 4 5 3

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,num[21][21];//邻接矩阵
int num2[110];//该点是否走过
void dfs(int x){//走到X点
    cout<<x<<" ";
    num2[x]=1;
    //判断1-n结点是否能走,并且没有走过,就递归走到X点
    for(int i=1;i<=n;i++){
        if(num[x][i]==1&&num2[i]==0){
            dfs(i);
        }
    }
}
int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        num[x][y]=1;
        num[y][x]=1;
    }
    dfs(1);
    return 0;
}

S+02L02【入门】图的bfs遍历

描述

一个有n个结点的无向连通图，这些结点以编号：1、2、……n进行编号，现给出结点间的连接关系。请以结点1为起点，按广度优先搜索（bfs）、优先访问小编号结点的顺序遍历并输出该图。

输入描述

第一行为两整数，n和e，表示n个顶点，e条边；（2<=n,e<=10）

以下e行每行两个数，表示两个结点是联通的。

输出描述

只有一行，为节点按照广度优先、小编号结点优先访问的结果。

用例输入 1

5 7
1 2
1 3
1 4
2 4
2 5
3 5
4 5

用例输出 1

1 2 3 4 5

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,num[21][21];//邻接矩阵
int num2[110];//该点是否走过
int q[100],head=1,tail=1;//模拟队列
int main() {
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        num[x][y]=1;
        num[y][x]=1;
    }
    q[tail]=1;
    num2[1]=1;//走过赋值为1
    //开始广搜 搜索的条件
    while(head<=tail){
        for(int i=1;i<=n;i++){
            if(num[q[head]][i]==1&&num2[i]==0){
                tail++;
                q[tail]=i;
                num2[i]=1;
            }
        }
        cout<<q[head]<<" ";
        head++;
    }
    return 0;
}

作业S04Z05