用鄰接表存儲時間復雜度

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

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

② 你好，請問用鄰接表存儲無向圖，進行深度優先搜索的時間復雜度為什麼

設有n個點，e條邊
鄰接矩陣：矩陣包含n^2個元素，在演算法中，共n個頂點，對每個頂點都要遍歷n次，所以時間復雜度為O(n^2)
鄰接表：包含n個頭結點和e個表結點，演算法中對所有結點都要遍歷一次，所以時間復雜度為
O（n+e）
順便，對於廣度優先演算法的時間復雜度，也是這樣

③ 在圖採用鄰接表存儲時prim演算法的時間復雜度

鄰接表儲存時,是B.鄰接矩陣儲存就是C了.

④ 圖的鄰接表的時間復雜度問題

其實是O(n + e)，頂點加上邊數
那個O(n*e)的意思是每次插入一條邊，都需要重新查找邊所包含兩個頂點信息對應的下標，正常的演算法沒這么弱智吧，不需要頂點信息即為頂點的下標，用散列等方法可以不用這樣的
用鄰接矩陣構造圖時，若存儲的是一個無向圖，則時間復雜度為O(n^2 + n*e)，其中，對鄰接矩陣的初始化耗費的時間為O(n^2);
對於DFS,BFS遍歷來說，時間復雜度和存儲結構有關：
n表示有n個頂點，e表示有e條邊。
1.若採用鄰接矩陣存儲，
時間復雜度為O(n^2);
2.若採用鄰接鏈表存儲，建立鄰接表或逆鄰接表時，

若輸入的頂點信息即為頂點的編號，則時間復雜度為O(n+e);
若輸入的頂點信息不是頂點的編號，需要通過查找才能得到頂點在圖中的位置，則時間復雜度為O(n*e);

⑤ 採用鄰接表存儲，拓撲排序演算法的時間復雜度為多少

要看使用什麼樣的拓撲排序，最好的方法是輸出DFS的逆序，這樣的演算法復雜度是O(V+L),V是頂點個數，L是邊個數。

⑥ 採用鄰接表存儲，Prim演算法的時間復雜度是多少

設連同網中有n個定點，第一個進行初始化循環語句需要執行n-1次，第二個循環共執行n-1次，內嵌兩個循環，其一是在長度為n的數組中求最小值，需要執行n-1次，其二是條用輔助數組，需要執行n-1次。所以Prim演算法的復雜度是n*n

⑦ n個頂點e條邊的圖G用鄰接表存儲，則求每個頂點入度的時間復雜度為查了好幾個地方的答案，答案大部分

O(n+e)是對的，O(n*n)是用鄰接矩陣存儲時的時間復雜度。
演算法就是遍歷每一條邊，然後把每條邊的終點的入度+1.
在鄰接表中，就是要依次訪問每個頂點，然後在每個頂點中依次訪問每條邊，把這些邊的終點的入度+1。也就是每個頂點和每條邊依次要各訪問一遍，所以時間復雜度是O(n+e)。
在鄰接矩陣中，演算法需要遍歷鄰接矩陣的每一個點，而鄰接矩陣有n*n個點，所以時間復雜度是O(n*n)。
有什麼不懂的可以追問。

⑧ 設圖 G 採用鄰接表存儲，則拓撲排序演算法的時間復雜度為（）

如果是鄰接表存儲，拓撲排序演算法的時間復雜度應該是O(n + e)，n是頂點個數，e是弧的數量

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

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

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

設有n個點，e條邊

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

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

(9)用鄰接表存儲時間復雜度擴展閱讀：

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

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

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

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