树与图的深度优先遍历（总结向，dfs序，深度和重心）

拼搏现实的明天。 2021-09-15 23:46 240阅读 0赞

# **dfs** #

## 1 ##

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

## 2 ##

VI e[maxn];
    void dfs(int u)
    {
        vis[u] = 1;
        for(auto &v:e[u])
        {
            if(!vis[v])
            {
                dfs(v);
            }
        }
    }

# 树的dfs序 #

就是递归后和回溯前记录一次该点的编号

## 1 ##

void dfs(int x)
    {
        a[++m] = x;
        vis[x] = 1;
        for(int i = head[x];i;i = next[i])
        {
            int y = ver[i];
            if(vis[y])
                continue;
            dfs(y);
        }
        a[++m] = x;
    }

## 2 ##

void dfs(int u)
    {
        a[++m] = u;
        vis[u] = 1;
        for(auto &v : e[u])
        {
            if(!vis[v])
            {
                dfs(v);
            }
        }
        a[++m] = u;
    }

# 树的深度 #

根节点的深度为0，若节点x  x 的深度为d\[x d \[ x\]，那么子节点y  y 的深度为d\[y\]=d\[x\]\+1 d \[ y \] = d \[ x \] \+ 1;

## 1 ##

void dfs(int x)
    {
        vis[x] = 1;
        for(int i = head[x];i;i = next[i])
            {
                int y = ver[x];
                if(vis[y]) continue;
                d[y] = d[x] + 1;
                dfs(y);
            }
    }

## 2 ##

void dfs(int u)
    {
        vis[u] = 1;
        for(auto &v : e[u])
        {
            if(!vis[v])
            {
                d[v] = d[u] + 1;
                dfs(v);
            }
        }
    }

# 树的重心 #

自底向下统计，以节点x  x 为根的子树大小为size\[x\] s i z e \[ x \]，节点x  x 有k k个节点y1,y2,...,yk  y 1 , y 2 , . . . , y k ,size\[x\]=size\[y1\]\+size\[y2\]\+...\+size\[yk\]\+1  s i z e \[ x \] = s i z e \[ y 1 \] + s i z e \[ y 2 \] + . . . + s i z e \[ y k \] + 1 ;  
对于一个节点，如果我们将它删去，那么一棵树可能分成若干个子树，设max  m a x *part(x)  p a r t ( x ) 为删去节点后产生的最大的一棵子树的大小。使max  m a x* part(x)  p a r t ( x ) 取最小值的节点p  p <script type="math/tex" id="MathJax-Element-1563">p</script>为重心

## 1 ##

void dfs(int x)
    {
        vis[x] = 1;
        size[x] = 1;
        int ma = 0;
        for(int i = head[x];i;i = next[i])
        {
            int y = ver[i];
            if(vis[y]) continue;
            dfs(y);
            size[x] += size[y];
            ma = max(ma,size[y]);
        }
        ma = max(ma,n - size[x]);
        if(ma < ans)
        {
            ans = ma;//重心对应的maxpart值
            pos = x;//重心位置
        }
    }

## 2 ##

void dfs(int u)
    {
        vis[u] = 1;
        size[u] = 1;
        int ma = 0;
        for(auto &v : e[u])
        {
            if(!vis[v])
            {
                dfs(v);
                size[u] += size[v];
                ma = max(ma,size[v]);
            }
        }
        ma = max(ma,n - size[x]);
        if(ma < ans)
        {
            ans = ma;
            pos = x;
        }
    }