評論(0

廣度優先遍歷

標籤: 暫無標籤

1簡介

廣度優先遍歷是連通圖的一種遍歷策略。因為它的思想是從一個頂點V0開始,輻射狀地優先遍歷其周圍較廣的區域,故得名。

2基本思想

1、從圖中某個頂點V0出發,並訪問此頂點;
2、從V0出發,訪問V0的各個未曾訪問的鄰接點W1,W2,…,Wk;然後,依次從W1,W2,…,Wk出發訪問各自未被訪問的鄰接點;
3、重複步驟2,直到全部頂點都被訪問為止。

3性質

與深度優先遍歷類似,廣度優先遍歷也有許多有用的特性:
1、廣度優先生成樹
在廣度優先遍歷中,如果將每次「前進」(縱深)路過的(將被訪問的)結點和邊都記錄下來,就得到一個子圖,該子圖為以出發點為根的樹,稱為廣度優先生成樹。這種情況與深度優先遍歷類似。
類似地,也可以給廣度優先生成樹結點定義時間戳。
2、最短路徑
顯然,從v0出發廣度優先遍歷圖,將得到v0到它的各個可達到的路徑。我們這裡定義路徑上的邊的數目為路徑長度。與深度優先遍歷不同,廣度優先遍歷得到的v0到各點的路徑是最短路徑(未考慮邊權)。

4演算法

template <int max_size>
void Digraph<max_size> ::
breadth_first(void (*visit)(Vertex &)) const
/* Post: The function *visit has been performed at each vertex of the Digraph in breadth-first order.
Uses: Methods of class Queue. */
{
Queue q;
bool visited [max_size];
Vertex v, w, x;
for (all v in G) visited [v] = false;
for (all v in G)
if (!visited [v]) {
q.append (v);
while (!q.empty ( )){
q.retrieve (w);
if (!visited [w]) {
visited [w] = true; (*visit) (w);
for (all x adjacent to w) q.append (x); }
q.serve ( ); } }
}
廣度優先搜索演算法pascal演算法框架
Program BFS;
初始化,存儲初始狀態(記錄初始結點);
設隊列首指針closed=0;隊列尾指針open:=1;
repeat
首指針closed后移一格,取其所指向的結點;
for r:=1 to max_r do
begin
if子結點符合條件 且 子結點沒有重複擴展 then
begin
尾指針open加1;把新結點存入隊列尾;
記錄相關信息;
if 達到目標 then 輸出且結束;
end;
until closed>=open(隊列空)

5深度比較

廣度優先遍歷與深度優先遍歷的區別在於:廣度優先遍歷是以層為順序,將某一層上的所有節點都搜索到了之後才向下一層搜索;而深度優先遍歷是將某一條枝椏上的所有節點都搜索到了之後,才轉向搜索另一條枝椏上的所有節點。
深度優先遍歷從某個頂點出發,首先訪問這個頂點,然後找出剛訪問這個結點的第一個未被訪問的鄰結點,然後再以此鄰結點為頂點,繼續找它的下一個新的頂點進行訪問,重複此步驟,直到所有結點都被訪問完為止。
廣度優先遍歷從某個頂點出發,首先訪問這個頂點,然後找出這個結點的所有未被訪問的鄰接點,訪問完后再訪問這些結點中第一個鄰接點的所有結點,重複此方法,直到所有結點都被訪問完為止。
可以看到兩種方法最大的區別在於前者從頂點的第一個鄰接點一直訪問下去再訪問頂點的第二個鄰接點;後者從頂點開始訪問該頂點的所有鄰接點再依次向下,一層一層的訪問。

6報告

運行結果
一、輸入圖的頂點數:a,運行結果:非法輸入,請重新輸入。
二、確定第1個頂點與第2個頂點是否有關係時,輸入非0和1,運行結果:程序並不響應。
三、確定從第幾個頂點開始遍歷該圖是,輸入:j,r,ab,-1,0,1,21.
四、運行結果:非法輸入,請重新輸入。
上一篇[最小生成樹]    下一篇 [深度優先遍歷]

相關評論

同義詞:暫無同義詞