“循环链表生成器”的最快算法
“循环链表生成器”的最快算法
提问于 2017-02-11 15:35:12
我有两个问题：
1)以“连接”顺序排列这个列表的最快算法是什么？
2)这是一个存在的问题/算法吗?它有什么名称？
节点总是以循环方式连接，所以我的起始ID并不重要。
鉴于这一清单：
id node1 node2
A 4 9
B 6 1
C 1 3
D 3 10
E 7 2
F 4 2
G 9 8
H 10 5
I 7 5
J 6 8node1 & node2没有一个特定的顺序，所以id A可以是4-9，也可以是9-4。
输出应该是这样的(如果以A开头也没关系，只要输出是一个链)。
node ids: 4 - 9 - 8 - 6 - 1 - 3 - 10 - 5 - 7 - 2 - 4
ids: A G J B C D H I E F(我正在用C#编写代码。但是任何语言的伪代码都行)
回答 4
Stack Overflow用户
回答已采纳
发布于 2017-02-12 02:30:18
你可以这样做：
static IEnumerable<Edge<T>> OrderEdges<T>(this IEnumerable<Edge<T>> edges)
where T : IEquatable<T>
{
Debug.Assert(edges.Any());
var map = new Dictionary<T, Edge<T>>();
foreach (var e in edges)
{
if (map.ContainsKey(e.Node1))
{
Debug.Assert(!map.ContainsKey(e.Node2));
map.Add(e.Node2, e);
}
else
{
map.Add(e.Node1, e);
}
}
var current = edges.First();
var orderedEdges = new HashSet<Edge<T>>();
while (true)
{
orderedEdges.Add(current);
yield return current;
if (orderedEdges.Count == map.Count)
break;
var next = map[current.Node2];
current = orderedEdges.Contains(next) ? map[current.Node1] : next;
}
}其中，Edge<T>类只是：
class Edge<T> where T: IEquatable<T>
{
public T Node1 { get; }
public T Node2 { get; }
public string Name { get; }
public Edge(string name, T node1, T node2)
{
Name = name;
Node1 = node1;
Node2 = node2;
}
public override string ToString() => Name;
}如果我们抓到这个小家伙
var edges = new List<Edge<int>>() {
new Edge<int>("A", 4, 9), new Edge<int>("B", 6, 1),
new Edge<int>("C", 1, 3), new Edge<int>("D", 3, 10),
new Edge<int>("E", 7, 2), new Edge<int>("F", 4, 2),
new Edge<int>("G", 9, 8), new Edge<int>("H", 10, 5),
new Edge<int>("I", 7, 5), new Edge<int>("J", 6, 8) };
Console.WriteLine(string.Join(" -> ", edges.OrderEdges()));我们得到了预期的结果：
A -> G -> J -> B -> C -> D -> H -> I -> E -> F请注意，此解决方案的前提是输入数据格式良好。
Stack Overflow用户
发布于 2017-02-11 15:49:39
我相信你在找欧拉路径
Stack Overflow用户
发布于 2017-02-11 15:51:01
我不知道这是不是个有名字的数学题。下面是伪代码，它允许您以O(N)方式(复杂性和内存使用)解决问题。
1)创建数组(假设节点在0.N1范围内具有唯一的ID。并将其填充为节点( id节点应放置在id位置)
2)选择任何节点并将其推入单独的列表中(它将按“循环”顺序包含节点)。列表中的最后一个节点将被命名为已处理节点。
3)在每一步中，从1迭代到N -1，选择处理节点的不遍历邻居。将未遍历的节点推入循环列表。连续过程
注意:检查“未遍历”属性可以以O(1)方式执行。请看，它已经在循环列表中出现了。它应该是最后一个(处理)节点的邻居。
这类算法的主要缺点是存在唯一的Euler路径。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/42177688
复制相关文章
相似问题
腾讯云开发者
