Обход общего класса узлов, перечисление всех узлов приводит к бесконечному циклу

Question

Я практикую обход деревьев / узлов, и я пришел к текущей проблеме.Я хочу иметь возможность подключить один узел к себе.Соедините узел 1 с узлом 2. Узлы могут быть подключены к такому количеству узлов, которое необходимо.Это текущий класс, с которым я писал и тренировался.

Моя проблема в том, что я не могу проверить, прошел ли я уже прошлый узел.То, что я получаю, это бесконечный цикл один -> два -> три -> четыре -> один -> два ... и т. Д.

Можно ли дать подсказку в правильном направлении?

Я хочу, чтобы nodeN.list_connections () мог печатать все узлы, к которым подключен nodeN.

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 (), только если текущий узел не подключен к другому узлу.

РЕДАКТИРОВАТЬ:

Все узлы связаны каким-либо образом.При выводе списка соединений он будет перечислять только соединения с этого узла вниз.Перечисляющие узлы не вернутся к корневому / первому узлу.

РЕДАКТИРОВАТЬ:

, используя только один.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 (), применяемую к целочисленным векторам, хранящим идентификаторы узлов.Для удобочитаемости и удобства использования я завернул его в bool Path::closeCycle(int nid).Поскольку путь может состоять не более чем из | N |элементы класса Path также могут быть представлены n-мерным vector<bool>, что позволит избежать использования std::find().Это может повысить производительность, но, возможно, это зависит от структуры вашего графа (длинные пути + несколько узлов против коротких путей + огромное количество узлов против чего-то между или против экстремумов).

В 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; }
};

В node.cpp

#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");
}