title: Breadth First Search Pruning and Memory Leak C++
body: <p>I'm doing a project that requires me to solve a maze where you cannot turn left.  The program is working fine, except for in cases with very large input.  </p>
  
  <p>My general strategy was to make each spot in the maze 4 nodes in the graph, corresponding to UP, DOWN, LEFT, and RIGHT, where each node has an edge going straight and right, and where straight has weight 0 and right has weight 1.  Edges are represented as an object in my code, and has a pointer to is destination node and its originating node.</p>
  
  <p>To find an optimal path (the path with fewest right turns), I used a breadth-first search with a double ended queue.  I use the deque to be able to push weight 1 nodes to the back and weight 0 nodes to the front.  However, I allocate a small amount memory during the search and not cleaning it up anywhere, which is presumably causing my program to fail very large maze inputs. </p>
  
  <p>Here is the code (specifically the for loop that checks adjacent edges of a node within the BFS):</p>
  
  <pre><code>    //t is a node object in the graph that has been popped out of the deque
  
      //loop that checks each adjacent node from t (adj is a vector of edges)
      for(unsigned int i = 0; i &lt; t.adj.size(); i++)
      {
          if(!t.adj[i].used)
          {
              if(!t.adj[i].dest-&gt;visited)
              {
                  //Memory leak location
                  t.adj[i].dest-&gt;prev = new node(t);
  
                  t.adj[i].used = true;
  
                  //weight of an edge is 1 if it's a right turn, 0 otherwise
                  if(t.adj[i].weight == 1) 
                  {
                      //put the heavier nodes on the end of the queue
                      nodes.push_back(t.adj[i].dest);
                  }
                  //0-weight nodes on the top
                  else nodes.push_front(t.adj[i].dest);                
              }
  
          }
  </code></pre>
  
  <p>I've been trying to figure out how to better prune the search and how to free up this allocation when I definitely won't need those nodes anymore.  But I need some direction for how to think about this.  Let me know if additional code is needed.</p>
  
  <p>Thanks.</p>
  
  <p>EDIT: Node and edge classes (excuse my disregard for standard class designing principles, just threw them together quickly):</p>
  
  <pre><code>class node
  {
  public:
      node();
      node(Direction d, int r, int c, NodeType t);
      ~node(); //empty definition
      node(const node* n);
      node(const node&amp; n);
      node&amp; operator=(const node&amp; n);
      node&amp; operator=(const node* n);
  
      void addAdj(node* a, int w);
      void printAdj() const;
      string direction() const;
  
      void print() const;
      bool operator&lt;(const node&amp; n) const;
  
  
      int distance; //from start
      bool visited;
      node* prev;
      vector&lt;Edge&gt; adj;
      Direction dir;
      int row, col;
      NodeType type;
  };
  ///////////////////////
  struct Edge
  {
  
      Edge();
      Edge(node* o, node* d, int c);
  
      node* org;
      node* dest;
      int weight;
      bool used;
  </code></pre>
  
  <p>};</p>