topological-sort

-3熱度

1回答

我試圖設計一種算法來確定有向圖是否具有唯一的拓撲排序。任何人都知道如何爲此編寫僞代碼？

3熱度

3回答

以下問題在塞奇威克和韋恩本書算法被發現在Java中： 4.2.19拓撲排序和BFS。解釋爲什麼以下算法不一定會產生拓撲順序：運行BFS，並通過增加到它們各自源的距離來標記頂點。我試圖證明它找到一個反例。但是，每次嘗試，我都會得到一個拓撲順序。我的意思是，我不明白爲什麼這不起作用：如果一個頂點的源頭出現在它之前，爲什麼我們沒有一個拓撲順序？我認爲要證明這一點，我們需要找到一個其來源之前的頂點，

0熱度

1回答

爲什麼拓撲排序找到最短路徑O（V + E）

我很困惑爲什麼最短路徑的拓撲排序是O（V + E）的Big-O。下面是算法： 1. Topologically sort G into L; 2. Set the distance to the source to 0; 3. Set the distances to all other vertices to infinity; 4. For each vertex u in L 5.

2熱度

1回答

如何使我的拓撲排序爲線性時間？（代碼註釋很好）

問題1：對於實施良好的拓撲排序，正確的運行時間應該是多少？我看到了不同的意見： Wikipedia says: O(log^2(n)) Geeksforgeeks says: O(V+E) 問題2：我的實現是運行在O（V * E）。因爲在最壞的情況下，我需要循環遍歷圖E次，每次我需要檢查V項。我如何使我的實現進入線性時間。該算法在步驟：產生圖形在鄰接表例如的形式該曲線圖 0 - - 2

0熱度

1回答

是否可以在不使用樹的情況下進行部分排序？

背景：所以我有幾百個元素（圖像是一個簡單的情況下），我需要不斷地重新排序因爲它們的排序值發生變化時的元素X或Y值的變化。正常（絕對）排序是不可能的，因爲許多元素彼此之間存在未定義關係（如紫色和橙色塊），只會破壞合併/快速/冒泡排序。然而，改變單個元素可能會改變許多訂購關係，如果該元素對其他許多人有優勢（比如，如果綠色塊被刪除）我理解構建樹和做拓撲排序背後的想法，但這似乎由於單個元素的變化，所以

0熱度

1回答

在DAG中合併不可達頂點可能會創建循環？

我有一個DAG（有向無環圖），其中我需要合併一些彼此不可達的頂點。我的最終圖應該是DAG。我的問題是通過做這個操作，做最後的圖可以有循環嗎？

3熱度

1回答

查找字符的優先級在字典

**給出一個字符串詞典[字符串都在有序]你必須要找到根據字典字符的優先級.. 吃 BXY e爲根據字典上面的排名b！** 我試圖解決這個問題，用拓撲排序，並寫了下面的代碼，它給了我ebxyat的輸出。我無法確定我的解決方案，有什麼建議嗎？（這個問題在谷歌接受採訪時問） public static ArrayList<Vertex> topologicalSort (List<Vertex> gr

2熱度

1回答

如何使用拓撲排序在有向圖中找到一個循環？

我在程序中實現這個僞代碼，以檢查是否有向圖是非循環： L ← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edges while S is non-empty do remove a node n from S add n to tail of

2熱度

1回答

快速拓撲排序，當節點順序顯着時？

我正在做關於Hackerrank的this problem。問題摘要如下：您正在嘗試重構範圍[1,10^6]中M個不同整數的序列。您得到長度爲2的子序列= N < = 10^3個子序列2 < = K < = 10^3。如果有兩個序列是可能的，則返回按字典順序較小的序列。我的算法如下：爲每個不同的整數創建一個頂點。將它們存儲在哈希映射中。對於每一行，如果i在該行之前出現j，則將i的邊添加到j

3熱度

1回答

唯一拓撲排序意味着存在哈密頓路徑

在DAG中，爲了找到哈密爾頓路徑，首先找到拓撲排序，然後從拓撲排序中找到哈密爾頓路徑。 Hamiltonian path in a DAG exists if and only if there is unique topological sorting. 我們如何證明這一說法？