單源最短路徑演算法（對於任意權重正或負）也稱為 Bellman-Ford 演算法，用於查詢從源頂點到任何其他頂點的最小距離。該演算法與 Dijkstra 演算法的主要區別在於，在 Dijkstra 演算法中，我們無法處理負權重，但在這裡我們可以輕鬆地處理它。Bellman-Ford 演算法以自底向上的方式查詢距離。首先，它找到路徑中只有一條邊的那些距離。之後增加路徑長度以找到所有可能的解決方案。輸入 - 圖的成本矩陣：0 6 ∞ 7 ∞ ∞ ... 閱讀更多

單源最短路徑演算法（對於非負權重）也稱為 Dijkstra 演算法。給定一個圖 G(V, E) 及其鄰接矩陣表示，並提供一個源頂點。Dijkstra 演算法用於查詢從源頂點到圖 G 的任何其他頂點的最小最短路徑。從起始節點到任何其他節點，找到最小的距離。在此問題中，圖使用鄰接矩陣表示。（成本矩陣和鄰接矩陣為此目的類似）。輸入 - 鄰接矩陣 - 0 3 6 ∞ ∞ ∞ ∞ 3 0 2 1 ∞ ∞ ... 閱讀更多

給定一個連通圖 G(V, E)，並且給出了每條邊的權重或成本。Prim 演算法將從圖 G 中找到最小生成樹。它是一種增長樹方法。該演算法需要一個種子值來啟動樹。種子頂點被擴充套件以形成整個樹。問題將使用兩個集合來解決。一個集合儲存已選擇的節點，另一個集合儲存尚未考慮的項。從種子頂點開始，它根據最小邊成本獲取相鄰頂點，因此它透過獲取... 閱讀更多

給定一個連通圖 G(V, E)，並且給出了每條邊的權重或成本。Kruskal 演算法將使用圖和成本找到最小生成樹。它是一種合併樹方法。最初存在不同的樹，該演算法將透過獲取成本最小的那些邊來合併它們，並形成一棵單一樹。在此問題中，列出了所有邊，並根據其成本進行排序。從列表中，取出成本最小的邊並新增到樹中，並且每次都會檢查邊是否形成迴圈，... 閱讀更多

廣度優先搜尋 (BFS) 遍歷是一種演算法，用於訪問給定圖的所有節點。在此遍歷演算法中，選擇一個節點，然後逐個訪問所有相鄰節點。完成所有相鄰頂點後，它將進一步移動以檢查另一個頂點並再次檢查其相鄰頂點。要實現此演算法，我們需要使用佇列資料結構。所有相鄰頂點都新增到佇列中，當所有相鄰頂點完成後，從佇列中刪除一個項並開始遍歷該... 閱讀更多

深度優先搜尋 (DFS) 是一種圖遍歷演算法。在此演算法中，給定一個起始頂點，並且當找到一個相鄰頂點時，它首先移動到該相鄰頂點並嘗試以相同的方式遍歷。它儘可能地遍歷整個深度，之後它回溯以到達以前的頂點以找到新的路徑。要以迭代方式實現 DFS，我們需要使用堆疊資料結構。如果我們想遞迴地執行它，則不需要外部堆疊，它可以使用內部堆疊進行遞迴呼叫。輸入：鄰接... 閱讀更多

圖是一種非線性資料結構。它使用節點表示資料，並使用邊表示它們之間的關係。圖 G 有兩個部分。頂點和邊。頂點用集合 V 表示，邊用集合 E 表示。因此圖表示法為 G(V, E)。讓我們看一個例子來了解一下。在此圖中，有五個頂點和五條邊。這些邊是有向的。例如，如果我們選擇連線頂點 B 和 D 的邊，則源頂點為 B，目標頂點為 D。因此我們可以從 B 移動到 D，但不能從... 閱讀更多

均攤分析此分析用於偶爾的操作非常慢，但大多數執行非常頻繁的操作都更快。在資料結構中，我們需要對雜湊表、不相交集等進行均攤分析。在雜湊表中，大多數情況下搜尋時間複雜度為 O(1)，但有時它執行 O(n) 操作。當我們想要在雜湊表中搜索或插入元素時，在大多數情況下，它是花費常數時間的任務，但是當發生衝突時，它需要 O(n) 次操作來解決衝突。聚合方法聚合方法用於... 閱讀更多

小o記號除了大O、大Ω和大θ記號之外，還存在一些其他記號。小o記號就是其中之一。小o記號用於描述一個不能緊密的界限。換句話說，f(n) 的鬆散上界。設 f(n) 和 g(n) 是對映正實數的函式。我們可以說函式 f(n) 為 o(g(n))，如果對於任何實正常數 c，存在一個整數常數 n0 ≤ 1 使得 f(n) > 0。小o記號的數學關係使用數學關係，我們可以說 f(n) = o(g(n)) 意味著，示例... 閱讀更多

漸進記號漸進記號用於表示演算法在漸進分析中的複雜度。這些記號是表示複雜度的數學工具。三種常用的記號。大Ω記號大Ω (Ω) 記號給出了函式 f(n) 在常數因子內的下界。我們寫 f(n) = Ω(g(n))，如果存在正常數 n0 和 c 使得，在 n0 的右側，f(n) 始終位於或高於 c*g(n)。Ω(g(n)) = { f(n) : 存在正常數 c 和 n0 使得 0 ≤ c g(n) ≤ f(n)，對於所有 n ≤ n0}大θ... 閱讀更多