title: BFS and DFS of a graph in C++
body: <p>I have been trying to do a BFS and DFS of my graph. I have tried everything but still cannot figure out what is wrong with my algorithm. Please help me with this.</p>
  
  <p>I send the vertices with is my vector that points to the vertexes of my graph to the bfs and bfs in order to go through it and seek for the correct values. I am new to this and am having a lot of problem trying to solve it. It would be nice if someone could go through my code and see where I am wrong in my algorithm. I hope a fresh pair of eyes would be able to detect the problem.</p>
  
  <p>It does show the output but is wrong!</p>
  
  <p>This is my input values for graph::
  5 1, 
  5 2, 
  5 3, 
  1 4, 
  1 6 </p>
  
  <p>Here 1 is the edge of 5, 2 is the edge of 5, 3 is the edge of 5 and so on....</p>
  
  <p>And this is the output I get:
  for BFS:
  5,1,2,3,4,6</p>
  
  <p>for DFS:
  5,4,3,2,1,5</p>
  
  <p><strong>Here is my algorithm for it:</strong></p>
  
  <pre><code>#ifndef SORT_HPP
  #define SORT_HPP
  
  #include &lt;string&gt;
  #include &lt;iostream&gt;
  #include &lt;fstream&gt;
  #include &lt;sstream&gt;
  #include &lt;list&gt;
  #include &lt;vector&gt;
  #include &lt;stack&gt;
  #include &lt;algorithm&gt;
  #include "clsVertex.hpp"
  #include "clsFileGraph.hpp"
  #include "clsGraph.hpp";
  
  class bfs : public clsGraph{
      int vert;
  
  public:
      bfs(int s, vector&lt;clsVertex*&gt; verticies); //prints BFS traversal from a given source
  
  };
  
  class dfs: public clsGraph{
      int vert;
      list&lt;int&gt; adj;
  
  public:
      dfs(int s, vector&lt;clsVertex*&gt; verticies);   //prints DFS traversal from a given source
  
  };
  
  bfs::bfs(int s, vector&lt;clsVertex*&gt; verticies){
  
      bool *visited = new bool[verticies.size()]; //creates a new boolean array of the size of the graph
  
      for (int i = 0; i &lt; verticies.size(); i++){ //loops till the end of the graph
          int x = verticies[i]-&gt;ID;   //gets the value of each vertex
              //cout &lt;&lt; "The val: " &lt;&lt; verticies[i]-&gt;ID &lt;&lt; endl;
              visited[x] = false; //marks that vertex as unvisited i.e: visited = false
      }
  
      list&lt;int&gt; queue;    //creates a queue
      visited[s] = true;  //marks the starting point as visited
      queue.push_back(s); //adds the starting point to the queue
      cout &lt;&lt; endl &lt;&lt; "The breath first sort is as follows:-" &lt;&lt; endl &lt;&lt; endl;
      while (queue.size() != 0){  //loops until the size of the queue is 0 
          for (int i = 0; i &lt; verticies.size(); i++){ //loops 
              int y = verticies[i]-&gt;edges.size();
              for (int j = 0; j &lt; y; j++){
                  int z = verticies[i]-&gt;edges[j]-&gt;ID;
  
                  if (visited[z]== false){
                      visited[z] = true;
                      queue.push_back(z);
                  }
  
              }
          }
          cout &lt;&lt; s &lt;&lt; ",";
          queue.pop_front();
          if (queue.size() == 0)
              goto here;
          s = queue.front();
  
      }
      here:
      cout &lt;&lt; ID &lt;&lt; " " &lt;&lt; graphType &lt;&lt; endl;
      for (int i = 0; i &lt; verticies.size(); i++){
          cout &lt;&lt; verticies[i]-&gt;ID &lt;&lt; "-&gt;";
          for (int j = 0; j &lt; verticies[i]-&gt;edges.size(); j++){
              cout &lt;&lt; verticies[i]-&gt;edges[j]-&gt;ID &lt;&lt; endl;
          }
      }
  
      cout &lt;&lt; endl &lt;&lt; endl &lt;&lt; "Done" &lt;&lt; endl &lt;&lt; endl;
  }
  
  
  
  
  // DFS traversal of the vertices reachable from v. It uses recursive DFSUtil()
  dfs::dfs(int s, vector&lt;clsVertex*&gt; verticies)
  {
      // Mark all the vertices as not visited
      bool *visited = new bool[verticies.size()]; //creates a new boolean array of the size of the graph
  
      for (int i = 0; i &lt; verticies.size(); i++){ //loops till the end of the graph
          int x = verticies[i]-&gt;ID;   //gets the value of each vertex
          //cout &lt;&lt; "The val: " &lt;&lt; verticies[i]-&gt;ID &lt;&lt; endl;
          visited[x] = false; //marks that vertex as unvisited i.e: visited = false
      }
      stack &lt;int&gt; depth;
      visited[s] = true;
      depth.push(s);
      //cout &lt;&lt; s &lt;&lt; ",";
      while (depth.size() != 0){  //loops until the size of the queue is 0 
          for (int i = 0; i &lt; verticies.size(); i++){ //loops 
              int y = verticies[i]-&gt;edges.size();
              for (int j = 0; j &lt; y; j++){
                  int z = verticies[i]-&gt;edges[j]-&gt;ID;
  
                  if (visited[z] == false){
                      visited[z] = true;
                      depth.push(z);
                  }
  
              }
          }
          cout &lt;&lt; s &lt;&lt; ",";
          depth.pop();
          if (depth.size() == 0)
              goto there;
          s = depth.top();
  
      }
  there:
      cout &lt;&lt; "done";
  
  }
  #endif
  </code></pre>