按遞增順序在鄰接列表中排序列表

-1

在有向圖中，我想要一個O（n + m）算法對鄰接列表中的列表進行排序，以便每個列表中的頂點名稱按遞增順序排序。我能想到的唯一辦法是在每個列表上執行插入排序，但是這絕對不會在O（n + m）中運行。有人可以幫我弄這個嗎？謝謝按遞增順序在鄰接列表中排序列表

來源

2016-02-04 verticese

我不相信這是可能的。您對O（n + m）時間的請求表明您正在尋找圖表的topological sort。但是，雖然這將對圖進行排序，但它不允許按照另一個度量（字符串節點名稱）對節點/邊進行排序所需的比較。

也許你沒有明確說明問題？

來源

2016-02-04 04:43:51

我還沒有足夠的積分通過評論問這個問題，所以我將假設n是頂點的數量，m是邊的數量。按頂點名稱排序，我假設你的意思是你想按字母順序排序。如果是這樣的話，那麼你可能會使用線性時間排序算法來實現O（n + m），即基數排序。只要頂點名稱的長度不是很大，對每個列表使用基數排序將花費O（n + m）時間總計。查看wiki的基數排序：

https://en.wikipedia.org/wiki/Radix_sort

來源

2016-02-04 04:46:42 ghui

按遞增順序在鄰接列表中排序列表

回答

相關問題