图的遍历

没有用的话qaq :
Ummmm…图论的大部分知识本来早就有学过，只是一直没有写成博文来梳理，但既然上了qbxt DP图论就写一篇来总结下，主要是来听DP的，但…由于太菜的原因，DP听得天花乱坠QWQ

图的遍历分为两种，图的深度优先遍历和图的广度优先遍历，深度优先遍历是用栈来实现的，可以用手写栈，也可以递归（要小心没开栈的时候爆栈）

一，图的深度优先遍历
实现很简单，和dfs一样，分为以下几个步骤
1，从起点s开始遍历
2，当遍历到节点u时，如果u节点没有被访问过，那么就访问u在访问u没有被访问过的相邻节点，一直到头....
3,当所有节点都被访问之后，遍历结束。

inline void dfs(int s)
{
    vis[s]=true;
    for(int i=first[s];i;i=edge[i].nxt)
    {
        if(!vis[edge[i].ed]) dfs(edge[i].ed);
    }
} 

二叉树的三种dfs序：先序遍历，中序遍历，后序遍历

1，前序遍历：先访问根节点，然后依次访问每一棵子树，如上述过程一样。
比如上图的先序遍历为B,F,E,K,L
2,中序遍历：先访问左子树，再访问根节点，再访问右子树。
比如上图的中序遍历为F,B,K,E,L
3,后序遍历：先访问左子树，再访问右子树，最后访问根节点
比如上图的后序遍历为F,K,L,E,B
*
二，图的广度优先遍历
就像广搜一样，一层一层的访问
算法流程如下：
1，创建一个包含起点的队列
2，取出队首结点，将相邻的未入队结点加入队列
3，重复上一步直到所有结点都被遍历过
代码实现也并不难**

inline void bfs(int s)
{
    queue <int> q;
    q.push(s);
    vis[s]=true;
    while(!q.empty())
    {
        int p=q.front();
        q.pop();
        for(int i=first[s];i;i=edge[i].nxt)
        {
            if(!vis[edge[i].ed]) 
            {
                vis[edge[i].ed]=true;
                q.push(edge[i].ed);
            }
        }
    }
    return;
}

二叉树的层次遍历：依次访问每一层
比如上面的图的层次遍历是B,F,E,K,L

图的广度优先有所适用于无权图上的单源最短路问题（额边权为1）
可以借用DAG上DP求路径长度的思想，因为广度优先遍历是层次遍历，所以根节点到自己的路径长度为0，之后的每一层的未被访问过点的长度都是能找到它的节点的长度加一，因为是广度优先遍历，所以保证了正确性，大部分人可能不理解下面这种情况。

就是说，从1出发的单源最短路径，dis[1]=1,dis[2]=1;那么3不会由2转移成2吗，显然不会因为当2找到3时，3已经被1找到过，所以不能更新，所以所有节点的长度都是由第一次找到它的节点更新，一层一层的，保证了算法的正确性。

inline void bfs_dis(int s)
{
    memset(0,dis,sizeof(dis));
    queue<int>q;
    q.push(s);
    vis[s]=true;
    while(!q.empty())
    {
        int p=q.front(); q.pop();
        for(int i=first[p];i;i=edge[i].nxt)
        {
            int e=edge[i].ed;
            if(!vis[e])
            {
                dis[e]=dis[p]+1;
                q.push(e);
                vis[e]=true;
            }
        }
    }
}

三，图的遍历的一些小ques
1，给定一个有向图，边权为1 或2，求单源最短路
<法1>将边权为2的边拆成两条边权为1的边，再加一个不存在的中间点接上这两个边权为1的边，其他做法如上
<法2>开三个队列，5555

2,给出一个有向图和起点s，对每条边< u, v > 回答，如果删去这条边，从s 到v 的最短路长度是否会改变。
<法一>很简单，当时bfs的时候，有一条性质是d[e]=d[p]+1;我们只需要把满足这样性质的边留下来，包括点i被访问后，再次搜到这个点的边如果满足性质也要留下，这就构成了一个最短路图，如果一条边存在且这条边的终点的入度为1，那么将这条边删去的话就会影响最短路的长度，如果一个点的入度不为一，删去这条边也不会影响最短路的长度。

写在最后 Yousiki Orz Orz

图的遍历

原文：https://www.cnblogs.com/Hoyoak/p/11336491.html