給定一個加權有向無環圖和一個源頂點。現在，我們必須找到從起始節點到圖中所有其他頂點的最短距離。為了檢測較短的距離，我們可以使用其他演算法，例如 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 ... 閱讀更多

Fleury 演算法用於從給定圖中顯示尤拉路徑或歐拉回路。在這個演算法中，從一條邊開始，它試圖透過移除之前的頂點來移動其他相鄰頂點。使用這種技巧，圖在每個步驟中都變得更簡單，以便找到尤拉路徑或迴路。為了獲得路徑或迴路，我們必須檢查一些規則-圖必須是尤拉圖。當有兩條邊時，一條是橋，另一條是非橋，我們必須首先選擇非橋。起始頂點的選擇也很棘手，我們不能使用任何頂點作為... 閱讀更多

尤拉路徑是一條路徑，透過它我們可以精確地訪問每條邊一次。我們可以多次使用相同的頂點。歐拉回路是一種特殊的尤拉路徑。當尤拉路徑的起始頂點也與該路徑的結束頂點連線時，則稱為歐拉回路。為了檢測路徑和迴路，我們必須遵循以下條件-圖必須是連通的。當恰好有兩個頂點具有奇數度時，它是一條尤拉路徑。現在，當無向圖的任何頂點都沒有奇數度時，它就是一個... 閱讀更多

尤拉路徑是一條路徑，透過它我們可以精確地訪問每條邊一次。我們可以多次使用相同的頂點。歐拉回路是一種特殊的尤拉路徑。當尤拉路徑的起始頂點也與該路徑的結束頂點連線時，則稱為歐拉回路。要檢查圖是否是尤拉圖，我們必須檢查兩個條件-圖必須是連通的。每個頂點的入度和出度必須相同。輸入和輸出輸入：圖的鄰接矩陣。0 1 0 0 0 ... 閱讀更多

使用深度優先搜尋 (DFS) 遍歷演算法，我們可以檢測有向圖中的環。如果任何節點中存在任何自環，則將其視為一個環，否則，當子節點有另一條邊連線其父節點時，它也將是一個環。對於不連通圖，可能存在不同的樹，我們可以稱它們為森林。現在我們必須檢測森林所有樹的環。在這種方法中，我們將使用不同的集合來分配節點以執行 DFS 遍歷。有三個不同的集合：白色、灰色和黑色。... 閱讀更多

為了檢測無向圖中是否存在任何環，我們將對給定圖使用 DFS 遍歷。對於每個已訪問的頂點 v，當我們找到任何相鄰頂點 u 時，如果 u 已經被訪問，並且 u 不是頂點 v 的父節點，則檢測到一個環。我們將假設任何一對頂點都沒有平行邊。輸入和輸出：鄰接矩陣 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 ... 閱讀更多

深度優先搜尋 (DFS) 是一種圖遍歷演算法。該演算法從一個起始頂點開始，當找到一個相鄰頂點時，它會首先移動到該相鄰頂點，並嘗試以相同的方式遍歷。它會盡可能深入地遍歷整個深度，之後回溯到之前的頂點以查詢新的路徑。要迭代地實現 DFS，我們需要使用棧資料結構。如果要遞迴地實現它，則不需要外部棧，可以使用遞迴呼叫的內部棧來實現。輸入和……閱讀更多