演算法/無權圖演算法
頂部，章節: 1，2，3，4，5，6，7，8，9，A 請編輯並從標題中省略“無權”
行/列是源/目標頂點，矩陣是一個具有非負條目的方陣，如果頂點之間沒有邊則為 0，如果從源頂點到目標頂點有 n 條邊則為 n。這對於稠密多重圖來說效率很高。對於無向圖，您可以將矩陣擴充套件為對稱矩陣，或者只將其用作三角矩陣。
一個向量，其條目是鄰接頂點的列表。如果您需要表示一個多重圖，那麼您需要一個字典向量，其中鍵是目標向量，值是邊的重數。這對於稀疏圖來說效率很高。對於無向圖，您可以對邊上的頂點排序，或者將每條邊輸入兩次（在每個頂點輸入一次）。
該列表可能與一級快取配合使用，使用鄰接物件（哪個節點、已訪問、路徑中、路徑權重、來自何處）。
dfs(vertex w)
if w has already been marked visited
return
mark w as visited
for each adjacent vertex v
dfs(v)
非遞迴 DFS 更加困難。它要求每個節點記住最後訪問的子節點，因為它會下降當前子節點。一種實現使用一個索引陣列作為迭代器，所以在訪問一個節點時，節點的編號就是陣列中的索引，該陣列儲存節點子節點的迭代器。然後將第一個迭代器值壓入作業棧。Peek 而不是 pop 用於檢查棧的當前頂部，並且只有當 peeked 節點的迭代器耗盡時才呼叫 pop。
這些技術來自：Yogesh Jakhar
bfs ( x ):
q insert x;
while (q not empty )
y = remove head q
visit y
mark y
for each z adjacent y
q add tail z
可以使用廣度優先搜尋來探索資料庫模式，試圖將其轉換為 XML 模式。這是透過命名根表，然後進行引用廣度優先搜尋來完成的。搜尋在引用端和被引用端都進行，因此如果另一個表引用了正在搜尋的當前節點，那麼該表在 XML 模式中具有 一對多關係，否則是 多對一關係。
在有向圖中，透過在 DFS 遞迴呼叫之前設定第二個標記，並在之後將其關閉，並在 DFS 鄰接遍歷中檢查第二個標記是否在原始標記檢查之前，來檢查圖是否為 *無環*。如果存在第二個標記，則存在迴圈。
- 檢查迴圈，如上一節所示。
- 對無環圖進行 DFS。在對相鄰節點呼叫 DFS 後，透過將結果儲存在堆疊而不是佇列中來反轉後序。
堆疊上的最後一個節點必須來自第一次 DFS 呼叫，移除最後一個節點會暴露第二個節點，該節點只能由最後一個節點到達。使用歸納法證明拓撲順序。
- 強連通分量在內部有迴圈，並且在分量之間必須是無環的（核心有向無環圖）。
- 原始圖的 DFS 反轉後序與反向圖的 DFS 反轉後序之間的區別在於，第一個節點在後者中依賴性最低。因此，所有非強連通節點將首先被反向圖的反轉後序中的 DFS 在原始圖中移除，然後 DFS 將透過標記來移除僅強連通節點，每次迭代反向圖的反轉後序都會標記一個 SCC，只訪問未標記的節點。由於反向圖的反轉後序，從遍歷的 SCC 中發出的每條出邊都會指向一個已經標記的節點。