按递增顺序在邻接列表中排序列表

-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

按递增顺序在邻接列表中排序列表

回答

相关问题