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

1樓：痴情鐲

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

鄰接表，儲存方法跟樹的孩子連結串列示法相類似，是一種順序分配和鏈式分配相結合的儲存結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向連結串列中。

對於無向圖來說，使用鄰接表進行儲存也會出現資料冗餘，表頭結點a所指連結串列中存在一個指向c的表結點的同時，表頭結點c所指連結串列也會存在一個指向a的表結點。

鄰接表相似類：

圖的鄰接表儲存方法跟樹的孩子連結串列示法相類似，是一種順序分配和鏈式分配相結合的儲存結構。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向連結串列中。如詞條概念圖所示，表結點存放的是鄰接頂點在陣列中的索引。

鄰接表是圖的一種最主要儲存結構,用來描述圖上的每一個點。對圖的每個頂點建立一個容器（n個頂點建立n個容器），第i個容器中的結點包含頂點vi的所有鄰接頂點。實際上我們常用的鄰接矩陣就是一種未離散化每個點的邊集的鄰接表。

2樓：

使用棧來實現演算法。

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

擴充套件材料：

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

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

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

知網**-資料結構中圖的遍歷演算法研究

3樓：昕痕

鄰接表圖的深度優先，思想是以深度因素為優先遍歷，（因此可以檢測是否圖為連通圖），可以想像成你從上往下走迷宮，走不動了就從根再換條路走，演算法實現方式就與這種思想匹配，使用遞迴（棧）來完成遍歷。具體為:

void dfstra(graph t,bool visit［n］)

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

4樓：匿名使用者

因為鄰接

矩陣最壞時需要將矩陣中所有元素掃描完，元素個數是n^2個，自然演算法就是內o(n^2)

鄰接表，只是儲存了邊容或者弧，將鄰接表掃描完就可以了，時間複雜度自然就是o(n+e)了，n是頂點數，e的邊或者弧的數量

具有n個頂點、e條邊的圖採用鄰接表儲存結構，進行深度優先遍歷和廣度優先遍歷運算的時間複雜度均為

5樓：烏石

答案是o（n+e）但是鄰接表裡面不是每個邊被儲存兩次嗎，為什麼不是n+2e呢？

在大o表示法中o（n+2e)通常應表示為o（n+e）

求大神幫做資料結構作業：使用鄰接矩陣或者鄰接表建立一個圖，並對這個圖進行深度優先遍歷和廣度優先遍歷

6樓：匿名使用者

這裡面有你上面

說的**實現，講

內的很容詳細

7樓：淡淡的黯然成傷

我這裡有一個，給你看看，明天給