寬度優先演算法迷宮時間復雜度數組

❶ 深度優先演算法 和 寬度優先演算法 的優缺點

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的空間)