Solved

Writing a program to perform DFS and BFS

Posted on 2004-04-15
4
2,575 Views
Last Modified: 2008-02-26
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.
0
Comment
Question by:krissi19
4 Comments
 
LVL 11

Accepted Solution

by:
bcladd earned 500 total points
ID: 10844464
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

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…

910 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now