遍历一般节点类，在一个无限循环列出所有节点结果

Question

我在练遍历树/节点，我来到了现在的问题。我希望能够在一个节点连接到其自身。连接节点1至节点2的节点可连接到尽可能多的节点作为理想的。这是当前类，我写的，并与实践。

我的问题是，我不能检查，如果我已经走过了过去的节点。我所得到的是一个无限循环 - >双 - >三 - >四 - >一个 - >两个... ...等等。

将有可能得到一个提示，以正确的方向？

我想nodeN.list_connections（）能够打印节点N连接到所有节点。

class Node {
private:
    std::vector<Node*> nodes;
    std::string data;
public:
    Node()
    {
        printf("Status: Created [%d]\n", this);
    }
    void connect(Node& node)
    {
        nodes.push_back(&node);
        printf("Status: Node [%d] Connected To [%d]\n", this, &node);
    }
    void input_data(std::string str_in)
    {
        data = str_in;
    }
    void list_connections()
    {
        printf("List: Start\n");
        printf("Node[this][%d]: %s\n", this, data.c_str());
        for (size_t i = 0; i < nodes.size(); i++)
        {
          printf("Node[i=%d][%d]: %s\n", i, nodes[i], nodes[i]->data.c_str());
          if (this != nodes[i])
             nodes[i]->list_connections();
        }
    }
};

void test_list()
{
    Node one;
    one.input_data("ONE");
    Node two;
    two.input_data("TWO");
    Node three;
    three.input_data("THREE");
    Node four;
    four.input_data("FOUR");

    // one -> two <-> three -> four -> one
    // one -> one
    // two -> two

    one.connect(two);
    one.connect(one);
    two.connect(two);
    two.connect(three);
    three.connect(four);
    four.connect(one);
    three.connect(two);

    one.list_connections();
    //two.list_connections();
    //three.list_connections();
    //four.list_connections();
}

这就是上面我的代码。

我test_list功能检查所有可能的连接方案。

编辑：

我nodeOne.list_connections目前理念（），是，它会通过所有连接到nodeone的节点循环。这些节点也将使用nodeOther.list_connections（）只如果当前节点未连接到其他节点。

编辑：

所有节点都以某种方式连接。当列出的连接只列出从该节点向下连接。清单节点将不会再回到根/第一个节点。

编辑：

通过仅使用one.list_connections（）;输出应该是

 List: Start
 Node[this][7731340]: ONE
 Node[i=0][7731288]: TWO
 Node[i=1][7731340]: ONE
 List: Start
 Node[this][7731288]: TWO
 Node[i=0][7731288]: TWO
 Node[i=1][7731236]: THREE
 List: Start
 Node[this][7731236]: THREE
 Node[i=0][7731184]: FOUR
 Node[i=1][7731288]: TWO
 List: Start
 Node[this][7731184]: FOUR
 Node[i=0][7731340]: ONE

感谢您StephanH指点出来。

Answer 1

你必须解决一个共同的地方问题（避免循环）在图论。您可以创建一个简单的Path类跟踪如果一个节点已经/或正在当前递归堆栈打印。因此，你必须检查新节点已经在递归栈。让我们使用标准的std :: find（）方法应用到存储节点ID的整数向量。为了提高可读性，更容易使用率我bool Path::closeCycle(int nid)包裹它。由于路径可以包含最多的| N |元件Path类也可以由n维vector<bool>这将避免使用std::find()表示。这可以提高性能，但是这或许取决于你图的结构（长路径+几个节点与节点与对extrems之间的事情短路径+休量）。

在node.h

#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>


class Path
{
    std::vector<int> vals;
public:
    Path();
    bool closeCycle(int nid)const;
    void add(int nid);
};

class Node {
private:
    int id;
    std::vector<Node*> nodes;
    std::string data;
public:
    Node(int id) : id(id)
    {
        printf("Status: Created [%d]\n", this);
    }
    void connect(Node& node)
    {
        nodes.push_back(&node);
        printf("Status: Node [%d] Connected To [%d]\n", this, &node);
    }
    void input_data(std::string str_in)
    {
        data = str_in;
    }
    void list_connections(const Path& path = Path());
    inline int getId()const { return id; }
};

由于饮用。 Ç津市p

#include "header.h"

void Node::list_connections(const Path& path)
{
    printf("List: Start\n");
    printf("Node[this][%d]: %s\n", this, data.c_str());


    Path npath(path);
    npath.add(id);
    for (size_t i = 0; i < nodes.size(); i++)
    {
        if (!npath.closeCycle(nodes[i]->id))
        {
            printf("Node[i=%d][%d]: %s\n", i, nodes[i], nodes[i]->data.c_str());
            nodes[i]->list_connections(npath);
        }
    }
    printf("List: %s End\n", data.c_str());
}



Path::Path()
{
}

bool Path::closeCycle(int nid) const
{
    return std::find(vals.begin(), vals.end(), nid) != vals.end();
}

void Path::add(int nid)
{
    vals.push_back(nid);
}

你的main.cpp

void main()
{
    Node one(1);
    one.input_data("ONE");
    Node two(2);
    two.input_data("TWO");
    Node three(3);
    three.input_data("THREE");
    Node four(4);
    four.input_data("FOUR");

    one.connect(two);
    one.connect(one);
    two.connect(two);
    two.connect(three);
    three.connect(four);
    four.connect(one);
    three.connect(two);

    one.list_connections();
    std::cout << "\n\n";
    two.list_connections();
    std::cout << "\n\n";
    three.list_connections();
    std::cout << "\n\n";
    four.list_connections();
    std::cout << "\n\n";

    system("pause");
}