"循环链表生成器"最快的算法

Question

我有两个问题:

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     8

node1和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#中编写代码.但是任何语言的伪代码都可以)

Answer 1

您可以通过以下方式进行操作：

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

请注意，此解决方案假定输入数据格式良好。