algorithm - 从坐标列表和连接它们的边列表创建一个 k-ary 树。

Question

我有一个节点/顶点列表，以及连接这些节点的线/边列表。这些列表没有以任何方式排序或排序，但包含特定数据集的所有边和节点。

边是由笛卡尔坐标定义的线段，(x1,y1)和(x2,y2)，每个节点位置也用(x,y)形式的坐标表示。附上图片depicts a typical test case ，清楚地显示了两棵树，根为 R1 和 R2，每个节点，包括叶节点(标记为 Lx，突出显示的橙色文本和蓝色圆圈)都显示有相应的坐标。

class Node
{
  Point coordinates;   // x,y coordinates of node <int,int>
  Node parentNode;     // parent node of current node. ( may not be necessary as parentID may suffice to keep reference to parent node)
  List<Node> children; // List of all child nodes of this node
  List<Edge> edges;    // list of all edges connected to this node
  string Data;         // relevant data of each node
  long   nodeID;       // current nodes ID
  long   parentID;     // ID of current node's parent node
}

每条边表示为:

class Edge
{
    Point p1;     // first end coordinates of line segment
    Point p2;     // coordinates of the other end of the segment
}

从附图中可以清楚地看出，边 N1-N2 将表示为 p1= (0,0), p2=(20,20) 或 p1 =(20,20), p2 = (0, 0).顺序是随机的。

假设 1:节点 R1 和 R2 可以清楚地识别为根节点，因为它们上面的节点类型。 (带红色外圈的同心圆)。假设 2:直接连接到节点的所有边的列表也是可用的，例如，节点 N8 将具有段:N8-L7，N8-R2，N8-N9，N8-N7。

我的问题是如何在 C# 中编写一个函数，它有两个输入，一个边列表和一个节点列表，并返回一个根节点，或者引用子节点的树的根节点，这也将与附图中描述的内容相同/真实。

List<Node> getRootNodes(List<Node> nodes, List<Edge> edges)
{
     // implementation here
     List<Node> roots = new List<Node>();
     //more logic
     //
     //
     return roots;  //returned list may have more than one root node!
}

我已经能够列出每个节点的边缘，但无法找到构建树的方法。我读过 Kruskal's Algorithm , 但我不确定我是否可以适应这个问题。我不确定它是否会保留图中显示的顺序。

所有代码都在 C# 中，但任何 C 风格的语言解决方案都可以。

注意:我在本网站上看到的答案假设树节点的父节点和子节点的顺序是已知的。我可以看出两个节点由边连接，但不能确定哪个节点是父节点，哪个是子节点。

谢谢，

格雷格·M

Answer 1

你说有两个假设:

1. 节点 R1 和 R2 可以清楚地识别为根节点，因为它们上面的节点类型。 (带红色外圈的同心圆)。
2. 所有直接连接到节点的边的列表也是可用的，例如，节点 N8 将有段 N8-L7, N8-R2, N8-N9, N8-N7 .

我假设还有段 L7-N8, R2-N8, N9-N8, N7-N8 .如果没有，您可以根据您提到的现有分割轻松地构建它们。

您在回答我的问题时还说，根没有父节点，每个节点只有一个父节点。这使这变得容易得多。

首先，创建一个以节点名称为键的字典，值为它所连接的节点列表。这将是 Dictionary<string, List<string>> .在上面的示例中，您将拥有:

key    value
N8     L7, R2, N9, N7
L7     N8
R2     N8
N9     N8
N7     N8

在上面的列表中，只有 N8 是完全填充的。您的字典将包含所有节点的所有连接。

构建这个:

var segmentDict = new Dictionary<string, List<string>>();
foreach (var segment in SegmentList)
{
    List<string> nodeConnections;
    if (!segmentDict.TryGetValue(segment.From, out nodeConnections))
    {
        // This node is not in dictionary. Create it.
        nodeConnections = new List<string>();
        segmentDict.Add(segment.From, nodeConnections);
    }
    nodeConnections.Add(segment.To);
}

现在，我们将构建一个新的 Dictionary<string, List<string>>最初是空的。这将是最后一棵树，每个节点只有子节点。

因为您知道根节点没有父节点，并且一个节点只有一个父节点，所以您可以从根节点开始建立连接。扫描字典并将每个根节点添加到队列中，并在 finalTree 中创建一个条目有一个空的子列表:

var finalTree = new Dictionary<string, List<string>>();
var nodeQueue = new Queue<string>();

foreach (var nodeName in segmentDict.Keys)
{
    if (nodeName.StartsWith("R")) // if it's a root node
    {
        finalTree.Add(nodeName, new List<string>()); // add tree node
        nodeQueue.Enqueue(nodeName); // and add node to queue
    }
}

现在，开始处理队列。对于您从队列中提取的每个节点名称:

1. 在 finalTree 中创建一个条目对于那个节点。
2. 从 segmentDict 获取该节点的连接列表.
3. 对于每个节点连接，如果 finalTree 中没有该节点的条目，将节点添加到队列中，并将其添加到 finalTree 中此节点的连接列表中.

重复直到队列为空。

代码看起来像这样:

while (nodeQueue.Count > 0)
{
    var fromNode = nodeQueue.Dequeue();
    var nodeChildren = finalTree[fromNode];
    foreach (var toNode in segmentDict[fromNode])
    {
        if (finalTree.ContainsKey(toNode))
        {
            // This node has already been seen as a child node.
            // So this connection is from child to parent. Ignore it.
            break;
        }
        nodeChildren.Add(toNode);  // update children for this node
        finalTree.Add(toNode, new List<string>()); // create tree entry for child node
        nodeQueue.Enqueue(toNode); // add child to queue
    }
}

我在这里所做的是从根到叶跟随树，所以我第一次遇到节点时，我知道它是父子链接而不是子父链接。所以所有的父子链接都被删除了。

然后，你可以通过 finalTree 得到你的树并对每个根节点进行深度优先遍历:

foreach (var kvp in finalTree)
{
    if (kvp.Key.StartsWith("R"))
    {
        PrintTree(kvp.Key, kvp.Value);
    }
}

void PrintTree(string nodeName, List<string> children)
{
    Console.WriteLine("node {1} has children {2}.", nodeName, string.Join(",", children);
    foreach (var child in children)
    {
        PrintTree(child, finalTree[child]);
    }
}

当然，你会想要美化输出，但这展示了如何从根部遍历树。