Solved

Writing a program to perform DFS and BFS

Posted on 2004-04-15
4
2,578 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 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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
SetCurrentDirectory path limit 7 145
Better understanding on C++ Class serialization and formats 9 86
gdb doesn't stop on breakpoint 2 114
Why isn't object file created? 6 93
In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
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 viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

726 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