根据坐标列表和连接它们的边列表创建k元树

Question

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

边是由笛卡尔坐标(x1，y1)和(x2，y2)定义的线段，并且每个节点位置也由形式为(x，y)的坐标表示。所附的图像描绘了一个典型的测试用例，清楚地显示了两棵树，根为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,0)，p2=(0,00)。顺序是随机的。

假设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算法的文章，但我不确定我是否能把它适应这个问题。我不确定它是否能保持图中所示的顺序。

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

注意：我在这个网站上看到的答案假设树节点在父节点和子节点方面的排序是已知的。我可以判断两个节点通过边连接，但无法确定哪个节点是父节点，哪个节点是子节点

谢谢你，

Greg 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]);
}
}

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