搜索基础题

2019/7/22 16:29:50 人评论 次浏览 分类:学习教程

**

题目描述

**
一个有n个节点的连通图,这些节点以编号:1、2、……n进行编号,现给出节点间的连接关系。请以节点1为起点,按dfs的顺序遍历并输出该图。


输入


第一行为两整数,n和e,表示n个顶点,e条边
以下e行每行两个数,表示两个节点是联通的

输出

只有一行,为节点的dfs顺序

**

样例输入

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

样例输出

1 2 4 5 3
AC_BFS_dode:

#include <bits/stdc++.h>
using namespace std;

const int mm=110;
int a[mm][mm],vis[mm],n,e;
queue <int> qu;

void bfs(int k)
{
    qu.push(k);
    vis[k]=1;
    while(!qu.empty())
    {
        int u=qu.front();
        qu.pop();
        cout<<u<<" ";
        for(int i=0;i<e;i++)
        {
            if(!vis[i] && a[u][i]==1)
            {
                bfs(i);
            }
        }
    }
}

main()
{
    cin>>n>>e;
    int x,y;
    memset(a,0,sizeof(a));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<e;i++)
    {
        cin>>x>>y;
        a[x][y]=a[y][x]=1;
    }
    bfs(1);
    cout<<endl;
}

AC_DFS_code:

#include <bits/stdc++.h>
using namespace std;

const int mm=110;
int a[mm][mm],vis[mm],n,e;

void dfs(int k)
{
    cout<<k<<" ";
    vis[k]=1;
    for(int i=0;i<e;i++)
    {
        if(vis[i]!=1 && a[i][k]==1)
        {
            dfs(i);
        }
    }
}

main()
{
    cin>>n>>e;
    int x,y;
    memset(a,0,sizeof(a));
    memset(vis,0,sizeof(vis));
    for(int i=0;i<e;i++)
    {
        cin>>x>>y;
        a[x][y]=a[y][x]=1;
    }
    dfs(1);
    cout<<endl;
}

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->