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()只是遍历节点(* vertex *) 层次结构并计算具有奇数度的顶点的数量。如果它们不超过两个，则返回 true。

现在的问题是 - 我不太确定如何实现算法。任何提示？我应该只提取向量中的整个层次结构并迭代它还是使用节点的一些递归方法？维基百科页面建议使用一个链表......或者我应该只生成一个新的较小的单向图作为GetEulerianPath()方法的输出？我对如何在此处进行感到困惑。

4

2 回答 2

0

您需要先转换图表。但绝对不是 std::vector。

对于每个节点，您需要能够快速获得未使用的边（将它们全部放在链表中，并在使用时删除）。

因此，每个节点都应该有一个子节点的链表，而不是 std::vector。

接下来，您需要能够找到具有未使用边的节点，您可以在遍历时将它们收集在链表中。您还需要在遍历时使用您的路径构建一个链表，未使用边的列表应参考此列表，以便您可以在 O(1) 中更改路径。

（Node<T>* Parent;对于一般图表，您的代码中的 似乎很奇怪。）

于 2013-10-25T13:19:11.580 回答
0

您构建Node类的方式基本上形成了一个包含在vector. 您似乎有一些问题（数学上）：

给定的“孩子”可以有多个“父母”。事实上，如果有 2 个“子”节点，则必须有2 个“父”节点才能成为欧拉循环。您可能需要重新定义Node如下：

template<class T>
class Node
{
   public:
      T Data;
      list<shared_ptr<Node<T>>> Connections;
};

这将允许您将您的更改Graph为：

template<class T>
class Graph
{
   public:
      shared_ptr<Node<T>> Start; // name change just to convey that there isn't a "root" node in an Eulerian cycle

      list<shared_ptr<Node<T>>> GetEulerianPath() const;
      bool HasEulerianPath() const;
};

这样，实现 Hierholzer 算法只是简单地遍历Connections每个节点的问题。

于 2013-10-25T14:00:57.267 回答