Solved

Writing a program to perform DFS and BFS

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

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
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…
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.

728 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