0x21 树与图的遍历

0x21 树与图的遍历

1.树的深度遍历

void dfs(int x){
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(vis[y]) continue;
        dfs(y);
    }
}

2.时间戳

//dfn[]
//以每个节点第一次访问的顺序，依此打上1~N的标记，称为时间戳

3.树的DFS序

//记录各点dfs访问和回溯顺序的序列
//这个序列中，设两次出现位置为L[x],R[x],那么区间[ L[x] , R[x] ]  就是以x为根的子树的dfs序
//很多树相关问题，可以通过dfs序把子树统计转换为序列上的区间统计
void dfs(int x){
    a[++m]=x;       //a数组存储dfs序
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(vis[y])continue;
        dfs(y);
    }
    a[++m]=x;
}

4.树的深度

void dfs(int x){
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(vis[y]) continue;
        deep[y]=deep[x]+1;      //核心语句
        dfs(y);
    }
}

5.找树的重心·

//pos维护树的重心。

void dfs(int x){
    vis[x]=1;
    size[x]=1;
    int max_part=0;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(vis[y])continue;
        dfs(y);
        size[x]+=size[y];
        max_part=max(max_part,size[y]);
    }
    max_part=max(max_part,n-size[x]);
    if(max_part < ans){
        ans=max_part;
        pos=x;
    }
}

6.图的连通块划分

//cnt维护连通块编号，vis[]记录各节点所属连通块
void dfs(int x){
    vis[x]=cnt;
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(vis[y])continue;
        dfs(y);
    }
}
for(int i=1;i<=n;++i){  //在main()中
    if(!vis[i]){
        cnt++;
        dfs(i);
    }
}

0x21 树与图的遍历

原文：https://www.cnblogs.com/A-sc/p/12241480.html