**News Alert:**Experts Exchange Confirmed as Safe in Cloudbleed Leak Read More

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.

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

Title | # Comments | Views | Activity |
---|---|---|---|

How to fix the Ubuntu Linux 15.10 Files GUI manager , Nautilus , flickers on and off? | 9 | 102 | |

Grammars for C C++ and java | 1 | 122 | |

why is it wrong to combine interface and abstract class; acquire the method externally? | 4 | 100 | |

computer science syllabus | 3 | 83 |

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