0

ノード/頂点のリストと、これらのノードを接続するライン/エッジのリストがあります。リストはソートまたは順序付けされていませんが、特定のデータ セットのすべてのエッジとノードが含まれています。

エッジはデカルト座標 (x1,y1) および (x2,y2) で定義される線分であり、各ノードの位置も (x,y) 形式の座標で表されます。添付の画像は典型的なテスト ケースを示しており、ルート R1 と R2 を持つ 2 つのツリーを明確に示しています。リーフ ノード (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 のセグメントがあります。

私の質問は、エッジのリストとノードのリストの 2 つの入力を持ち、ルート ノード、または子ノードを参照してツリーのルート ノードを返す関数を 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!
}

各ノードのエッジを一覧表示できましたが、ツリーを構築する方法がわかりません。クラスカルのアルゴリズムについて読んだことがありますが、この問題に適応できるかどうかはわかりません。図に示されている順序が維持されるかどうかはわかりません。

すべてのコードは C# ですが、C スタイルの言語ソリューションであれば何でも構いません。

注: この Web サイトで見た回答は、親ノードと子に関するツリー ノードの順序が既にわかっていることを前提としています。2 つのノードがエッジで接続されていることはわかりますが、どちらのノードが親ノードでどちらが子ノードであるかを判断できません。

ありがとうございました、

グレッグ・M

4

1 に答える 1