0

次のようなノード（基本的にグラフの頂点）テンプレート化されたクラスがあります。

template<class T>
class Node
{
   public:
      T Data;
      Node<T>* Parent;
      vector<Node<T>*> Children;
};

次に、グラフのルートをカプセル化するテンプレート化されたグラフ クラスがあり、(オイラー パスの存在条件が満たされているかどうかを確認した後) オイラー パスを生成することになっているメソッドがあります。

template<class T>
class Graph
{
   public:
      Node<T>* Root;

      vector<Node<T>*> GetEulerianPath() const;
      bool HasEulerianPath() const;
};

HasEulerianPath()は、ノード(*頂点*) 階層をトラバースし、次数が奇数の頂点の数をカウントします。それらが 2 つ以下の場合、true を返します。

問題は次のとおりです-アルゴリズムをどのように実装するのか正確にはわかりません。ヒントはありますか?ベクター内の階層全体を抽出し、それを繰り返し処理する必要がありますか?それともNodeの再帰的な方法を使用する必要がありますか?ウィキペディアのページでは、リンクされたリスト...または、 GetEulerianPath()メソッドの出力として、新しい小さな単方向グラフを生成する必要があるのでしょうか?ここでどのように進めればよいか混乱しています。

4

2 に答える 2

0

最初にグラフを変換する必要があります。しかし、間違いなく std::vector ではありません。

ノードごとに、未使用のエッジをすばやく取得できる必要があります (それらをすべてリンクされたリストに入れ、使用すると削除します)。

したがって、各ノードには、std::vector ではなく、子のリンク リストが必要です。

次に、未使用のエッジを持つノードを見つけられるようにする必要があります。トラバース中にそれらをリンクされたリストに集めることができます。O(1) でパスを変更できるように、未使用のエッジのリストはこのリストを参照する必要があります。

(Node<T>* Parent;あなたのコードの は、一般的なグラフでは奇妙に思えます。)

于 2013-10-25T13:19:11.580 に答える