宽度优先算法迷宫时间复杂度数组

❶ 深度优先算法 和 宽度优先算法 的优缺点

1、深度优先算法占内存少但速度较慢，广度优先算法占内存多但速度较快，在距离和深度成正比的情况下能较快地求出最优解。
2、深度优先与广度优先的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。
3、这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度优先下一次扩展的是本次扩展出来的子节点中的一个，而广度优先扩展的则是本次扩展的节点的兄弟点。在具体实现上为了提高效率,所以采用了不同的数据结构。

❷ C++设计一个迷宫并走出来

本程序的前提是将迷宫保存在一个二维数组里，可走的地方为0，不可走的地方为1。由于采用回朔算法，不使用递归，所以首先应该建立一个栈来保存路径，路径是用一个一个点来表示的，也就是说栈中保存的是一系列点的列表。
栈节点类型说明：
struct StackNode
{
POINT Point;
struct StackNode *Next, *Prev;//双向链表形式
};

栈结构用一个类（CPointStack）实现，声明如下：
class CPointStack
{
public:
void ClearStack();//清空栈
void InitStack();//初始化栈
bool Pop(POINT &pt);//弹出顶端元素，并给出该点的坐标，返回是否弹出成功
bool Push(POINT pt);//将pt点的信息压入栈，返回是否压入成功
CPointStack();
virtual ~CPointStack();
protected:
StackNode *m_psnTop;//栈顶指针
StackNode m_snBottom;//栈底，不保存点信息
};

以下为成员函数实现，都是一些数据结构的操作，应该没什么好说的：
//构造时初始化栈
CPointStack::CPointStack()
{
InitStack();
}
//析构时清空栈
CPointStack::~CPointStack()
{
ClearStack();
}

//将点压入栈(成功返回true,失败返回false)
bool CPointStack::Push(POINT pt)
{
StackNode* NewNode = new StackNode;
//是否返回true主要看这里申请内存是否成功
if(!NewNode)
return false;

NewNode->Point = pt;
NewNode->Prev = m_psnTop;
NewNode->Next = NULL;
m_psnTop->Next = NewNode;
m_psnTop = NewNode;

return true;
}

//将点弹出栈(成功返回true,栈为空则返回false)
bool CPointStack::Pop(POINT &pt)
{
if(m_psnTop == &m_snBottom)//是否返回true主要看这里栈是否为空
return false;

StackNode *p;

p = m_psnTop;
m_psnTop = m_psnTop->Prev;
pt = p->Point;
delete p;
m_psnTop->Next = NULL;
return true;
}

//初始化栈
void CPointStack::InitStack()
{
m_psnTop = &m_snBottom;
m_snBottom.Next = NULL;
m_snBottom.Prev = NULL;
}

//清空栈
void CPointStack::ClearStack()
{
StackNode *p;

while(m_psnTop != &m_snBottom)
{
p = m_psnTop;
m_psnTop = m_psnTop->Prev;
delete p;
}
}

接下来设计怎样走出这个迷宫，也就是迷宫算法的主体部分。再次用一个类实现。
在设计这个类时，我考虑到以下几点：
1、迷宫入口和出口的坐标
2、保存迷宫的2维数组
3、获得路径的函数
但是实际设计时由于没有考虑太多问题，只是以设计迷宫算法和解决一个具体迷宫为目的，所以没有考虑动态大小的迷宫，而是将迷宫大小定为601×401。而且在设计迷宫算法后没有将路径顺序输出而是直接在原图中标识（在保存迷宫数据的表中设置经过的点为2而将死路点设置为3）。
这样迷宫类（CGoMaze）的声明为：
class CGoMaze
{
public:
void Go();//寻找路径的函数
POINT m_ptIn;//入口坐标
POINT m_ptOut;//出口坐标
BYTE m_btArrMaze[401][601];//保存迷宫的二维表
CGoMaze();
virtual ~CGoMaze();
};

最后让我们来看一下CGoMaze::Go()这个函数：
我们模仿人走迷宫时的思路，设置一个当前点，一个目标点（下一个要走的点）。初始情况下当前点为入口，终止条件为当前点为出口，这样，我们的函数大概结构就出来了。
在从入口到出口的过程中程序对当前点的上、下、左、右四个点依次进行判断，当发现任一个方向是未走过的区域时，就将当前点指向那个点进行尝试，同时将当前点入栈并做标记。而当4个方向都不通或已走过时，则为死路，标记当前点为死路并从栈中弹出上一个点继续进行尝试，这时因为当前点已被标记为死路，则弹出上一个点时就不会重复这条路，达到寻找正确路径的效果。
Go函数的具体实现如下，其实挺简单的^_^：
void CGoMaze::Go()
{
CPointStack psPath;//保存路径的栈
POINT ptCur = m_ptIn, ptNext;//设置当前点为入口

while(ptCur.x != m_ptOut.x || ptCur.y != m_ptOut.y)//判断是否已经走出
{
ptNext = ptCur;//设置目标点为当前点，便于下面偏移
if(m_btArrMaze[ptCur.y - 1][ptCur.x] == 0)
ptNext.y --;//如果上方是空的，则目标点向上偏移
else if(m_btArrMaze[ptCur.y][ptCur.x - 1] == 0)
ptNext.x --;//如果左边是空的，则目标点向左偏移
else if(m_btArrMaze[ptCur.y + 1][ptCur.x] == 0)
ptNext.y ++;//如果下方是空的，则目标点向下偏移
else if(m_btArrMaze[ptCur.y][ptCur.x + 1] == 0)
ptNext.x ++;//如果右边是空的，则目标点向右偏移
else
{//这里是没有路的状态
m_btArrMaze[ptCur.y][ptCur.x] = 3;//标记为死路
psPath.Pop(ptCur);//弹出上一次的点
continue;//继续循环
}
//如果有路的话会执行到这里
m_btArrMaze[ptCur.y][ptCur.x] = 2;//标记当前点为路径上的点
psPath.Push(ptCur);//当前点压入栈中
ptCur = ptNext;//移动当前点
}
}

其实这个部分可以将栈设置为CGoMaze类的成员，然后在Go函数里加上：
psPath.ClearStack();
这样就可以用Timer来演示走迷宫的过程了

❸ 迷宫问题详细的算法或Pascal程序带注释

Dinic算法的思想是为了减少增广次数，建立一个辅助网络L，L与原网络G具有相同的节点数，但边上的容量有所不同，在L上进行增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流。分层的目的是降低寻找增广路的代价。
算法步骤如下：
STEP1：建造原网络G的一个分层网络L。
STEP2：用增广路算法计算L的最大流F，若在L中找不到增广路，算法结束。
SETP3：根据F更新G中的流f，转STEP1。
分层网络的构造算法：
STEP1：标号源节点s，M[s]＝0。
STEP2：调用广度优先遍历算法，执行一步遍历操作，当前遍历的弧e=v1v2，令r＝G.u（e）－G.f（e）。
若r>0，则
（1） 若M[v2]还没有遍历，则M[v2]=M[v1]+1，且将弧e加入到L中，容量L.u（e）＝r。
（2） 若M[v2]已经遍历且M[v2]=M[v1]+1，则将边e加入到L中，容量L.u（e）＝r。
（3） 否则L.u（e）＝0。
否则L.u（e）＝0。
重复本步直至G遍历完。其中的G.u(e)、G.f(e)、L.u(e)分别表示图G中弧e的容量上界和当前流量，图L中弧e的容量上界。

下附程序 （邻接表的程序，希望看得懂）
Program zw_dinicc;
type
o=record
point,next,c:longint;
end;
Var
i,j,k,p,n,m,head,tail,s,t,tot,a1,a2,a3,tot1,a4:longint;
h,l:array[1..55002]of longint;
first:array[1..55002]of longint;
e:array[1..310002] of o;
procere add(a,b,c:longint);
begin
e[tot1].point:=b; e[tot1].next:=first[a]; e[tot1].c:=c; first[a]:=tot1; inc(tot1);
end;

procere init;
var i,x,y,q:longint;
begin
tot1:=2;
readln(n,m);
for i:=m+2 to n+m+1 do
begin
read(a1);
add(i,n+m+2,a1);
add(n+m+2,i,0);
end;
for i:=2 to m+1 do
begin
read(a1,a2,a3);
add(i,1+m+a1,65536000); add(1+m+a1,i,0);
add(i,1+m+a2,65536000); add(1+m+a2,i,0);
add(1,i,a3);add(i,1,0);
inc(j,a3);
end;
n:=2+m+n;

s:=1;
t:=n;
end;
//以上为建边，用的是残量网络
procere bfs;｛构建分层图，从原点开始广搜｝
var
i,j,k,now:longint;
begin
head:=1; tail:=1; l[head]:=s; fillchar(h,sizeof(h),127); h[s]:=0;
while head<= tail do
begin
now:=l[head]; inc(head); k:=first[now];
while k>0 do
begin
if (h[e[k].point]>n) and(e[k].c>0) then｛如果可以流，且该点未被访问｝
begin
h[e[k].point]:=h[now]+1;
inc(tail);
l[tail]:=e[k].point;
end;
k:=e[k].next;
end;
end;
end;

function dfs(now,low:longint):longint;｛根据分层图增广，low表示到now为止最多可增广流量｝
var
i,j,k,tmp:longint;
begin
if now=t then exit(low);
dfs:=0; k:=first[now];
while k>0 do
begin
if (e[k].c>0) and (h[e[k].point]=h[now]+1) then｛如果在分层图中符合限制｝
begin
if e[k].c<low then tmp:=dfs(e[k].point,e[k].c)｛寻找可接受的最大流量｝
else tmp:=dfs(e[k].point,low);
if tmp=0 then h[e[k].point]:=maxlongint shr 1;
dec(low,tmp);｛把可流量减去增广值｝
dec(e[k].c,tmp);
inc(e[k xor 1].c,tmp);
inc(dfs,tmp);
if low=0 then break;｛若无法再增广，退出｝
end;
k:=e[k].next;
end;
end;

Procere main;
begin
bfs;
while h[t]<n do｛如果在分层图中找得到汇点｝
begin
inc(tot,dfs(s,maxlongint));｛根据分层图增广｝
bfs;｛根据新的流量构建分层图｝
end;
end;

Begin
assign(input,'profit.in');reset(input);
assign(output,'profit.out');rewrite(output);
init;
main;
writeln(j-tot);
close(input);close(output);
End.
看在本人手打这么多东西的份上，选我吧

❹ 数据结构中排序和查找各种时间复杂度

数据结构中排序和查找各种时间复杂度
(1)冒泡排序
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
(2)选择排序
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的。…… 例子说明好多了。序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了， 所以选择排序不稳定的排序算法
(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果和插入元素相等，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变。所以插入排序是稳定的。
(4)快速排序
快速排序有两个方向，左边的i下标一直往右走（往后），当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走（往前），当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法。（不稳定发生在中枢元素和a[j]交换的时刻）
(5)归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列。不断合并直到原序列全部排好序。相等时不发生交换。所以，归并排序也是稳定的排序算法。
(6)基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
(7)希尔排序(shell)
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
(8)堆排序
我们知道堆的结构是节点i的孩子为2*i和2*i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序是不稳定的排序算法
一、排序
排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2) O(n2) 稳定 O(1) n小时较好
交换 O(n2) O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
Shell O(nlogn) O(ns) 1<s<2 不稳定???="" o(1)???????="" s是所选分组</s
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好
基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9)，R是基数(个十百)
二、查找
未写……
三 树图
克鲁斯卡尔算法的时间复杂度为O（eloge）
普里姆算法的时间复杂度为O（n2）
迪杰斯特拉算法的时间复杂度为O（n2）
拓扑排序算法的时间复杂度为O（n+e）
关键路径算法的时间复杂度为O（n+e）

❺ 宽度优先搜索算法(pascal)

宽度优先搜索（BFS，BreadthFirstSearch）是一种搜索算法，其主要用来解决最优解问题。原型是图的宽度优先遍历问题，即从源顶点s出发，遍历每一个节点，它的基本思路是：先扩展当前节点所有邻接的节点，然后再从这些顶点出发，遍历所有顶点，即分层处理，将遍历路径表示成树，就是按层次遍历。

宽度优先搜索实现要依赖队列，即先进先出表（FIFO），这样保证了搜索的顺序正确。下面以图的遍历为例，写出标准算法（伪代码）

BFS(G,s)

foreachvertexuexceptsdo//对除源顶点外的所有节点进行初始化

begin

visited[u]:=false;//是否访问过

distance[u]:=infinite;//距源顶点距离

parent[u]:=NIL;//父节点

end;

visited[s]:=true;//对源顶点进行初始化

distance[s]:=0;

parent[s]:=NIL;

ENQUEUE(Q,s);//入队；Q为队列

whilenot(empty(Q))do //队列不空

begin

u:=DEQUEUE(Q);//队首元素出队

foreachvertexVbelongstoAdj[u]do//扩展每个邻接节点

ifvisited[v]=falsethen//如果未访问

begin

visited[v]:=true;//标记已访问

distance[v]:=distance[u]+1;//距离更新

parent[v]:=u;//父节点记录

ENQUEUE(Q,v);//入队

end;

end;

实际运用时要注意在达到结果后就要加一个break退出并输出。为什么宽度优先搜索能解决最优问题呢？因为根据宽搜的策略，被搜索到的顶点被戳上的distance标记就是到源顶点的最短路径的距离，因此可以解决无权图的最短路径问题以及由其抽象而来的最优问题。

题目要求并不一样，有的要求最优解大小，就可以直接输出distance；有的要输出最优解路径、方法，可以用循环将parent层层取出，入栈调整顺序输出，这也算一个技巧。

也许你还看不懂算法，可以找本算法导论好好读读，上面的图示对于理解很有帮助。

PS：敲完之后看了看网络，发现上面的内容完全改成了算法导论，可以去看看。尤其图示，很有帮助的。

❻ C语言迷宫问题，求该算法的时间和空间的复杂度。迷宫的路径已经定义好，求出路的算法。

该算法是不稳定的，其时空复杂度不仅和m,n有关，还和mg[][]的具体数值有关。
最坏情况下：每个点都试探过才走到终点。此时时间复杂度为：(m*n-1)*4，（其中4为4个方向），空间复杂度m*n*2，(其中m*n为存储迷宫图空间，m*n为栈空间);
再好情况下：一次试探过就走到终点。此时时间复杂度为：(min(m,n)-1)，空间复杂度m*n;

所以：
该算法时间复杂度为：[(m*n-1)*4+(min(m,n)-1)]/2，约为2×m×n
空间复杂度为3*m*n/2

❼ 详细介绍广度优先搜索的实现，原理，c++程序

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。

已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。
之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。
为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。
在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根节点，即源顶点s.在扫描已发现顶点u的邻接表的过程中每发现一个白色顶点v，该顶点v及边(u,v)就被添加到树中。在宽度优先树中，我们称结点u 是结点v的先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有--个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果u处于树中从根s到结点v的路径中，那么u称为v的祖先，v是u的后裔。

❽ 深度优先和广度优先 的区别 ，用法。

1、主体区别

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。

2、算法区别

深度优先搜索是每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

广度优先搜索是每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。

3、用法

广度优先属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

深度优先即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

(8)宽度优先算法迷宫时间复杂度数组扩展阅读：

实际应用

BFS在求解最短路径或者最短步数上有很多的应用，应用最多的是在走迷宫上，单独写代码有点泛化，取来自九度1335闯迷宫一例说明，并给出C++/Java的具体实现。

在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走，求最短步数。n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。

int mazeArr[maxn][maxn]; //表示的是01矩阵int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向，int visit[maxn][maxn]; //表示该点是否被访问过，防止回溯，回溯很耗时。核心代码。基本上所有的BFS问题都可以使用类似的代码来解决。

❾ C语言迷宫问题，求该算法的时间和空间的复杂度。迷宫的路径已经定义好，求出路的算法。

时间复杂度：o(nm) (这是时间的上界，最多把所有点都遍历一遍，且边与点的访问是同阶的)
空间复杂度：o(nm) (把这个图存下来就要nm的空间)