廣度遍歷演算法

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

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

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

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

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

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

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

② 試分別畫出自頂點1出發進行遍歷所得的深度優先生成樹和廣度優先生成樹。

從1開始，1連接7,7連接3，3連接4,4連接5,5連接6,6連接2（1已經連過了）（2連接了3,7，但是3和7都已經連過，所以回到上一級6,6的連接是1,2都已經連過，所以再回到上一級5）5連接10 。

（10連接1,6都已經連過了，所以回到上一級5，但是5的所有連接點都連過了，所以回到上一級4）4連接9,（9連接5,10都已經連過了，所以回到上一級4,4也已經練完了，所以再回到上一級3）3連接8，至此連完。

廣度遍歷：從1開始，連接7和9，下一個是7，連接3和10 ，下一個是9，連接5，下一個是3，連接4和8，下一個是10 連接6，下一個是5，沒有什麼連接的，下一個是4，沒有什麼連接的，下一個是8，沒有什麼連接的，下一個是6，連接2，至此連完。

(2)廣度遍歷演算法擴展閱讀：

通用定義：

若從圖的某頂點出發，可以系統地訪問到圖中所有頂點，則遍歷時經過的邊和圖的所有頂點所構成的子圖，稱作該圖的生成樹。

（1）若G是強連通的有向圖，則從其中任一頂點v出發，都可以訪問遍G中的所有頂點，從而得到以v為根的生成樹。

（2）若G是有根的有向圖，設根為v，則從根v出發可以完成對G的遍歷，得到G的以v為根的生成樹。

（3）若G是非連通的無向圖，則要若干次從外部調用DFS(或BFS)演算法，才能完成對G的遍歷。每一次外部調用，只能訪問到G的一個連通分量的頂點集，這些頂點和遍歷時所經過的邊構成了該連通分量的一棵DFS(或BPS)生成樹。

G的各個連通分量的DFS(或BFS)生成樹組成了G的DFS(或BFS)生成森林。

（4）若G是非強連通的有向圖，且源點又不是有向圖的根，則遍歷時一般也只能得到該有向圖的生成森林。