優先遍歷演算法

㈠ 廣度優先遍歷是什麼

1.廣度優先遍歷的思想廣度優先遍歷類似樹的按層次遍歷。設初始狀態時圖中的所有頂點未被訪問，則演算法思想為：首先訪問圖中某指定的起始頂點v，並將其標記為已訪問過，然後由v出發依次訪問v的各個未被訪問的鄰接點v1，v2，…，vk；並將其均標識為已訪問過，再分別從v1，v2，…，vk出發依次訪問它們未被訪問的鄰接點，並使「先被訪問頂點的鄰接點」先於「後被訪問頂點的鄰接點」被訪問。直至圖中所有與頂點v路徑相通的頂點都被訪問到。

若G是連通圖，則遍歷完成；否則，在圖G中另選一個尚未訪問的頂點作為新源點繼續上述搜索過程，直至圖G中所有頂點均被訪問為止。

2.廣度優先遍歷示例例如，對圖7－18（a）所示的圖G，假設指定從頂點v1開始進行廣度優先遍歷，首先訪問v1，因與v1相鄰並且未被訪問過的頂點有v2和v6，則訪問v2和v6，然後訪問與v2相鄰並未訪問的鄰接點v2，v7，再訪問與v6相鄰並且未被訪問過的鄰接點v5，按這樣的次序依次訪問與v2相鄰並且未被訪問過的鄰接點v4，v8，與v7相鄰並且未被訪問過的鄰接點v9，此時，與v5，v4，v8，v9相鄰並且未被訪問過的鄰接點沒有了，即圖G中的所有頂點訪問完，其遍歷序列為：v1－＞v2－＞v6－＞v2－＞v7－＞v5－＞v4－＞v8－＞v9。這種順序不是唯一的，如果從v1出發後，相鄰的多個頂點優先選擇序號大的頂點訪問，其遍歷序列為：v1－＞v6－＞v2－＞v5－＞v7－＞v2－＞v4－＞v9－＞v8。同理，圖7－18（b）是假設從v1開始，相鄰的多個頂點優先選擇序號小的頂點訪問，其遍歷序列為：v1－＞v2－＞v2－＞v4－＞v5－＞v6－＞v7－＞v8；相鄰的多個頂點優先選擇序號大的頂點訪問，其遍歷序列為：v1－＞v2－＞v2－＞v7－＞v6－＞v5－＞v4－＞v8。圖7－18（c）假設從a開始，相鄰的多個頂點優先選擇ASCII碼小的頂點訪問，其遍歷序列為：a－＞b－＞d－＞e－＞f－＞c－＞g；相鄰的多個頂點優先選擇ASCII碼大的頂點訪問，其遍歷序列為：a－＞f－＞e－＞d－＞b－＞g－＞c。

2.廣度優先遍歷的演算法在廣度優先遍歷中，要求先被訪問的頂點其鄰接點也被優先訪問，因此，必須對每個頂點的訪問順序進行記錄，以便後面按此順序訪問各頂點的鄰接點。應利用一個隊列結構記錄頂點的訪問順序，將訪問的每個頂點入隊，然後再依次出隊。

在廣度優先遍歷過程中，為了避免重復訪問某個頂點，也需要創建一個一維數組visited［n］（n是圖中頂點的數目），用來記錄每個頂點是否已被訪問過。

㈡ 什麼叫遍歷演算法(最好有例子)

遍歷演算法：所謂遍歷(Traversal)，是指沿著某條搜索路線，依次對樹中每個結點均做一次且僅做一次訪問。訪問結點所做的操作依賴於具體的應用問題。遍歷是二叉樹上最重要的運算之一，是二叉樹上進行其它運算之基礎。當然遍歷的概念也適合於多元素集合的情況，如數組。

遍歷演算法概念延伸：

圖遍歷：圖遍歷又稱圖的遍歷，屬於數據結構中的內容。指的是從圖中的任一頂點出發，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎之上。

舉例：

遍歷二叉樹搜索路線：

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：⑴訪問結點本身（N），⑵遍歷該結點的左子樹（L），⑶遍歷該結點的右子樹（R）。以上三種操作有六種執行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三種次序與後三種次序對稱。

遍歷二叉樹的執行蹤跡三種遞歸遍歷演算法的搜索路線相同（如下圖虛線所示）。具體線路為：從根結點出發，逆時針沿著二叉樹外緣移動，對每個結點均途徑三次，最後回到根結點。

㈢ 深度優先遍歷演算法的問題

你好，c的話是a e b... ,深度優先的話，e後面還可以訪問d，d可以訪問f，f可以訪問c。
圖的深度優先遍歷類似於樹的前序遍歷。採用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優先搜索(Depth-First Search)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。

㈣ 先序遍歷和後序遍歷是什麼

1、先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的遍歷結果是：ABDECF

（1）後序遍歷左子樹

（2）後序遍歷右子樹

（3）訪問根結點

如右圖所示二叉樹

後序遍歷結果：DEBFCA

已知前序遍歷和中序遍歷，就能確定後序遍歷。

(4)優先遍歷演算法擴展閱讀：

圖的遍歷演算法主要有兩種，

一種是按照深度優先的順序展開遍歷的演算法，也就是深度優先遍歷；

另一種是按照寬度優先的順序展開遍歷的演算法，也就是寬度優先遍歷。寬度優先遍歷是沿著圖的深度遍歷圖的所有節點，每次遍歷都會沿著當前節點的鄰接點遍歷，直到所有點全部遍歷完成。

如果當前節點的所有鄰接點都遍歷過了，則回溯到上一個節點，重復這一過程一直到已訪問從源節點可達的所有節點為止。

如果還存在沒有被訪問的節點，則選擇其中一個節點作為源節點並重復以上過程，直到所有節點都被訪問為止。

利用圖的深度優先搜索可以獲得很多額外的信息，也可以解決很多圖論的問題。寬度優先遍歷又名廣度優先遍歷。通過沿著圖的寬度遍歷圖的節點，如果所有節點均被訪問，演算法隨即終止。寬度優先遍歷的實現一般需要一個隊列來輔助完成。

寬度優先遍歷和深度優先遍歷一樣也是一種盲目的遍歷方法。也就是說，寬度遍歷演算法並不使用經驗法則演算法， 並不考慮結果的可能地址，只是徹底地遍歷整張圖，直到找到結果為止。圖的遍歷問題分為四類：

1、遍歷完所有的邊而不能有重復，即所謂「歐拉路徑問題」（又名一筆畫問題）；

2、遍歷完所有的頂點而沒有重復，即所謂「哈密頓路徑問題」。

3、遍歷完所有的邊而可以有重復，即所謂「中國郵遞員問題」；

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(隊列空)

㈥ 設計一個基於深度優先遍歷的演算法，判斷一個給定的有向圖是否包含迴路。

你好，關於DFS判斷有向圖是否存在迴路的問題，我本人編寫的考研資料中有相關的原創總結，希望對你有幫助，轉載還請註明原創出處：《大連理工大學軟體學院887專業課（2021版）》。如有問題可以加我QQ601964408交流。
法一：利用遞歸方式，在DFS對圖進行遍歷時，將遍歷過的頂點放入棧中，如果新遍歷的頂點已經存在於遞歸棧中，則說明存在一個反向邊，即存在一個環。此時棧中結點剛好是環路中的所有結點！
注意該方法沒辦法用DFS的非遞歸方法實現，因為非遞歸方法中，利用出棧的結點獲取下一個鄰接點入棧，和遞歸方式不同的地方在於，即使圖中有環，非遞歸方法中的棧也無法存儲環上的結點。（DFS的非遞歸詳見本小結後續的代碼總結部分）
代碼實現如下：
void HasCycle ( Graph G ) {
bool visited [MAX_VERTEX_NUM] ; //訪問標記數組
bool recursionStack [MAX_VERTEX_NUM] ; //標記該點是否在棧中
for ( i=0 ; i<G.vexnum ; i++) {
//mark all the vertices as not visited and not part of recursion stack
//標記所有結點均未訪問以及不在棧中
visited [i] = FALSE ;
recursionStack [i] = FALSE ;
}
//call the recursive helper function to detect cycle in different DFS trees
//調用輔助遞歸函數以檢測不同DFS樹種的環路
for ( int i =0 ; i < G.vexnum ; i++ ) //每次檢測一個連通圖
if ( CheckCyclic ( G , i , VISITED , recursionStack ) ) ;
return true ; //存在迴路
return false ; //不存在迴路
}

bool CheckCyclic ( Graph G , int v , bool [ ] visited , bool [ ] recursionStack ) {
if ( visited [v] == FALSE) {
//mark the current nodes as visited and part of recursion stack
//將當前結點的標記數組和遞歸棧標記，置為已訪問
visited [v] = TRUE ;
recursionStack [v] = TRUE ;

//recursion for all the vertices adjacent to this vertex
//遞歸該頂點附近的所有頂點
for ( Edge e = G.FirstEdge(v) ; G.IsEdge(e) ; e=G.NextEdge(e) ) {
//判斷下一結點未被訪問，進入遞歸函數判斷是否有環
if ( visited [G.ToVertex(e) ] == FALSE &&
CheckCyclic ( G , G.ToVertex(e) , visited , recursionStack) )
return TRUE ;
//當下一結點已經訪問過，並且已經在棧中，判斷有環
else if ( recusionStack (G.ToVertex(e) ) == TRUE )
return TRUE ;
}//end_for
}//end_if

//remove the vertex from recursion stack
//從遞歸棧種移除該結點
recursionStack [v] = FALSE ;
return false ; //判斷無環
}
--------------------------------------------------------------------------------------------------
法二：本方法與法一非常相似，方法一中存在三種情況，還未入棧時表示未被訪問過的點；在棧中時表示已經被訪問過但是還沒有遞歸結束；從棧中出棧時表示遞歸結束，即後代也全部被訪問過了。上述三種情況分別用 -1，0，1三種狀態來標記點。
針對上述思路，假設正在處理點v，那麼v的狀態是0，其餘正在處理的結點的狀態也是0，如果從狀態0的結點遍歷到狀態為0的結點，那麼就存在環。此時所有狀態為0的結點構成了一個環！發現存在環時遍歷輸出state數組即可，不過該方法輸出時不是按照環路的順序輸出；如果需要順序輸出環路，可增加一個cycle數組，每次記錄環路的起點位置i。用cycle[i]記錄結點i的下一個結點編號。利用遞歸的方式輸出cycle數組即可得到迴路順序。
代碼實現：
bool Found = FALSE ; //標記是否發現環路
void HasCycle ( Graph G ) {
int state [MAX_VERTEX_NUM] ; //結點狀態標識數組
for ( i=0 ; i<G.vexnum ; i++) {
state [i] = -1 ;
}
for ( int i =0 ; i < G.vexnum ; i++ ) { //每次檢測一個連通圖
CheckCyclic ( G , i , state )；
if ( Found == TRUE ) ; //存在迴路
return true ;
}
return false ; //不存在迴路
}

void CheckCyclic ( Graph G , int v , int [ ] state ) {
if ( state [v] == -1) { //如果未訪問過
state [v] = 0 ; //改變該點的狀態
for ( Edge e = G.FirstEdge(v) ; G.IsEdge(e) ; e=G.NextEdge(e) ) {
if ( state [ G.ToVertex(e) ] == -1 )
CheckCyclic ( G , G.ToVertex(e) , state )
else if ( state [ G.ToVertex(e) ] == 0 ) //該圖有環
Found = TRUE ;
}//end_for
}//end_if

state [v] = 1 ; //該點遞歸結束，即後代也訪問完
}

㈦ 採用鄰接表存儲的圖的深度優先遍歷演算法類似於二叉樹的先序遍歷，為什麼是先序呢

這是因為圖的深度優先遍歷演算法先訪問所在結點，再訪問它的鄰接點。與二叉樹的先序遍歷先訪問子樹的根結點，再訪問它的孩子結點（鄰接點）類似。圖的廣度優先遍歷演算法類似於二叉樹的按層次遍歷。
先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。
首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。
例如，下圖所示二叉樹的遍歷結果是：ABDECF。

(7)優先遍歷演算法擴展閱讀：
遍歷種類：
一、NLR：前序遍歷(Preorder
Traversal
亦稱（先序遍歷）），訪問根結點的操作發生在遍歷其左右子樹之前。
二、LNR：中序遍歷(Inorder
Traversal)，訪問根結點的操作發生在遍歷其左右子樹之中（間）。
三、LRN：後序遍歷(Postorder
Traversal)，訪問根結點的操作發生在遍歷其左右子樹之後。
注意：
由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left
subtree）和R(Right
subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為
先根遍歷、中根遍歷和後根遍歷。
參考資料來源：網路-先序遍歷

㈧ 用鄰接表表示圖進行深度優先遍歷時，通常採用（）來實現演算法

使用棧來實現演算法。

用鄰接表表示圖進行深度優先遍歷時，通常採用棧來實現演算法，廣度遍歷使用隊列。

擴展材料：

深度優先遍歷：類似與樹的前序遍歷。從圖中的某個頂點v出發，訪問此頂點，然後從v的未被訪問到的鄰接點進行遍歷，直到圖中所有和v有路徑相通的頂點都被訪問到

註：優先訪問外層節點，訪問到無新頂點時，會進行回退，訪問未被訪問過的分支頂點。

廣度優先遍歷：類似於樹的層序遍歷。從圖中的某個頂點w出發，讓頂點w入隊，然後頂點w再出隊，並讓所有和頂點w相連的頂點入隊，然後再出隊一個頂點t，並讓所有和t相連但未被訪問過的頂點入隊……由此循環，指定圖中所有元素都出隊。

參考資料來源：

知網論文-數據結構中圖的遍歷演算法研究

㈨ 無向有權的圖的深度、廣度優先遍歷怎麼做的啊，他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1） 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧，廣度優先遍歷的非遞歸的通用做法是採用隊列。

2） 深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下：

先序遍歷：對任一子樹，先訪問根，然後遍歷其左子樹，最後遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然後訪問根，最後遍歷其右子樹。
後序遍歷：對任一子樹，先遍歷其左子樹，然後遍歷其右子樹，最後訪問根。
廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

3）深度優先搜素演算法：不全部保留結點，佔用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。

廣度優先搜索演算法：保留全部結點，佔用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。

㈩ 深度優先遍歷樹的演算法怎麼編程

程序的頭已經有了只要一個深度優先遍歷的演算法的程序。程序開始如下： #include "stdafx.h" #include "iostream.h" typedf int adjmatrix; const int max value=32767; conts int maxlength=30; int visited[10]; adjmatrix ga[10][10]; void create(int n,int e){int i,j,k,w; for(i=0;i<n;i++) for(j=0;j<n;j++){if(i==j)ga[i][j]=0; else ga[i][j]=max value;}cout<<"請輸入"<<e<<"條邊的權值："<<endl; for(k=1;k<=e;k++){cout<<"第"<<k<<"條邊的起始頂點,結束頂點及權值,如1 2 8:"; cin>>i>>j>>w; ga[i][j]=w;}}void dfs(int i,int n) //深度優先遍歷演算法{//請完成函數的編程}void main(){int i,j,n,e; cout<<"請輸入頂點個數:";cin>>n;cout<<"請輸入邊數:";cin>>e;create(n,e); cout<<endl<<"深度優先遍歷表:"<<endl; for(i=0;i<n;i++)visited[i]=0; if(!visited[i])dfs(i,n);}只要在請完成函數的編程這部分把程序編完就可以了。