Breadth first search

[clarkkent]

Could you tell me what is wrong with my breadth first search function. I havent implemented the shortest path function but i tried to test it by displaying the predecessors but it does not work. Here is the code.

graph2.h(could not get the code brackets to work, sorry about that)

#include <string>
#include <list>
#include <queue>
#include <iostream>
using namespace std;

class directedGraph
{
private:
class vertex
{
public:
string data;
list<vertex*> neighbors;
bool visited;
vertex *predecesor;
vertex(string x)
{
data = x;
}
};

list<vertex*> vertexList;


//locate vertex containg value x
vertex * findVertex(string x)
{
for each(vertex * v in vertexList)
{
if (v->data == x)
return v;
}
return NULL;
}

public:

directedGraph()
{
}

void addVertex(string x)
{
vertexList.push_back(new vertex(x));
}

//add directed edge going from x to y
void addDirectedEdge(string x, string y)
{
vertex * xVert = findVertex(x);
vertex * yVert = findVertex(y);

xVert->neighbors.push_back(yVert);
}

void addEdge(string x, string y)
{
addDirectedEdge(x, y);
addDirectedEdge(y, x);
}

//display all vertices and who they connect to
void testDisplay()
{
for each(vertex * v in vertexList)
{
cout << v->data << ": ";
for each(vertex * u in v->neighbors)
{
cout << u->data << ", ";
}
cout << endl;
}
}

void testBreadthFirstSearch(string a)
{
breadthFirstSearch(findVertex(a));
displayPredecesors();
}

void displayPredecesors()
{
for each(vertex *v in vertexList)
{
cout<< v->predecesor;
}
}

void shortestPath()
{

}

void breadthFirstSearch(vertex *s)
{
queue<vertex*> Q;
s->visited = true;
Q.push(s);
while (!Q.empty())
{
vertex *x = Q.front();
Q.pop();
for each( vertex *v in x->neighbors)
{
if (s->visited == false)
{
s->visited = true;
v->predecesor = x;
}
}
}
}
};

[clarkkent]

Here is a more readable code

#include <string>
#include <list>
#include <queue>
#include <iostream>
using namespace std;

class directedGraph
{
private:
	class vertex
	{
	public:
		string data;
		list<vertex*> neighbors;
		bool visited; 
		vertex *predecesor; 
		vertex(string x)
		{
			data = x;
		}
	};

	list<vertex*> vertexList;
	

	//locate vertex containg value x
	vertex * findVertex(string x)
	{
		for each(vertex * v in vertexList)
		{
			if (v->data == x)
				return v;
		}
		return NULL;
	}

public:

	directedGraph()
	{
	}

	void addVertex(string x)
	{
		vertexList.push_back(new vertex(x));
	}

	//add directed edge going from x to y
	void addDirectedEdge(string x, string y)
	{
		vertex * xVert = findVertex(x);
		vertex * yVert = findVertex(y);

		xVert->neighbors.push_back(yVert);
	}

	void addEdge(string x, string y)
	{
		addDirectedEdge(x, y);
		addDirectedEdge(y, x);
	}

	//display all vertices and who they connect to
	void testDisplay()
	{
		for each(vertex * v in vertexList)
		{
			cout << v->data << ": ";
			for each(vertex * u in v->neighbors)
			{
				cout << u->data << ", ";
			}
			cout << endl;
		}
	}

	void testBreadthFirstSearch(string a)
	{
		breadthFirstSearch(findVertex(a));
		displayPredecesors();
	}

	void displayPredecesors()
	{
		for each(vertex *v in vertexList)
		{
			cout<< v->predecesor; 
		}
	}

	void shortestPath()
	{

	}

	void breadthFirstSearch(vertex *s)
	{
		queue<vertex*> Q;
		s->visited = true; 
		Q.push(s); 
		while (!Q.empty())
		{
			vertex *x = Q.front();
			Q.pop();
			for each( vertex *v in x->neighbors)
			{
				if (s->visited == false)
				{
					s->visited = true;
					v->predecesor = x;
				}
			}
		}
	}
};

[dhayden]

Refering to clarkkent's listing, you only push one node onto Q. You need to add Q.push(s) around line 109.

Why not do BFS recursively? The code will probably be a lot shorter.

[clarkkent]

Thanks I hadn't seen that. Does it mater if I put it at 111 instead of 109? I also found that the displayPredecessors function was incorrect, I corrected it but now the program stops when I compile. I get this error when I debug... Unhandled exception at 0x00F6B136 in Directed Graph.exe: 0xC0000005: Access violation reading location 0x00000014.

#include <string>
#include <list>
#include <queue>
#include <iostream>
using namespace std;

class directedGraph
{
private:
	class vertex
	{
	public:
		string data;
		list<vertex*> neighbors;
		bool visited; 
		vertex *predecesor; 
		vertex(string x)
		{
			data = x;
		}
	};

	list<vertex*> vertexList;
	

	//locate vertex containg value x
	vertex * findVertex(string x)
	{
		for each(vertex * v in vertexList)
		{
			if (v->data == x)
				return v;
		}
		return NULL;
	}

public:

	directedGraph()
	{
	}

	void addVertex(string x)
	{
		vertexList.push_back(new vertex(x));
	}

	//add directed edge going from x to y
	void addDirectedEdge(string x, string y)
	{
		vertex * xVert = findVertex(x);
		vertex * yVert = findVertex(y);

		xVert->neighbors.push_back(yVert);
	}

	void addEdge(string x, string y)
	{
		addDirectedEdge(x, y);
		addDirectedEdge(y, x);
	}

	//display all vertices and who they connect to
	void testDisplay()
	{
		for each(vertex * v in vertexList)
		{
			cout << v->data << ": ";
			for each(vertex * u in v->neighbors)
			{
				cout << u->data << ", ";
			}
			cout << endl;
		}
	}

	void testBreadthFirstSearch(string a)
	{
		breadthFirstSearch(findVertex(a));
		displayPredecesors();
	}

	void displayPredecesors()
	{
		for each(vertex *v in vertexList)
		{
			cout<< v->predecesor->data; //I added ->data 
		}
	}

	void shortestPath()
	{

	}

	void breadthFirstSearch(vertex *s)
	{
		queue<vertex*> Q;
		s->visited = true; 
		Q.push(s); 
		while (!Q.empty())
		{
			vertex *x = Q.front();
			//Q.pop();
			for each( vertex *v in x->neighbors)
			{
				if (s->visited == false)
				{
					s->visited = true;
					v->predecesor = x;
					Q.push(v);
				}
				
			}
		}
	}
};

Here is source.cpp

#include <iostream>
#include <string>
#include "graph2.h"
using namespace std;

int main()
{
	directedGraph graph;

	graph.addVertex("a");
	graph.addVertex("b");
	graph.addVertex("c");
	graph.addVertex("d");
	graph.addVertex("e");
	graph.addVertex("f");

	graph.addEdge("a", "b");
	graph.addEdge("a", "c");
	graph.addEdge("b", "d");
	graph.addEdge("c", "d");
	graph.addEdge("c", "e");
	graph.addEdge("e", "d");
	graph.addEdge("c", "e");
	graph.addEdge("e", "f");
	graph.testDisplay(); 

	cout << "Predecessor" << endl;
	graph.displayPredecesors();

	

	return 0;
}

[dhayden]

Breadth first search is still wrong. I think you're getting your vertices mixed up. s is the original vertex that you called it with. x is the current vertex you're exploring. v is one of x's neighbors, so I think lines 107-112 should be:

if (v->visited == false)
{
	v->visited = true;
	v->predecesor = x;
	Q.push(v);
}