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