数据结构(C++)——图的遍历算法:广度优先搜索、深度优先搜索、优先级搜索算法

算法:广度优先搜索、深度优先搜索、优先级搜索算法"/>

数据结构(C++)——图的遍历算法:广度优先搜索、深度优先搜索、优先级搜索算法

图的遍历算法

图的遍历都可以理解为，将非线性结构转化为半线性结构的过程。经遍历而确定的边类型中,最重要的一类即所谓的树边,它们与所有顶点共同构成了原图的一棵支撑树(森林),称作遍历树(traversal tree)。

广度优先搜索(BFS)

广度优先搜索(breadth-first search, BFS)采用的策略,可概括为:

    越早被访问到的定点，其邻居越优先被选用

于是,始自图中顶点s的BFS搜索,将首先访问顶点s;再依次访问s所有尚未访问到的邻居;再按后者被访问的先后次序,逐个访问它们的邻居;...;如此不断。在所有已访问到的顶点中,仍有邻居尚未访问者,构成所谓的波峰集(frontier)。

    广度优先搜索类似与树的层次遍历。

广度优先搜索算法实现：(BFS算法)

template <typename Tv, typename Te> //广度优先搜索BFS算法(全图)
void Graph<Tv, Te>::bfs(int s) { //assert: 0 <= s < nreset(); int clock = 0; int v = s; //初始化do //逐一检查所有顶点if (UNDISCOVERED == status(v)) //一旦遇到尚未发现的顶点BFS(v, clock); //即从该顶点出发启动一次BFSwhile (s != (v = (++v % n))); //按序号检查,故不漏不重
}template <typename Tv, typename Te> //广度优先搜索BFS算法(单个连通域)
void Graph<Tv, Te>::BFS(int v, int& clock) { //assert: 0 <= v < nQueue<int> Q; //引入辅助队列status(v) = DISCOVERED; Q.enqueue(v); //初始化起点while (!Q.empty()) { //在Q变空之前,不断int v = Q.dequeue(); dTime(v) = ++clock; //取出队首顶点vfor (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) //枚举v的所有邻居uif (UNDISCOVER