Depth First検索ノード経由での注釈。 C++

Question

注ぎ込み問題を解決するためのプログラムでの作業：

私は最後の問題が1つになったと思います。私のデータ構造は以下の通りです： 私はノードポインタのベクトルを持ち、各ノードはint配列と次のノードへのアドレスを含んでいます。すべてのテストで適切に機能します。このデータ構造の目標は、基本的に隣接関係リストとして機能することです。各ノードは、エッジを持つノードにリンクされています。

現在のところ私の問題は、これらのノードを互いにリンクしようとしているときです。 これを達成する必要があるLinkState機能ですが、代わりにプログラムが実行されています...永遠に。

この関数は、単純に個々のノードのリンクリストを反復し、新しいノードをどこに接続するかを見つける必要があります。その代わりに、ノードが絶えず自分自身にリークする原因となっています。これは、実行時の問題につながります。

ご迷惑をおかけして申し訳ありません。どんな助けでも大歓迎です。

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(); 

} 

編集

私は（これは私はあなたが意味すると仮定しているものです）の前に修正案をしようとしました。それでもプログラミングは永遠に実行されます。また、私はスマートポインタについて十分に知っていないアプリケーションをオーバーホール！

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

Answer 1

リストにローカル変数のアドレスを格納しています。 exploreで

、あなたは

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

その後、あなたのPouringListにそのポインタを格納する、LinkStateにconnを渡してきました。追加されたノードはすべて同じメモリアドレスを指します。

Nodeを新規に割り当てて、それを使用してください（好ましくは、クリーンアップが自動的に行われるように、生ポインタを格納するのではなく、スマートポインタを使用してください）。