Вы, похоже, иногда ошибаетесь с v и не принимаете во внимание идентификацию из псевдокода.
q.pop();
g[v][0].color=black;
должен был быть после for. Кроме того, вы сделали
g[v][0].color=black
вместо
g[u][0].color=black
с вами. Опять же, та же ошибка ранее:
g[v][0].distance = g[v][0].distance+1;
, когда вы должны были написать это (с u):
g[v][0].distance = g[u][0].distance+1;
с u вместо v. Это на самом деле не имеет никакого смысла в противном случае.
Я настоятельно рекомендую прочитать логи c за BFS. https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/
Если вы действительно знаете логику c, стоящую за BFS, и только что совершили эти ошибки, вот два совета по отладке, которые помогли мне понять, что происходит неправильно:
, если ваша программа должна выводить некоторые значения, но это не так, скорее всего, будет oop. Обычно при отладке рекомендуется использовать cout на промежуточных этапах, посмотрите, соответствует ли результат ожидаемому. Вы можете сделать аналогичные вещи в случае al oop, чтобы заметить, где находится l oop и, возможно, даже почему.
1.1. И если каким-то образом, независимо от того, где вы разместили cout, вы все равно не получаете вывод, возможно, произошла ошибка сегментации (в определенных средах кодирования это скажет ошибка сегментации, иногда вы увидите, что это займет некоторое время, прежде чем сказать что-то вроде «процесс завершен, возвращено некоторое число, которое не равно 0», возможно, «процесс завершен, возвращен -243» в консоли. Ошибка сегментации - когда вы обращаетесь к некоторой памяти, которую вы не должны (один из элементов, которые вы Попытка доступа к массиву выходит за границы, или вы удалили этот элемент из списка, и вы пытаетесь получить к нему доступ.)
После того, как q.pop () была решена, вы заметил отрицательный и большой вывод (что обычно было невозможно). Это означает, что где-то произошло переполнение. Вы начали с максимального расстояния почти для всех узлов, кроме источника, переполнение имело смысл, как-то добавляя к узлам, которые имеют максимум.
Правка: о случайной генерации, как есть сейчас это не так уж случайно. Вы должны использовать генератор случайных чисел с начальным числом, таким как текущее время, чтобы каждый раз получать новое дерево.
В c ++ есть srand, и здесь вы можете увидеть быстрый пример из https://www.cplusplus.com/reference/cstdlib/srand/ о получении действительных случайных чисел из srand (простая инициализация без аргумента заставит его каждый раз выбирать одно и то же начальное число и, следовательно, давать тот же результат. Однако мы можем исправить это с получением текущего времени, так как текущее время будет всегда отличаться и использовать его как семя):
/* srand example */
#include <stdio.h> /* printf, NULL */
#include <stdlib.h> /* srand, rand */
#include <time.h> /* time */
int main ()
{
printf ("First number: %d\n", rand()%100);
srand (time(NULL));
printf ("Random number: %d\n", rand()%100);
srand (1);
printf ("Again the first number: %d\n", rand()%100);
return 0;
}