Creo que para comenzar debes pensar en como representar un grafo dentro de tu programa. Debido a que este programa no necesita el peso de los vértices de un grafo te puede bastar con algo llamado matriz de adyacencia u otra forma seria una lista de adyacencia que es algo cercano a la matriz de adyacencia pero sin embargo solo almacena valores para los nodos con adyacencia... Personalmente creo que la matriz de adyacencia es la más facil tanto de implementar como de entender.
En resumen la matriz de adyacencia es una matriz cuadrada de longitud igual al numero de nodos en donde cada uno de sus valores puede tener solo dos valores(booleano) , un valor true determina que existe adyacencia mientras que un valor false determina que no existe adyacencia, es decir, no existe conexión entre esos dos vertices.
Ejemplo de matriz de adyacencia de la imagen:
0 | 1 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 1 | 0 |
1 | 0 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 1 |
0 | 0 | 0 | 1 | 1 | 0 |
En pocas palabras la primera fila representa las conexiones o adyacencias con otros vértices a partir del vértice '1' o del primer vértice, la segunda fila representa las conexiones con otros vértices a partir del vértice '2' o del segundo vértice y así sucesivamente.
Nota. La matriz de adyacente tiene ambigüedades pensando en que se trata de un grafo no dirigido por lo cual es redundante representar la conexión de A->B y B->A .
En resumen la anterior matriz de adyacencia representa:
1. El vertice 1 tiene adyacencia con el vertice 2 y 3.
2. El vertice 2 tiene adyacencia con el vertice 1,4 y 5.
3. El vertice 3 tiene adyacencia con el vertice 1 y 5.
4. El vertice 4 tiene adyacencia con el vertice 2,5 y 6.
5. El vertice 5 tiene adyacencia con el vertice 2,3,4 y 6.
6. El vértice 6 tiene adyacencia con el vértice 4 y 5.
Es importante tomar en cuenta que en C++ los arreglos comienzan en el indice 0 por lo cual podríamos decir que la fila n representa la adyacencia del vértice n+1.
Ejemplo
Matriz_Adyacencia[ 0 ][ . . . ] representa un valor de adyacencia del vértice 1 ( 0 +1 )
A partir de lo anterior ya podrías empezar a aplicar el algoritmo debido a que ya tienes la representación del grafo, en el problema se plantea el uso de una cola la cual no es necesario que revises a detalle su implementación debido a que ya existe una clase definida en C++ la cual puedes utilizar aunque personalmente yo recomendaría ver ese tipo de temas antes de llegar al tema de grafos.