有向無環圖的拓撲排序是指頂點的線性排序。對於有向圖的每條邊 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 -∞ -∞ ... 閱讀更多

圖著色問題是圖示記的一個特例。在這個問題中，每個節點都用一些顏色著色。但是著色有一些約束。我們不能對任何相鄰的頂點使用相同的顏色。為了解決這個問題，我們需要使用貪婪演算法，但它不能保證使用最少的顏色。輸入和輸出輸入：圖的鄰接矩陣。0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 輸出：節點：0，分配的顏色：0 節點：1，分配的顏色：0 ... 閱讀更多