So I have a lab to implement Breadth First Search and Depth First Search using an adjacency matrix. The vertices of the graph to be searched are numbered 0-(V-1), so for example a graph with 10 vertices would have vertices numbered 0-9. Each vertex is also given a value.

In the example I am going to give, the number of each vertex is equal to it's value (for example, vertex 0 has value 0, vertex 1 has value 1, etc.). I store the values of each vertex in an array, where the position is the vertex and the item in the array is it's value, so finding the value of vertex 7 would look like:

```
value = matrix[7];
```

I am supposed to write a program that finds a certain value with Breadth First Search and reports the vertex it was found at, and how many "steps" it took to find it.

My program finds the value in each test case, but the problem is that the "steps" don't match. I think the problem must be within my BFS algorithm itself, but I can't find it.

For example, I am searching the following adjacency matrix for value 7, which is at vertex 7:

```
0 1 1 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
```

There are 10 nodes, numbered 0-9, node 0 is connected to nodes 1 and 2, node 1 is connected to nodes 3 and 4, node 2 is connected to nodes 5 and 6, node 3 is connected to nodes 7 and 8, and node 4 is connected to node 9.

As mentioned "vertices" is the array of vertex values. "matrix" is the adjacency matrix. "visited" is an array of bool to keep track of whether or not a vertex has been visited.

I am "walking" the graph with a deque container, which I am required to use.

Here is my BFS:

```
steps = 1;
int cur_v = 0;
int vertexFound = 0;
bool found = false;
bool *visited = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
}
deque <int> q;
q.push_back(0);
visited[0] = true;
while (!q.empty()) {
if (found == false) {
steps++;
}
cur_v = q.front();
q.pop_front();
for (int n = 0; n < V; n++) {
if (matrix[cur_v][n] == 1) {
if (visited[n] == false) {
if (vertices[n] == search) {
vertexFound = n;
found = true;
}
visited[n] = true;
q.push_back(n);
}
}
}
}
if (found == true) {
cout << steps << endl;
}
```

The value I am searching for is "7", located at vertex 7. It is supposed to take 7 steps for me to get there, but my program says that it takes 5.

Another problem I am having is that when I give the program input that is supposed to make it search for value 8 in a graph with 8 vertices that go from values 0-7, it tells me that it found the value at vertex 0 in 9 steps.

Any help is very appreciated!