0

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

边是由笛卡尔坐标定义的线段，(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,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

4

1 回答 1

0

你说有两个假设：

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

我将假设还有 segment 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]);
    }
}

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

于 2019-01-07T04:44:24.743 回答