图的遍历

深度优先DFS

DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况。

DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样。有关该类搜索思想请参阅 DFS（搜索）.

DFS 最显著的特征在于其 递归调用自身。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次。符合以上两条规则的函数，便是广义上的 DFS。

该算法通常的时间复杂度为 O(n+m)，空间复杂度为 O(n)，其中 n 表示点数，m 表示边数。注意空间复杂度包含了栈空间，栈空间的空间复杂度是 O(n) 的。在平均 O(1) 遍历一条边的条件下才能达到此时间复杂度，例如用前向星或邻接表存储图；如果用邻接矩阵则不一定能达到此复杂度。

备注：目前大部分算法竞赛（包括 NOIP、大部分省选以及 CCF 举办的各项赛事）都支持 无限栈空间，即：栈空间不单独限制，但总内存空间仍然受题面限制。但大部分操作系统会对栈空间做额外的限制，因此在本地调试时需要一些方式来取消栈空间限制。

在 Windows 上，通常的方法是在 编译选项 中加入 -Wl,--stack=1000000000，表示将栈空间限制设置为 1000000000 字节。在 Linux 上，通常的方法是在运行程序前 在终端内 执行 ulimit -s unlimited，表示栈空间无限。每个终端只需执行一次，对之后每次程序运行都有效。

栈实现

邻接表存储图的深度优先算法

Graph g = new Graph(NODES_SUM);
//更新图

// 从s点开始遍历
vector<int>& Graph::dfs(const int s){
    stack<int> st; //辅助栈
    vector<int> visited; //标记容器，记录结点是否已经遍历
    visited.push_back(s);
    st.push(s);
    while(!st.empty()){
        int last = st.top(); //上一个访问的元素
        for(int to : edges[last]){
            if(find(all(visited),to) == visited.end()){
                visited.push_back(to); //确保栈里没有元素
                st.push(to);
            }
        }
        st.pop(); //出栈
    }
    return visited;
};
cout << g.dfs(2) << endl;

警告

这里是根据OI wiki中内容改写。 但笔者觉得是有问题， 还在等待原作者的答疑。

递归实现

void recursion_dfs(const int u, vector<int>& visited, vector<vector<int>>& edges) {
    visited.push_back(u);
    for(int v : edges[u])
        if (find(all(visited),to) == visited.end()) 
            recursion_dfs(v)
}

vector<int> Graph::dfs(const int u){
    vector<int> visited;
    recursion_dfs(u,visited,edges);
}
Graph g = new Graph(NODES_SUM);
g.dfs(2);

对于非连通图，只能访问到起点所在的连通分量。

对于连通图，DFS 序列通常不唯一。

注：树的 DFS 序列也是不唯一的。

在 DFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 DFS 树。DFS 树是原图的一个生成树。

DFS 树 有很多性质，比如可以用来求 强连通分量。

广度优先BFS

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

这样做的结果是，BFS 算法找到的路径是从起点开始的 最短 合法路径。换言之，这条路径所包含的边数最小。

在 BFS 结束时，每个节点都是通过从起点到该点的最短路径访问的。

算法过程可以看做是图上火苗传播的过程：最开始只有起点着火了，在每一时刻，有火的节点都向它相邻的所有节点传播火苗。

队列实现

bool visited[MAXSIZE];//访问标记
int Q[MAXSIZE],front=0,rear=0;
Edge edge;

void enQue(int v){
    rear=(rear + 1) % MAXSIZE;
    Q[rear]=v;
}

void deQue(int &v){
    front=(front+1) % maxSize;
    v=Q[front];
}

void isEmpty(){
    return front==rear?1:0
        }

void visit(int v){
    visited[v] = TRUE;
}

// 非连通图循环访问
void traverse(Graph &G){
    for(int i = 0;i<G.info.node_num;++i)
        if(visit[i]==0) BFS(g,i)
            }

void BFS（Graph &G,int id){
    //访问
    visit(id);
    //入队
    enQue(id);
    //循环遍历
    while(!isEmpty()){
        deQue(v);
        edge=G.nodes[id].first;
        while(edge){
            if(!visited[edge.to_node]){
                visit(edge.to_node);
                enQue(edge.to_node);
            }
            edge=edge.next;
        }
    }
}

深度优先和广度优先算法的对比

深度优先搜索(回溯法) 算法思路 深度优先搜索(DFS,Depth-First Search)是搜索的手段之一 它从某个状态开始,不断地转移状态直到无法转移,然后回退到前一步状态,继续转移到其他状态,如此不断重复,直到找到最终的解.根据深度优先搜索的特点,采用递归函数(隐式地利用了栈进行计算)实现比较简单.

算法效率 深度优先搜索从最开始的状态出发,遍历所有可以到达的状态.由此可以对所有的状态进行操作,或列举出所有的状态.作为搜索算法的一种,DFS对于寻找一个解的NP(包括NPC)问题作用很大.

但是,搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率比较低,在数据规模变大时,这种算法就显得力不从心了.关于深度优先搜索的效率问题,有多种解决方法.最具有通用性的是**剪枝(prunning),**也就是去除没有用的搜索分支.有可行性剪枝和最优性剪枝两种.此外,对于很多问题,可以把搜索与动态规划(DP,dynamic programming)、完备匹配(匈牙利算法)等高效算法结合.

2.宽度优先搜索(分支限界法) 算法思路 宽度优先搜索(BFS,Breadth-First Search)也是搜索的手段之一.他与深度优先搜索类似,从某个状态出发搜索所有可以到达的状态.根据宽度优先搜索的特点,采用队列实现比较简单.

算法效率 与深度优先不同之处在与搜索的顺序,宽度优先搜索总是先搜索距离初始状态近的状态.也就是说,它是按照开始状态->只需1次转移就可以到达的所有状态->只需2次转移就可以到达的所有状态->…这样的顺序进行搜索.对于同一个状态,宽度优先搜索只经过一次,因此复杂度为

O(状态数*转移的方式).很容易地用来求最短路径、最少操作之类问题的答案.

广度搜索的判断重复如果直接判断十分耗时,我们一般借助哈希表来优化时间复杂度.

3.Death-Breadth总结 宽度优先搜索与深度优先搜索一样,都会生成所有能够遍历到的状态,因此需要对所有状态进行处理时使用宽度优先也是可以的.但是递归函数可以很简短地编写,而且状态的管理也更简单,所以大多数情况下还是用深度优先搜索实现.反之,在求取最短路时深度优先搜索需要反复经过同样的状态,所以还是使用宽度优先搜索比较好.

宽度优先搜索会把状态逐个加入队列,因此通常需要与状态数成正比的内存空间.反之,深度优先搜索是与最大的递归深度成正比的.一般与状态数相比,递归的深度并不会太大,所以可以认为深度优先搜索更加节省内存.

具体来说，我们用一个队列 Q 来记录要处理的节点，然后开一个布尔数组 vis[] 来标记是否已经访问过某个节点。

开始的时候，我们将所有节点的 vis 值设为 0，表示没有访问过；然后把起点 s 放入队列 Q 中并将 vis[s] 设为 1。

之后，我们每次从队列 Q 中取出队首的节点 u，然后把与 u 相邻的所有节点 v 标记为已访问过并放入队列 Q。

循环直至当队列 Q 为空，表示 BFS 结束。

在 BFS 的过程中，也可以记录一些额外的信息。例如上述代码中，d 数组用于记录起点到某个节点的最短距离（要经过的最少边数），p 数组记录是从哪个节点走到当前节点的。

有了 d 数组，可以方便地得到起点到一个节点的距离。

有了 p 数组，可以方便地还原出起点到一个点的最短路径。上述代码中的 restore 函数使用该数组依次输出从起点到节点 x 的最短路径所经过的节点。

时间复杂度 O(n + m)

空间复杂度 O(n)（vis 数组和队列）

在实现 BFS 的时候，本质上我们把未被访问过的节点放在一个称为 open 的容器中，而把已经访问过了的节点放在一个称为 closed 容器中。

BFS 序列 类似 DFS 序列，BFS 序列是指在 BFS 过程中访问的节点编号的序列。

一般图上 BFS 如果原图不连通，只能访问到从起点出发能够到达的点。

BFS 序列通常也不唯一。

类似的我们也可以定义 BFS 树：在 BFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，即为 BFS 树。

在一个无权图上求从起点到其他所有点的最短路径。 在 O(n+m) 时间内求出所有连通块。（我们只需要从每个没有被访问过的节点开始做 BFS，显然每次 BFS 会走完一个连通块） 如果把一个游戏的动作看做是状态图上的一条边（一个转移），那么 BFS 可以用来找到在游戏中从一个状态到达另一个状态所需要的最小步骤。 在一个有向无权图中找最小环。（从每个点开始 BFS，在我们即将抵达一个之前访问过的点开始的时候，就知道遇到了一个环。图的最小环是每次 BFS 得到的最小环的平均值。） 找到一定在 (a, b) 最短路上的边。（分别从 a 和 b 进行 BFS，得到两个 d 数组。之后对每一条边 (u, v)，如果 d_a[u]+1+d_b[v]=d_a[b]，则说明该边在最短路上） 找到一定在 (a, b) 最短路上的点。（分别从 a 和 b 进行 BFS，得到两个 d 数组。之后对每一个点 v，如果 d_a[v]+d_b[v]=d_a[b]，则说明该点在某条最短路上） 找到一条长度为偶数的最短路。（我们需要一个构造一个新图，把每个点拆成两个新点，原图的边 (u, v) 变成 ((u, 0), (v, 1)) 和 ((u, 1), (v, 0))。对新图做 BFS，(s, 0) 和 (t, 0) 之间的最短路即为所求） 在一个边权为 0/1 的图上求最短路，见下方双端队列 BFS。

双端队列

边权值为可能有，也可能没有（由于 BFS 适用于权值为 1 的图，所以一般权值是 0 或 1），或者能够转化为这种边权值的最短路问题。

例如在走迷宫问题中，你可以花 1 个金币走 5 步，也可以不花金币走 1 步，这就可以用 0-1 BFS 解决。

优先队列

优先队列，相当于一个二叉堆，STL 中提供了 std::priority_queue，可以方便我们使用优先队列。

在基于优先队列的 BFS 中，我们每次从队首取出代价最小的结点进行进一步搜索。容易证明这个贪心思想是正确的，因为从这个结点开始扩展的搜索，一定不会更新原来那些代价更高的结点。换句话说，其余那些代价更高的结点，我们不回去考虑更新它。

当然，每个结点可能会被入队多次，只是每次入队的代价不同。当该结点第一次从优先队列中取出，以后便无需再在该结点进行搜索，直接忽略即可。所以，优先队列的 BFS 当中，每个结点只会被处理一次。

相对于普通队列的 BFS，时间复杂度多了一个 \log n，毕竟要维护这个优先队列嘛。不过普通 BFS 有可能每个结点入队、出队多次，时间复杂度会达到 O(n^2)，不是 O(n)。所以优先队列 BFS 通常还是快的。

诶？这怎么听起来这么像堆优化的 Dijkstra 算法呢？事实上，堆优化 Dijkstra 就是优先队列 BFS。