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

Solved

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.

//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

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.

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

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(vertexN

}

string sourceName, targetName;

while (inFile >> sourceName >> targetName) {

graph.InsertEdge(sourceNam

}

Make sense?

If you have more/different questions, ask.

-bcl

Question has a verified solution.

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

Course of the Month14 days, left to enroll

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