[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

Writing a program to perform DFS and BFS

Posted on 2004-04-15
4
Medium Priority
?
2,583 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
4 Comments
 
LVL 11

Accepted Solution

by:
bcladd earned 2000 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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

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

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
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 viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

656 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