Assistance with Greedy Best First Search Algorithm

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(for my test file example), 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). 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
#include <iostream>
#include <stdlib.h>
#include <list>
#include <cmath>
#include <fstream>


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 am also suppose to compute the distance between the points, but I am not sure how to add it to the greedy best first search. Any help would be appreciated.
Last edited on
Registered users can post here. Sign in or register to post.