数据结构试验课——树的bfs遍历,dfs遍历

//********INPUT********
/*
8 8
1 2
1 3
2 4
2 5
4 8
5 8
3 6
3 7
*/
//********INPUT********

//********OUTPUT*******
/*
用dfs跑邻接矩阵 : 1 2 4 8 5 3 6 7 
用dfs跑邻接表   : 1 2 4 8 5 3 6 7 
用bfs跑邻接矩阵 : 1 2 3 4 5 6 7 8 
用bfs跑邻接表   : 1 2 3 4 5 6 7 8 
*/
//********OUTPUT*******

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

int a[205][205];

//***************
//  a数组是邻接矩阵:a[x][y]==1 表示x到y有一条长度为1 的边,即x到y有边相连
//*************** 

vector<int> v[205]; 
//***************
//  v数组是邻接表:v是动态数组,比如v[1]的长度为2,并且v[1][0]==2;v[1][2]==3;
//              这个的意思就是,顶点1有两条边,第一条边指向2;第二条边指向3; 
//*************** 

int n;//顶点数 
int m;//边数 
int ans[200050];
int len=0;
bool flag[205];

//***********************************
//  dfs_Arccell:用dfs跑邻接矩阵 
//***********************************
void dfs_Arccell(int x) //1
{
    ans[len++]=x;
    flag[x]=false;
    for(int i=1;i<=n;i++)
    {
        if(flag[i]&&a[x][i])
        {
            dfs_Arccell(i);
        }
    }
}

//***********************************
//  dfs_AdjList:用dfs跑邻接表 
//***********************************
void dfs_AdjList(int x)
{
    ans[len++]=x;
    flag[x]=false;
    //***********
    //下面的to是指和x相连的点 
    //***********
    for(int i=0;i<v[x].size();i++)
    {
        int to=v[x][i];
        if(flag[to])
        {
            dfs_AdjList(to);
        }
    }
}
//***********************************
//  bfs_Arccell:用bfs跑邻接矩阵 
//***********************************
void bfs_Arccell(int x)
{
    queue<int> Q;
    Q.push(x);
    flag[x]=false; 
    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        ans[len++]=node;

        for(int i=1;i<=n;i++)
            if(a[node][i] && flag[i]){
                //****************
                //如果node->i 这条边存在且i这个顶点没被访问过 
                //****************
                flag[i]=false;
                Q.push(i);
            }
    }
}

//***********************************
//  bfs_AdjList:用bfs跑邻接表 
//***********************************
void bfs_AdjList(int x)
{
    queue<int> Q;
    Q.push(x);
    flag[x]=false; 
    while(!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        ans[len++]=node;

        for(int i=0;i<v[node].size();i++)
        {
            int to=v[node][i];
            if(flag[to]){
                //****************
                //如果node->to 这条边存在且to这个顶点没被访问过 
                //****************
                flag[to]=false;
                Q.push(to);
            }           
        }

    }
}

void Print_Ans(string s)
{
    cout<<s<<": ";
    for(int i=0;i<len;i++)
        cout<<ans[i]<<" ";
    cout<<endl; 
}

int main()
{
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout); 
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        a[x][y]=1;

        v[x].push_back(y);

    }

    //***********************************
    //  dfs_Arccell:用dfs跑邻接矩阵 
    //***********************************
    memset(flag,true,sizeof(flag));
    len=0;
    dfs_Arccell(1);
    Print_Ans("用dfs跑邻接矩阵 ");

    //***********************************
    //  dfs_AdjList:用dfs跑邻接表 
    //***********************************
    memset(flag,true,sizeof(flag));
    len=0; 
    dfs_AdjList(1);
    Print_Ans("用dfs跑邻接表   ");

    //***********************************
    //  bfs_Arccell:用bfs跑邻接矩阵 
    //***********************************
    memset(flag,true,sizeof(flag));
    len=0;
    bfs_Arccell(1);
    Print_Ans("用bfs跑邻接矩阵 ");

    //***********************************
    //  bfs_AdjList:用bfs跑邻接表 
    //***********************************
    memset(flag,true,sizeof(flag));
    len=0;
    bfs_AdjList(1);
    Print_Ans("用bfs跑邻接表   ");

    return 0;
}

您可能还喜欢...

发表评论

电子邮件地址不会被公开。 必填项已用*标注