鄰接圖演算法

Ⅰ 已知圖的鄰接表如下所示,根據演算法,則從頂點0出發按廣度優先遍歷的結點序列是

A。

首先，認識下廣度優先遍歷，相當於樹的層序遍歷，通常藉助隊列(先進先出)實現演算法。題中從0出發，即0入隊，鄰接表訪問順序為3，2，1，則入隊順序也為3，2，1所以答案A。

例如：

深度：FCBDEA或者FCADEB

廣度：FCABDE或者FCBADE

(1)鄰接圖演算法擴展閱讀 ：

從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結點及左、右子樹這三個基本部分組成。因此，在任一給定結點上，可以按某種次序執行三個操作：

（1）訪問結點本身(N)，

（2）遍歷該結點的左子樹(L)，

（3）遍歷該結點的右子樹(R)。

以上三種操作有六種執行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

前三種次序與後三種次序對稱，故只討論先左後右的前三種次序。

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

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

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

Ⅲ 在用鄰接表表示圖時，拓撲排序演算法時間復雜度為多少

O（n + e）。
對於一個具有n個頂點e條弧的有向圖來說，剛開始將入度為0的頂點入棧的時間復雜為O(n)，在之後頂點出棧時，入度減1的操作共執行了e次，所以整個演算法的時間復雜度為O(n + e)。

Ⅳ 用鄰接表表示圖的廣度優先搜索時的存儲結構,通常採用（）結構來實現演算法

B。

廣度優先搜索相當於層次遍歷，深度優先搜索相當於先序優先遍歷，所以答案選擇B。

鄰接表表示的圖的廣度優先搜索一般採用隊列結構來實現演算法：

首先選擇一個起始節點，把它的臨界表中節點加入到隊列中，每次取出隊首元素，然後把該元素的鄰接表中的節點加入到隊列末尾，標記已遍歷過的節點，直到隊列中沒有節點為止，一般棧用於深度優先搜索，隊列用於廣度優先搜索。

(4)鄰接圖演算法擴展閱讀：

深度優先搜索用一個數組存放產生的所有狀態。

（1） 把初始狀態放入數組中，設為當前狀態；

（2） 擴展當前的狀態，產生一個新的狀態放入數組中，同時把新產生的狀態設為當前狀態；

（3） 判斷當前狀態是否和前面的重復，如果重復則回到上一個狀態，產生它的另一狀態；

（4） 判斷當前狀態是否為目標狀態，如果是目標，則找到一個解答，結束演算法。

Ⅳ 在用鄰接表表示圖時,對圖進行深度優先搜索遍歷的演算法的時間復雜度為()

因為當相鄰矩陣的大部分被破壞時，矩陣中的所有元素都需要掃並追蹤到，且元素個數為n＾2，自然演算法為O（n＾2）。

所以鄰接表只存儲邊或弧，如果掃描鄰接表，當然會得到O（n＋e）其中n是頂點的數量，e的邊或弧的數量。

設有n個點，e條邊

鄰接矩陣：矩陣包含n＾2個元素，在演算法中共n個頂點，對每個頂點都要遍歷n次，所以時間復雜度為O（n＾2）。

鄰接表：包含n個頭結點和e個表結點，演算法中對所有結點都要遍歷一次，所以時間復雜度為O（n+e）順便，對於廣度優先演算法的時間復雜度，也是這樣。

(5)鄰接圖演算法擴展閱讀：

鄰接表是圖的最重要的存儲結構之一，描述了圖上的每個點。創建一個容器對於每一個圖的頂點（n頂點n容器）和節點在第i個容器包含所有相鄰頂點的頂點Vi。事實上，我們經常使用的鄰接矩陣是一個鄰接表的邊集不離散化每一個點。

在有向圖中，描述每個點與另一個節點連接的邊(在a點->點B)。

在無向圖中，描述每個點上的所有邊（A點和B點的情況）

鄰接表對應的圖存儲方法稱為邊集表。此方法將所有邊存儲在容器中。

Ⅵ 已知一個有向圖的鄰接表，試編寫一個演算法求每個結點的出度和入度。

因此要在多個鄰接頂點之間約定一種訪問次序。@由於圖中可能存在迴路，在訪問某個頂點之後，可能沿著某條路徑又回到圖的深度優先搜索遍歷演算法p88
聯通的無迴路的無向圖，簡稱樹。樹中的懸掛點又成為樹葉，其他頂點稱為分支點。