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

給定一個圖；我們必須檢查給定的圖是否為星形圖。透過遍歷圖，我們必須找到度數為 1 的頂點數，以及度數為 n-1 的頂點數。（這裡 n 是給定圖中的頂點數）。當度數為 1 的頂點數為 n-1 且度數為 (n-1) 的頂點數為 1 時，則它是一個星形圖。輸入和輸出輸入：鄰接矩陣：0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 輸出： ... 閱讀更多

傳遞閉包是圖中從頂點 u 到達頂點 v 的可達性矩陣。給定一個圖，我們必須找到一個從另一個頂點 u 可達的頂點 v，對於所有頂點對 (u, v)。最終矩陣是布林型別。當頂點 u 到頂點 v 的值為 1 時，表示從 u 到 v 至少存在一條路徑。輸入和輸出輸入：1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 輸出：傳遞閉包矩陣 1 1 1 ... 閱讀更多

Ford-Fulkerson 演算法用於檢測給定圖中從起始頂點到匯點頂點的最大流量。在此圖中，每條邊都有容量。提供兩個名為源和匯的頂點。源頂點具有所有向外邊，沒有向內邊，而匯點將具有所有向內邊，沒有向外邊。有一些約束條件：邊的流量不超過該圖的給定容量。除了源和匯之外，每條邊的流入流量和流出流量也將相等。輸入和輸出輸入：鄰接矩陣：0 10 0 10 0 0 0 0 4 ... 閱讀更多

有向無環圖的拓撲排序是頂點的線性排序。對於有向圖的每條邊 U-V，頂點 u 將在排序中出現在頂點 v 之前。眾所周知，源頂點將出現在目標頂點之後，因此我們需要使用一個棧來儲存先前的元素。完成所有節點後，我們可以簡單地從棧中顯示它們。輸入和輸出輸入：0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 ... 閱讀更多

Tarjan 演算法用於查詢有向圖的強連通分量。它只需要一次 DFS 遍歷即可實現該演算法。使用 DFS 遍歷，我們可以找到森林的 DFS 樹。從 DFS 樹中，可以找到強連通分量。當找到此類子樹的根時，我們可以顯示整個子樹。該子樹是一個強連通分量。輸入和輸出輸入：圖的鄰接矩陣。0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 輸出：給定圖中的強連通分量如下 ... 閱讀更多

我們瞭解著名的蛇梯遊戲。在這個遊戲中，棋盤上有一些房間，帶有房間編號。一些房間透過梯子或蛇連線。當我們得到梯子時，我們可以爬到一些房間以接近目的地，而無需依次移動。類似地，當我們得到一些蛇時，它會將我們送到一個較低的房間，以從該房間重新開始旅程。在這個問題中，我們必須找到到達起點到目的地的最小骰子投擲次數。輸入和輸出輸入：起始和 ... 閱讀更多

在一個有向圖中，當一個元件中每對頂點之間都存在一條路徑時，稱為強連通。為了解決此演算法，首先，使用 DFS 演算法獲取每個頂點的完成時間，現在找到轉置圖的完成時間，然後按拓撲排序對頂點進行降序排序。輸入和輸出輸入：圖的鄰接矩陣。0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 輸出：以下是在給定圖中的強連通分量 ... 閱讀更多

提供了一個有向圖，其中每對頂點之間都有權重，並且還提供了兩個頂點 u 和 v。我們的任務是找到從頂點 u 到頂點 v 的最短距離，且恰好有 k 條邊。為了解決這個問題，我們將從頂點 u 開始並轉到所有相鄰頂點，並使用 k 值為 k - 1 對相鄰頂點進行遞迴。輸入和輸出輸入：圖的成本矩陣。0 10 3 2 ∞ 0 ∞ 7 ∞ ∞ 0 6 ∞ ∞ ∞ 0 輸出：最短路徑的權重 ... 閱讀更多

二分圖匹配是指從圖中選擇一組邊，使得這組邊中的任意兩條邊都不共享端點。最大匹配是指匹配邊數最多的匹配。當找到最大匹配後，我們就無法再新增任何邊。如果向最大匹配圖中新增一條邊，它將不再是匹配。對於二分圖，可能存在多個最大匹配。輸入和輸出輸入：鄰接矩陣。0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 ... 閱讀更多