《算法导论》22.2 广度优先搜索 (含C++代码)

《算法导论》22.2 广度优先搜索 (含C++代码),第1张

一、相关概念

1、在广度优先搜索中,给定一个图G(u,v)和一个可以识别的源结点s,广度优先搜索可以用来发现从源结点s到达的所有结点。这个class="superseo">算法最终可以生成一个“广度优先搜索树”,以s为根结点,包含所有从s可以到达的结点。对于每个从源结点s可以到达的结点v,在广度优先搜索树里从结点s到结点0的简单路径,所对应的就是图G中从结点s到结点u的“最短路径”,即包含最少边数的路径。该算法既可以用于有向图,也可以用于无向图。
2、算法需要在发现所有距离源结点s为k的所有结点之后,才会发现k+1以外的结点,这就是“广度”的由来。
3、在搜索中,我们会给结点涂上白、灰、黑三色。所有结点一开始均涂上白色,第一次发现后作为发现和未发现结点的边界就变成灰色,已经发现且不是边界的就是黑色。
4、大致过程:一开始只有根结点s;扫描一发现结点u的邻接链表时,每发现一个白色结点,就将其和边(u,v)加入这棵树。u为v的前驱或者父结点。

二、广度优先搜索算法
BFS(G,s)
//将所有结点初始化
for each vertex u ∈ G.V - {s}
	u.color = WHITE
	u.d = ∞
	u.π = NIL
//s已经被发现
s.color = GRAY
s.d = 0
s.π = NIL
//初始化队列
Q = ∅
ENQUEUE(Q,s)
//通过循环取出队头元素
while(Q != ∅)
{
	u = DEQUEUE(Q)	//将队头元素取出
	for each v ∈ G.Adj[u]	//遍历u的相关链表,找到未发现结点
		if v.color  = WHITE
			v.color = GRAY
			v.d = u.d + 1
			v.π = u
			ENQUEUE(Q,v)
	u.color = BLACK	//将取出的元素变为black,因为它已经不是边界了
}

三、最短路径





四、广度优先树



下面伪代码会打印出从源节点s到结点v的一条最短路径上的所有结点,这里假定BFS已经计算出一棵广度优先树。

PRINT-PATH(G,s,v)
if v == s
	print s
else if v.π == NIL
	print "no path from s to v"
else PRINT-PATH(G,s,v.π)	//一直向上递归,直到s,打印完s以后,返回打印后面路径上的所有结点
	print v
#include 
using namespace std;
#include 
#include 
#include 
#include 

//枚举三种颜色
enum Color{white=0, gray, black};

//定义顶点类型
struct Vertex
{
	enum Color color;	//颜色属性
	int d;	//距离源结点的距离
	Vertex* pre;	//前驱结点
	char name;	//每一个结点的编号
	Vertex(char n):name(n),pre(NULL),d(0),color(white){}
};

struct Graph
{
	vector<Vertex*>v;//顶点集合
	map<char, list<Vertex*>>Adj;//邻接链表,用顶点查找
};

//初始化邻接链表
Graph Init_graph()
{
    Graph G;
    G.v = { new Vertex('r'),new Vertex('v'),new Vertex('s'),new Vertex('w'),
        new Vertex('t'),new Vertex('x'),new Vertex('u'),new Vertex('y') };
    //初始化邻接链表
    G.Adj['r'] = { G.v[1],G.v[2] };
    G.Adj['s'] = { G.v[3],G.v[0] };
    G.Adj['w'] = { G.v[2],G.v[4],G.v[5] };
    G.Adj['t'] = { G.v[5],G.v[1],G.v[6] };
    G.Adj['x'] = { G.v[4],G.v[3],G.v[6],G.v[7] };
    G.Adj['u'] = { G.v[4],G.v[5],G.v[7] };
    G.Adj['y'] = { G.v[5],G.v[6] };
    G.Adj['v'] = { G.v[0] };
    return G;
}

//广度优先遍历
Graph Bfs(Graph g, Vertex *ve)
{
    ve->color = gray;
    ve->d = 0;
    deque<Vertex*>q;//创建一个双端队列
    q.push_back(ve);
    while (!q.empty()) {
        Vertex* head = q.front();
        //头元素出列
        q.pop_front();
        char n = head->name;
        //遍历每一个ve的结点
        for (Vertex *v : g.Adj[n]) {
            //遇到一个未知节点就将其改为灰色,同时更新其他属性
            if (v->color == white) {
                v->color = gray;
                v->pre = head;
                v->d = head->d + 1;
                q.push_back(v);
            }
        }
        //ve不再为边界
        head->color = black;
    }
    return g;
}

//打印源结点ve到v的最短路径
void print_path(Graph g,Vertex *ve,Vertex*v)
{
    //如果v等于ve,那么直接打印
    if (ve == v) {
        cout << v->name<<"  ";
    }
    else if(v->pre == NULL) {
        cout << "Can't find the path..." << endl;
    }
    else {
        print_path(g, ve, v->pre);
        cout << v->name<<"  ";
    }
}

int main()
{
    Graph G = Init_graph();
    G = Bfs(G, G.v[2]);//根结点为s
    print_path(G, G.v[2], G.v[6]);//查找u
    return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/3002868.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-27
下一篇 2022-09-27

发表评论

登录后才能评论

评论列表(0条)

保存