我有两个问题：
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
1 {A, 4, 9}
2 {B, 6, 1}
3 {C, 1, 3}
4 {D, 3,10}
5 {E, 7, 2}
6 {F, 4, 2}
7 {G, 9, 8}
8 {H,10, 5}
9 {I, 7, 5}
10 {J, 6, 8}
1 {C, 1, 3}
2 {F, 2, 4} (nodes swapped)
3 {D, 3,10}
4 {A, 4, 9}
5 {I, 5, 7} (nodes swapped)
6 {B, 6, 1}
7 {E, 7, 2}
8 {J, 8, 6} (nodes swapped)
9 {G, 9, 8}
10 {H,10, 5}
如果按照节点1的顺序排序，那么我们可以将这个列表或数组读作链表：
start with item 1: {C, 1, 3}
read node2: 3
skip to item 3: {D, 3,10}
read node2: 10
skip to item 10: {H,10, 5}
...
skip to item 6: {B, 6, 1}
read node2: 1
end of list
result: C D H I E F A G J B
look at item 1: {A, 4, 9}
if item 4 has a node1 different from 4, swap item 1 and 4
else, change item 1 to {A, 9, 4} and swap item 1 and 9
(-> item 1 and 4 swapped)
while current item is already in-place, skip to next
(-> stay at item 1)
look at new item 1: {D, 3,10}
if item 3 has a node1 different from 3, swap item 1 and 3
else, change item 1 to {D,10, 3} and swap item 1 and 10
(-> item 1 and 3 swapped)
while current item is already in-place, skip to next
(-> item 1 is now {C, 1, 3}, so skip to item 2)
...
look at item 1: {A, 4, 9}
if new list has no item 4, copy item 1 as item 4 to the new list
else, change item 1 to {A, 9, 4} and copy as item 9 to the new list
move to next item
更新
我刚意识到，订购物品的步骤可能会比上述描述的（大大）增加。例如，如果您首先将 {A,4,8} 移动到位置 4，将 {B,5,9} 移动到位置 5，然后遇到 {C,4,5}，您就会卡住。然后，您必须将 {C,4,5} 与其他两个项目之一交换，交换另一个项目中的节点，并将其移动到位。该新位置本身可能已被占用，等等，因此无法知道两个选项中哪个更小。在最坏的情况下，交换次数接近 N2。
更新2
当然，可以通过将项目存储为双向链表来解决上述问题。例如，遇到{A,4,8}时，将{A,8}存储为项目4，将{A,4}存储为项目8，然后对于{B,5,9}，将{B,9}存储为项目5，将{B,5}存储为项目9，然后对于{C,4,5}，将其添加到已存储的项目中，使项目4变为{A,8,C,5}，项目5变为{B,9,C,4}。然后可以在两个方向上遍历双向链表。这将增加需要完成的工作和使用的空间，但仍然与列表中的项目数量成线性关系。
class Program
{
class Cell
{
public string Id { get; set; }
public int Node1 { get; set; }
public int Node2 { get; set; }
public int Min { get { return Math.Min( Node1, Node2 ); } }
public Cell( string name, int node1, int node2 )
{
Id = name;
Node1 = node1;
Node2 = node2;
}
public override string ToString()
{
return Id + "(" + Node1.ToString() + "," + Node2.ToString() + ")";
}
}
static void Main( string[] args )
{
var A = new Cell( "A", 4, 9 );
var B = new Cell( "B", 6, 1 );
var C = new Cell( "C", 1, 3 );
var D = new Cell( "D", 3, 10 );
var E = new Cell( "E", 7, 2 );
var F = new Cell( "F", 4, 2 );
var G = new Cell( "G", 9, 8 );
var H = new Cell( "H", 10, 5 );
var I = new Cell( "I", 7, 5 );
var J = new Cell( "J", 6, 8 );
var cells = new List<Cell>() { A, B, C, D, E, F, G, H, I, J };
// A dictionary to store the cells corresponding to each node values
Dictionary<int, List<Cell>> dict = new Dictionary<int, List<Cell>>();
// Add all the cells to the dictionary
foreach ( var cell in cells )
AddCell( dict, cell );
// Start with arbitrary first cell and remove it from the dictionary
var currentCell = GetCell( dict, A.Node1 );
RemoveCell( dict, currentCell );
// The result is a list of cells initialized with the first cell
var result = new List<Cell>() { currentCell };
// Calculation loop
bool doContinue = true;
while ( doContinue )
{
// Tries to get a next cell from the node1 of current cell...
var nextCell = GetCell( dict, currentCell.Node1 );
// ... or if not found, tries to get it from node2
if ( nextCell == null )
nextCell = GetCell( dict, currentCell.Node2 );
if ( nextCell == null )
// If not found, we stop
{
doContinue = false;
}
else
// If found
{
// Add the next cell to the result
result.Add( nextCell );
// Remove the cell
RemoveCell( dict, nextCell );
}
// The next cell becomes the current cell
currentCell = nextCell;
}
}
// Adding a cell puts the cell against its two nodes values
static void AddCell( Dictionary<int, List<Cell>> dict, Cell cell )
{
List<Cell> cells = null;
if ( dict.TryGetValue( cell.Node1, out cells ) == false )
{
cells = new List<Cell>();
dict[cell.Node1] = cells;
}
cells.Add( cell );
if ( dict.TryGetValue( cell.Node2, out cells ) == false )
{
cells = new List<Cell>();
dict[cell.Node2] = cells;
}
cells.Add( cell );
}
// Gets a cell from a node value
static Cell GetCell( Dictionary<int, List<Cell>> dict, int node )
{
var cell = null as Cell;
var cells = dict[node];
if ( cells.Count > 0 )
cell = cells.First();
return cell;
}
// Removes a cell from the dictionary for both node1 and node2 entries.
static void RemoveCell( Dictionary<int, List<Cell>> dict, Cell cell )
{
dict[cell.Node1].Remove( cell );
dict[cell.Node2].Remove( cell );
}
}
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