广度优先算法实现

‘壹’ 急！！C++深度优先算法和广度优先算法

以搜索为例，下面两种介绍了深搜与广搜的具体实现。
算法博大精深，望楼主好好学习啊
1. 深度搜索
void Graph::DFS(const int v, int visited[])
{
cout<<GetValue(v)<<"";//访问顶点 v
visited[v] = 1; //顶点 v 作访问标记
int w = GetFirstNeighbor(v););//取 v 的第一个邻接顶点 w
while(w != -1) //若邻接顶点 w 存在
{
if(!visited[w])//若顶点 w 未访问过, 递归访问顶点 w
DFS(w, visited);
w = GetNextNeighbor(v, w);//取顶点 v 的排在 w 后面的下一个邻接顶点
}
}
void Graph::UseDFS()
{
visited = new Boolean[n];
for(int i = 0; i < n; i++)
visited[i] = 0;
DFS(0);
delete[] visited;
}
算法分析：
(1)图中有 n 个顶点，e 条边。
(2)如果用邻接表表示图，沿 link 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。
(3)如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。
2. 广度优先搜索
void BFS(Graph G, int visited[])
{//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited.
for(v = 0; v < G.vexnum; v++)
visited[v] = false;
Quene q;
for(v = 0; v < G.vexnum; v++)
if(!visited[v])
{
visited[v] = true;
EnQuene(Q,v);
while(!QueneEmpty(Q))
{
DeQuene(Q,u);
for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))
if(!visited[w])
{
visited[w] = true;
EnQuene(Q, w);
}//if
}//while
}//if
}//BFS
算法分析：
每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深搜相同。

‘贰’ 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）

        深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。

一、深度优先搜索

        深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

基本步奏

（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。

（2）从stack中访问栈顶的点；

（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；

（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；

（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。

二、广度优先搜索

        广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

基本步奏

（1）给出一连通图，如图，初始化全是白色（未访问）；

（2）搜索起点V1（灰色）；

（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；

（4）对V2，V3，V4重复以上操作；

（5）直到终点V7被染灰，终止；

（6）最短路径为V1，V4，V7.

‘叁’ 用邻接表表示图的广度优先搜索时的存储结构,通常采用（）结构来实现算法

B。

广度优先搜索相当于层次遍历，深度优先搜索相当于先序优先遍历，所以答案选择B。

邻接表表示的图的广度优先搜索一般采用队列结构来实现算法：

首先选择一个起始节点，把它的临界表中节点加入到队列中，每次取出队首元素，然后把该元素的邻接表中的节点加入到队列末尾，标记已遍历过的节点，直到队列中没有节点为止，一般栈用于深度优先搜索，队列用于广度优先搜索。

(3)广度优先算法实现扩展阅读：

深度优先搜索用一个数组存放产生的所有状态。

（1） 把初始状态放入数组中，设为当前状态；

（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；

（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；

（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。

‘肆’ 广度优先搜索有什么难点

广度优先搜索难点在于每一种算法的不同，树的遍历。

扩展知识：

广度优先搜索算法又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。

广度优先搜索算法主要有四个特性：

空间复杂度：由于对空间的大量需求，因此BFS并不适合解非常大的问题，对于类似的问题，应用IDDFS已达节省空间的效果。

时间复杂度：最差情形下，BFS必须查找所有到可能节点的所有路径。

完全性：广度优先搜索算法具有完全性。这意指无论图形的种类如何，只要目标存在，则BFS一定会找到。然而，若目标不存在，且图为无限大，则BFS将不收敛（不会结束）。

最佳解：若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少；但对一般的图来说，BFS并不一定回传最佳解。

‘伍’ 广度优先算法（宽搜）pascal

下面是一段delphi代码：
算法核心代码，为增强算法通用性，将窗体的一个treeview和ADOQuery引用到局部变量中，作为对象引用，不创建，也不释放，相当于别名
procere Tfrm.FmtTree();
var
i,j :integer;
leafList,leafListPlus: TList;
leaf,subNode: TTreeNode;
tv: TTreeView;//引用窗体控件
qry: TADOQuery;//引用窗体控件
begin
//初始化
leafList:=TList.Create;
leafListPlus:=TList.Create;
tv:=tvw1;
tv.Items.Clear;
qry:=qry1;
subNode:=tv.Items.AddChild(nil,'月夜风筝(我)的公司');
leafList.Add(subNode);
//处理
while leafList.Count > 0 do
begin
leafListPlus.Clear;
for i:=0 to leafList.Count-1 do
begin
leaf:=leafList[i];
if leaf.Level = 0 then
qry.SQL.Text:=Format('select code,name,belong from TB where belong = ''%s''',['--'])
else
qry.SQL.Text:=Format('select code,Name,belong from TB where belong = ''%d''',[leaf.StateIndex]);
qry.Open;
for j:= 0 to qry.RecordCount-1 do
begin
subNode:=tv.Items.AddChild(leaf,qry.FieldByName('name').AsString);
subNode.ImageIndex:=subNode.Level;
subNode.StateIndex:=StrToInt(qry.FieldByName('code').AsString);
leafListPlus.Add(subNode);
qry.Next;
end;
end;
leafList.Assign(leafListPlus);
end;
//清理
tv.FullExpand;
leafListPlus.Free;
leafList.Free;
end;

说明：
用TList类型模拟实现了广度优先算法的队列－－先进先出－－实际上，本算法不需要那么严格，只要按批先进先出就行了。leafList用于当前循环，leafListPlus用于下一轮循环，其中保存的都是树节点类型，以方便在treeview上直接插入子节点，就省了查找父结点的算法，节点的编号缓存在节点的StateIndex属性中，编号可转为整数型这是最方便的，如果编号不能保证可转为整数，可以使用data属性，可保万无一失
希望对你有帮助~

‘陆’ 广度优先搜索C语言算法

广度优先搜索算法，是按层遍历各个结点，以求出最短或最优的解，
常用于计算路径的最短距离，和最佳通路。
例如：迷宫的最短路径计算，推箱子的移动最小步数等小游戏，都是按广度搜索来进行的。

这个算法是教程中很经典的，有很多例子和代码。你可以好好研究！

如下是一段迷宫的最佳路径求解算法。
#include <stdio.h>

const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};
int maze[5][5],prev[5][5];
int que[32];
int qn;

void print(int x,int y)
{
if(prev[x][y]!=-2)
{
print(prev[x][y]>>3,prev[x][y]&7);
}
printf("(%d, %d)\n",x,y);
}

int main()
{
int i,j,cx,cy,nx,ny;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&maze[i][j]);
}
}
memset(prev,-1,sizeof(prev));
prev[0][0]=-2;
que[0]=0;
qn=1;
for(i=0;i<qn;i++)
{
cx=que[i]>>3;
cy=que[i]&7;
for(j=0;j<4;j++)
{
nx=cx+dx[j];
ny=cy+dy[j];
if((nx>=0)&&(nx<5)&&(ny>=0)&&(ny<5)&&(maze[nx][ny]==0)&&(prev[nx][ny]==-1))
{
prev[nx][ny]=(cx<<3)|cy;
que[qn++]=(nx<<3)|ny;
if((nx==4)&&(ny==4))
{
print(nx,ny);
return 0;
}
}
}
}
return 0;
}

‘柒’ 常见算法5、广度优先搜索 Breadth-First Search

1、定义

广度优先搜索 （Breadth-First Search）是最简便的图的搜索算法之一，又称 宽度优先搜索 ，这一算法也是很多重要的图算法的原型。广度优先搜索属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

2、应用

广度优先搜索被用于解决 最短路径问题（shortest-path problem） 。

广度优先搜索让你能够找出两样东西之间的最短距离，不过最短距离的含义有很多！使用广度优先搜索可以：

3、图简介

既然广度优先搜索是作用于图的一种算法，这里对图作一个简单的介绍，先不深入了解。

图由 节点 和 边 组成。一个节点可能与多个节点相连，这些节点被称为邻居。

广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形。

例：假如你需要在你的人际关系网中寻找是否有职业为医生的人，图如下：

而使用广度优先搜索工作原理大概如下 ：

1、Python 3 ：

2、php ：

1、《算法图解》 https://www.manning.com/books/grokking-algorithms
2、SplQueue类： https://www.php.net/manual/zh/class.splqueue.php