通过链接到自身的深度优先搜索节点进行注入。 C++

Question

正在研究解决浇注问题的程序：

我想我已经到了最后一期了。我的数据结构如下：我有一个 Node 指针向量，每个节点都包含一个 int 数组和一个指向下一个节点的地址。在测试中一切正常。这个数据结构的目标是基本上起到邻接表的作用。每个节点 linked 到它有边的节点。

目前我的问题是当我试图 link 这些节点时：我拥有的 LinkState 函数应该可以完成此操作，但它会导致程序运行...forever.

该函数应该简单地遍历 linked 列表中的各个节点并找到连接新节点的位置。相反，它会导致节点不断向自身泄漏。这会导致运行时问题。

抱歉，如果这有点令人困惑。任何帮助将不胜感激。

p.s。我知道有更好的方法可以解决这个问题，比如 BFS，我想坚持使用 DFS。

#ifndef _POURINGLIST_H_
#define _POURINGLIST_H_
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
 struct Node{
    int state[3];
    Node* next = NULL;
  };
class PouringList{
  Node* init;
  vector<Node*> Head;
  int max[3];
  int steps;
public:
  PouringList(){
    //max values for comaprison
    max[0] = 10;
    max[1] = 7;
    max[2] = 4;
    //init values to begin DFS
    init = new Node;
    init->state[0] = 0;
    init->state[1] = 7;
    init->state[2] = 4;
  };
//private methods not to be called by user
private:
  //pours some good old h2o
  Node pour(Node* curr_state, int A, int B){
    int a = curr_state->state[A];
    int b = curr_state->state[B];
    int change = min(a, max[B]-b);
    Node newState = *curr_state;
    newState.state[A] = (a-=change);
    newState.state[B] = (b+=change);
    return newState;
  }
  //O(n) complexity used to check if a node is already in head 
  bool isIn(Node* find_me){
    for(vector<Node*>::iterator i = Head.begin(); i != Head.end(); i++) {
      if (equal(begin(find_me->state), end(find_me->state), begin((*i)->state)))
        return true;
      }
    return false;
  }
  void printNode(Node* print){
    for(int i = 0; i < 3; i++){
      cout << print->state[i] << " ";
    }
    cout << endl;
  }

  int locate(Node* find_me){
    for(vector<Node*>::iterator i = Head.begin(); i != Head.end(); i++) {
      if (equal(begin(find_me->state), end(find_me->state), begin((*i)->state)))
        return distance(Head.begin(), i);
      }
    return -1;
  }
  void LinkState(Node* head, Node * nxt){
    Node* vert = Head[locate(head)];
    while(vert->next != NULL){
      vert = vert->next;
    }
    vert->next = nxt;
  }
public:
  void DFS(){
    steps = 0;
    //start exploring at initial value
    explore(init);
  }
  void explore(Node* vertex){
    //base case to end
    if(!isIn(vertex)){
      Head.push_back(vertex);
      if(vertex->state[1] == 2 || vertex->state[2] == 2){
        cout << steps << endl;
        printNode(vertex);
        return;
      }
      //generate all possible states and connects them to Head vertex
      else{
        for(int i = 0; i < 3; i++){
          for(int j = 0; j < 3; j++){
            Node conn1 = pour(vertex,i,j);
            Node *conn = &conn1;
            if(i!=j && !isIn(conn)){
              cout << i << " adds water to " << j << endl;
              LinkState(vertex, conn);
            }
          }
        }
      }

      Node* Nextex = vertex;
      //printNode(vertex);
      while(Nextex != NULL){
        //new neighbor
        if(!isIn(Nextex)){
          //printNode(Nextex);
          explore(Nextex);
        }
        Nextex = Nextex->next;
      }
    }
        //printNode(Nextex);
    else{
      cout <<"Dead end" << endl;
    }
  }

  //start from init node and show path to solution
  void display(){
    Node *output;
    for(int i = 0; i < Head.size(); i++){ 
      output = Head[i];
      while ( output != NULL){
        printNode(output);
        output = output->next;
      }
      cout << '#'  <<endl;
    }
  }
};
#endif  // _POURINGLIST_

基本驱动程序：

#include "PouringList.h"
int main(){
    PouringList s1;
    s1.DFS();

}

编辑

我之前尝试过建议的修复方法（这就是我假设您的意思）。它仍然导致编程运行永远。此外，我对 smartpointers 的了解还不够多，无法对应用程序进行大修！

Node conn1 = pour(vertex,i,
Node *conn = new Node;
conn = &conn1;

Answer 1

您正在列表中存储局部变量的地址。

在explore中，你有

        Node conn1 = pour(vertex,i,j);
        Node *conn = &conn1;

然后稍后将 conn 传递给 LinkState，后者将该指针存储在您的 PouringList 中。您添加的所有节点都将指向相同的内存地址。

您应该做的是分配一个新的 Node 并使用它（最好使用某种智能指针而不是存储原始指针，以便自动进行清理）。

通过链接到自身的深度优先搜索节点进行注入。 C++

Pouring via Depth First Search node linking to itself. C++

c++

graph

linked-list

depth-first-search

adjacency-list