Need assistance on figuring out error on search traversals output.

Hi,
I am trying to implement a best first search which takes in input of points(x,y) from a test.txt file. After its traversal it should output the same points/vertices in order, but its giving me a different output for instance if the "test.txt" file contains: (0,1),(0,2),(1,2),(1,3), but what I am getting is: (0,1),(0,2),(0,2),(1,3), so I am trying to determine if I am doing the best first search correctly, this been just recently introduced but it still quite confusing on when trying to implement it. I followed its algorithm to get the code, and this what I have so far:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <stdlib.h>
#include <list>
#include <cmath>
#include <fstream>
#include <vector>


using namespace std;

class Graph {
	int numVertices;
	list<int> *adjacencyList;
	
	public:
		Graph(int numVertices);
		void addEdge(int v, int w);
		void BestFirstSearch(int start);
};

Graph::Graph(int numVertices)
{
	this->numVertices = numVertices;
	adjacencyList = new list<int>[numVertices];
}

void Graph::addEdge(int v, int w)
{
	adjacencyList[v].push_back(w);
}

void Graph::BestFirstSearch(int start)
{
	bool *visited = new bool[numVertices];
	for(int i = 0; i < numVertices; i++)
	{
		visited[i] = false;
	}
	
	list<int> queue;
	
	visited[start] = true;
	queue.push_back(start);
	list<int>::iterator i;
	
	while(!queue.empty())
	{
		start = queue.front();
		cout << start << " " << '\n';
		queue.pop_front();
		
		for(i = adjacencyList[start].begin(); i != adjacencyList[start].end(); i++)
		{
			if(!visited[*i])
			{
				visited[*i] = true;
				queue.push_back(*i);
			}
		}
			
	}
	
} 

int main() {
	
	int x, y, lines;
	float distance;
	Graph g(4); //Create 4 vertices.
	ifstream read("test.txt");
	while(read>>x>>y) {
		g.addEdge(x, y); //makes edges with point provided.
		g.BestFirstSearch(0); //start at the first node/vertex.

	}
	//lines = c1.size();	
		
	//distance = sqrt(pow(e, 2) + pow(f, 2));
	
	//cout << distance << "" << endl;
	
	return 0;
	
	
}


I also will need to compute the distance to get the total length that it followed. But at the moment I am trying to figure this out.
Last edited on
Topic archived. No new replies allowed.