Writing a program to perform DFS and BFS

I am to write a program to perform Depth First Search and Breadth First Search operations on a graph.  I must implemtnt ADT Graph in either array-based or adjacent lists and other ADTs like stack and queue.  The main function must construct the graph first and then perform DFS and BFS operations starting at a particular vertex.  The traversal stops when all the vertices in the graph have been visited.  Here is what I have so far for the DFS:

//Depth First Search

template <class VertexType>
void DFS(GraphType<VertexType> graph, VertexType startVertex, VertexType endVertex)
{
      using namespace std;
      StackType<VertexType> stack;
      QueType<VertexType> vertexQ;

      bool found = false;
      VertexType vertex;
      VertexType item;

      graph.ClearMarks();
      stack.Push(startVertex);
      do
      {
            stack.Pop(vertex);
            if (vertex == endVertex)
            {
                  cout<<vertex;
                  found = true;
            }
            else
            {
                  if (!graph.IsMarked(vertex))
                  {
                        graph.MarkVertex(vertex);
                        cout<<vertex;
                        graph.GetToVertices(vertex, vertexQ);

                        while (!vertexQ.IsEmpty())
                        {
                              vertexQ.Dequeue(item);
                              if(!graph.IsMarked(item))
                                    stack.Push(item);
                        }
                  }
            }
      }while (!stack.IsEmpty() && !found);
      if (!found)
            cout<< "Path not found." << endl;
}

Can someone please help me with the rest.  My biggest problem is the main function because I don't know where to start.
krissi19Asked:
Who is Participating?
 
bcladdCommented:
In what format will your data be? Let's assume it is a list of vertices followed by a list of pairs of vertices. Further, strings are used for vertex names, the string "end-of-vertices" is used to mark the end of the vertex list.

So what do you need to do? Open the inFile stream so that you can read strings from it. It is assumed that vertex names have no spaces in them.

string vertexName;

while ((inFile >> vertexName) && (vertexName != "end-of-vertices")) {
  graph.InsertVertex(vertexName);
}

string sourceName, targetName;

while (inFile >> sourceName >> targetName) {
  graph.InsertEdge(sourceName, targetName);
}

Make sense?

If you have more/different questions, ask.
-bcl
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.