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

我有一个节点/顶点的列表，以及连接这些节点的线/边的列表。这些列表不是以任何方式排序或排序的，而是包含特定数据集的所有边和节点。
边是由笛卡尔坐标（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

最佳答案

你说有两个假设：
节点r1和r2可以清楚地识别为根节点，因为它们上的节点类型不同。（带有红色外圆的同心圆）。
直接连接到节点的所有边的列表也可用，例如，节点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
    }
}

现在，开始处理队列。对于从队列中提取的每个节点名：
在finalTree中为该节点创建一个条目。
从segmentDict获取该节点的连接列表。
对于每个节点连接，如果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]);
    }
}

当然，您会希望优化输出，但这说明了如何从根遍历树。