### BSF Algorithm

An undirected graph has 24 vertices denoted by A’, B,’ C’, D’, E’, F’, G’, H’, I’, J’, K’, L’, M’, N’, P’, Q’, R’, S’, T’, U’, V’, W’, Y’, and Z’ respectively. {M’, Z’}, {M’, Y’}, {L’, W’}, {K’, V’}, {J’, U’}, {J’, T’}, {I’, S’}, {H’, R’}, {G’, Q’}, {F’, P’}, {F’, N’}, {E’, M’}, {E’, L’}, {D’, K’}, {D’, J’}, {D’, I’}, {C’, H’}, {C’, G’}, {B’, F’}, {B’, E’}, {A’, D’}, {A’, C’}, and {A’, B’} are the edges in this graph. Assume that breadth-first search does not revisit any vertex along any path. Each edge is equivalent to two operators, e.g., the operators corresponding to {A’, B’} are A’ --> B’ and B’ --> A’. How many vertices other than D’ and V’ is breadth-first search guaranteed to visit if D’ is the initial state and V’ is the goal state?
I have written the following code but I am confused about one thing. should I consider immediate neighbors of D including A,I,J and K and take into account all possibilities? let's say

from D, I,J, and K can be visited, then from I "S" is visited, from J, "T" and "U" and from "K", "V" is visited. so far {E,J,K,S,T,U} are visited in this side. Now my question is should I consider all paths through A as well? Like B and C can be visited through A, then E and F can be visited through B and so on so far. Your help is strongly appreciated.
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182`` ``````#include #include #include #include #include using namespace std; unordered_map> graph = { {'A', {'B', 'C', 'D'}}, {'B', {'A', 'F', 'E'}}, {'C', {'A', 'H', 'G'}}, {'D', {'A', 'K', 'J', 'I'}}, {'E', {'B', 'M', 'L'}}, {'F', {'B', 'P', 'N'}}, {'G', {'C', 'Q'}}, {'H', {'C', 'R'}}, {'I', {'D', 'S'}}, {'J', {'D', 'T', 'U'}}, {'K', {'D', 'V'}}, {'L', {'E', 'W'}}, {'M', {'E', 'Z', 'Y'}}, {'N', {'F'}}, {'P', {'F'}}, {'Q', {'G'}}, {'R', {'H'}}, {'S', {'I'}}, {'T', {'J'}}, {'U', {'J'}}, {'V', {'K'}}, {'W', {'L'}}, {'Y', {'M'}}, {'Z', {'M'}} }; int bfs(char start, char goal) { queue> q; unordered_map visited; q.push({ start }); visited[start] = true; while (!q.empty()) { vector path = q.front(); q.pop(); char node = path.back(); if (node == goal) { cout << "Shortest path: "; for (char vertex : path) { cout << vertex << " -> "; } cout << "\b\b\b \n"; return path.size() - 1; } for (char adjacent : graph[node]) { if (!visited[adjacent]) { visited[adjacent] = true; vector new_path = path; new_path.push_back(adjacent); q.push(new_path); } } } return -1; } int main() { char start = 'Z'; char goal = 'C'; int operators = bfs(start, goal); if (operators != -1) { cout << "Number of operators on the path found by BFS: " << operators << endl; } else { cout << "Goal state not reachable from the initial state!" << endl; } return 0; }``````
Last edited on
 `{'D', {'A', 'K', 'J', 'I'}}`

From D you can reach four vertices.
 ``1234`` ``````{'A', {'B', 'C', 'D'}}, {'K', {'V', 'D'}}, {'J', {'T', 'U', 'D'}}, {'I', {'S', 'D'}}``````

From 'A', 'K', 'J', and 'I' you can reach six new vertices.