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.