Breadth First Search on Directed Graph output problem

[thuynh97]

I am currently having a problem with my output for my BFSTraveral for a program where I take an adjacency matrix to make a directed graph.

using namespace std;

class Graph
{
private:
	vector<int> *adj;
public:
	int num_vertices;
	Graph(int num_vertices)
	{
		this->num_vertices = num_vertices;
		adj = new vector<int>[num_vertices];
	}
	void addEdge(int vertice, int adjacent)
	{
		adj[vertice].push_back(adjacent); 
	}
	void ShowGraph()
	{
		int i;
		vector<int>::iterator it;
		for (i = 1; i < this->num_vertices; i++) 
		{
			cout << i << " { ";
			for (it = this->adj[i].begin(); it != this->adj[i].end(); it++) 
			{
				cout << *it << " ";
			}
			cout << "}" << endl;
		}
	}
	void BFS(int source)
	{
		bool *visited = new bool[num_vertices];
		for (int i = 0; i < num_vertices; i++)
			visited[i] = false;

		Queue queue;

		visited[source] = true;
		queue.enqueue(source);

		vector<int>::iterator i;

		while (!queue.isEmpty()) 
		{
			source = queue.getFront();
			cout << source << " ";

			for (i = adj[source].begin(); i != adj[source].end(); i++) 
			{
				if (!visited[*i])
				{
					visited[*i] = true;
					queue.enqueue(*i);
				}
			}
			queue.dequeue();
		}

	}
};
int main()
{
	ifstream fin("input1.txt", ios::in);
	int i, j, v, size;
	Graph* matrix;

	while (fin >> i >> j >> v) //get matrix size from the last line where i always = j
	{
		if (i == j)
		{
			size = i + 1;
			matrix = new Graph(size);
		}
	}
	fin.close();
	ifstream fin2("input1.txt", ios::in);
	while (fin2 >> i >> j >> v)
	{
		if (i == j && v == 0) break;
		else
			matrix->addEdge(i, j);
	}

	matrix->ShowGraph();

	matrix->BFS(2);
        system("pause");
        return 0;
}

The file input is :
1 2 1
2 3 1
3 4 1
4 1 1
3 5 1
5 6 1
6 7 1
8 7 1
8 2 1
5 8 1
8 8 1

where column 3 tells if the graph has a directed edge connected from item in column 1 to item in column 2.

The output is supposed to be: 2 3 4 5 6 7 8
My current output is: 2 3 4 5 1 6 8 7

[mbozzi]

You are dequeuing the old vertex too late. Move line 58 to line 49 so you remove the current vertex rather than the last one adjacent to it.

Also, you're abusing new.

[thuynh97]

The output is still the same.

[mbozzi]

Yeah, my mistake - I got confused between a queue and a stack. DFS uses a stack.

The output is supposed to be: 2 3 4 5 6 7 8
If there is an edge from vertex 4 to vertex 1, then 1 should be traversed.

Notwithstanding the fact that 1 isn't traversed when it should be, simply drawing the graph indicates that the sequence 5 6 7 8 in the expected output is most certainly not breadth-order, so either you're interpreting the graph incorrectly or the expected output is wrong. Someone else should check this, too - I'm tired today.

[gunnerfunner]

I've been stumbling on this piece of the program:

vector<int> *adj;
//...
adj = new vector<int>[num_vertices];
//...
adj[vertice].push_back(adjacent);

so variable adj is a pointer to std::vector<int> that is allocated dynamically. So far so good but then what does the last statement mean? adj[vertice] is a std::vector<int> by itself as push_back() is defined in relation to it?

[mbozzi]

Is adj[vertice] a std::vector<int>?

Yeah, adj is a pointer to the first element of an array of vectors. The whole thing (adj) is the adjacency matrix.

[gunnerfunner]

thanks max, now it's clear