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

給定一個加權有向無環圖。還提供了另一個源頂點。現在我們必須找到從起始節點到圖中所有其他頂點的最短距離。為了檢測較小的距離，我們可以使用另一種演算法，例如 Bellman-Ford 用於具有負權重的圖，對於正權重，Dijkstra 演算法也有幫助。這裡對於有向無環圖，我們將使用拓撲排序技術來降低複雜度。輸入和輸出輸入：圖的成本矩陣。 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ ... 閱讀更多

如果一個圖的頂點可以分成兩個獨立的集合，使得圖中的每條邊要麼從第一個集合開始並在第二個集合結束，要麼從第二個集合開始，連線到第一個集合，換句話說，我們可以說在同一個集合中找不到任何邊，則稱該圖是二分圖。可以使用頂點著色來檢查二分圖。當一個頂點在同一個集合中時，它具有相同的顏色，對於另一個集合，顏色將發生變化。輸入和輸出輸入：... 閱讀更多

給定一個加權有向無環圖。還提供了另一個源頂點。現在我們必須找到從起始節點到圖中所有其他頂點的最長距離。我們需要對節點進行拓撲排序，並將拓撲排序後的結果儲存到堆疊中。之後反覆從堆疊中彈出並嘗試為每個頂點找到最長距離。輸入和輸出輸入：圖的成本矩陣。 0 5 3 -∞ -∞ -∞ -∞ 0 2 6 -∞ -∞ -∞ -∞ 0 7 4 2 -∞ -∞ ... 閱讀更多