当前位置: 首页 > 工具软件 > dfs > 使用案例 >

图的遍历(DFS、DFS序,BFS)

吕和风
2023-12-01

一、DFS

const int maxn=100008;
int head[maxn],nt[maxn],ver[maxn],edge[maxn];
bool ha[maxn];
void DFS(int x)
{
    ha[x]=true;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(ha[y]) continue;
        DFS(y);
    }
    return ;
}
int main(void)
{
    //建图
    memset(ha,0,sizeof(ha));
    DFS(1);
    return 0;
}

这段代码访问每个点和每条边恰好一次(如果是无向边,正反向访问各一次),时间复杂度为O(N+M),N为节点个数,M为边数。

二、DFS序:
一般来讲,我们在对树进行深度优先遍历时,对于每个节点,在刚进入递归后以及即将回溯前各记录一次该点的编号,最后产生长度为2*N 的节点序列就称为树的DFS序;

const int maxn=100008;
int head[maxn],nt[maxn],ver[maxn],edge[maxn];
bool ha[maxn];
int a[maxn*2];
int m=0;
void DFS(int x)
{
    a[++m]=x;
    ha[x]=true;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(ha[y]) continue;
        DFS(y);
    }
    a[++m]=x;
    return ;
}
int main(void)
{
    //建图
    memset(ha,0,sizeof(ha));
    DFS(1);
    return 0;
}

特点:每个节点x的编号在序列中恰好出现两次。设两次出现的位置为Lx,Rx,那么闭区间
[Lx,Rx],就是以x为根的子树的DFS序

三、BFS:

const int maxn=100008;
int head[maxn],nt[maxn],ver[maxn],edge[maxn];
//树的深度d
int d[maxn];

void BFS(void)
{
    memset(d,0,sizeof(d));
    queue<int>q;
    q.push(1);
    d[1]=1;
    while(q.size())//while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nt[i])
        {
            int y=ver[i];
            if(d[y]) continue;
            d[y]=d[x]+1;
            q.push(y);
        }
    }
    return ;
}
int main(void)
{
    //建图

    BFS();
    return 0;
}

时间复杂度O(N+M)。
对于一棵树来讲,d[x]就是点x在树中的深度。
对于一张图来讲,d[x]被称为点x的层次(从起点1走到点x需要经过的最小点数)。

 类似资料: