dfs和bfs(链式前向星实现)

时间:2021-06-27 07:55:29

dfs代码:

#include<iostream>
#include<Algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int cnt,m;
int head[50005];
bool s[50005]={0};
struct node
{
    int w;
    int to;
    int next;
}edge[50005];
void add(int u,int v,int w)
{
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    edge[cnt].to=v;
    head[u]=cnt++;
}
void dfs(int x)
{
    s[x] = true;
    printf("%d\n", x);
    for(int i= head[x];i!=-1;i=edge[i].next)//刚开始不太理解这里,其实就是循环一个点(比如u)的所有边(u-v,u-v1...)。。。递归是递归v的所有边。
    {
        if(!s[edge[i].to])
        {

dfs(edge[i].to);
        }
    }
}
int main()
{
    int n,x,y,w;
    while(cin>>n)
    {
        memset(head,-1,sizeof(head));
        for(int i=1;i<=n;i++)
        {
            cin>>x>>y;
            add(x,y,0);
        }
        dfs(1);
    }
        return 0;
}

/*1 2
2 3
3 4
1 3
4 1
1 5
4 5
edge[0].to=2;edge[0].next=-1;head[1]=0;
edge[1].to=3;edge[1].next=-1;head[2]=1;
edge[2].to=4;edge[2].next=-1;head[3]=2;
edge[3].to=3;edge[3].next= 0;head[1]=3;
edge[4].to=1;edge[4].next=-1;head[4]=4;
edge[5].to=5;edge[5].next= 3;head[1]=5;
edge[6].to=5;edge[6].next= 4;head[4]=6;*/

bfs代码:

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
struct node
{
    int to;
    int next;
    int w;
}edge[maxn];
int cnt;
int head[maxn];
bool s[maxn];
int que[maxn];
void add(int u,int v,int w)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    edge[cnt].w=w;
    head[u]=cnt++;
}
void bfs(int x)
{
    int i,j;
    int iq=0;
    que[iq++]=x;
    s[x]=true;
    for(i=0;i<iq;i++)
    {
        cout<<que[i]<<" ";
        for(j=head[que[i]];j!=-1;j=edge[j].next)
        {
            if(!s[edge[j].to])
            {
                que[iq++]=edge[j].to;
                s[edge[j].to]=true;
            }
        }
    }
}
int main()
{
    int n;
    int x,y;
    memset(head,-1,sizeof(head));
    while(cin>>n)
    {
        while(n--)
        {
        cin>>x>>y;
        add(x,y,0);
        }
        bfs(1);
    }
    return 0;
}