Solved

# Writing a program to perform DFS and BFS

Posted on 2004-04-15

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.