Форум программистов, компьютерный форум CyberForum.ru

Проверка графа на возможность достижимости одной вершины из другой - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Двумерный массив! http://www.cyberforum.ru/cpp-beginners/thread192281.html
Заполнить случайним образом двумерный массив ненулевых цисел от -100 до 100 а) определить сколько раз массив меняет знак(принимая, что массив просматривается построчно сверзу вниз, а в каждой строке - слева на право) б)расположить все элементы массива по убыванию PS убедительная просьба с коментариями что б лучше понять что где делалось))) Дублирование тем запрещено правилами форума (п....
C++ Работа со Строками Поменять местами последнее и предпоследнее слово в каждой строке http://www.cyberforum.ru/cpp-beginners/thread192275.html
C++ среда ругается на функции
когда начинаю работать с функциями при попытке компиляции среда выдает следущее сообщение :cry:
C++ помогите)
помогите позязя)
C++ Уравнение Эрмита http://www.cyberforum.ru/cpp-beginners/thread192260.html
построение сегмента с условием непрерывности второго порядка(ур-е Эрмита)
C++ Помoгиte В текстовом файле записан одномерный массив целых чисел. Разделить массив на две части (сначала элементы, какие меньшие и уровни среднему значению, и элементы, какие больше среднего значения), храня последовательность их выведения. Пример введения 1 2 3 4 5 Пример выведения 1 2 3 4 5 Входные данные. Во входном файле Input02.TXT записаны элементы массива – через «пропуск». ... подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.11.2010, 05:57     Проверка графа на возможность достижимости одной вершины из другой
Мунир, Я так понимаю что в матрице смежности, которая у нас есть уже отражен случай закрытия одной из дорог и имеются города между которыми нужно проверить связь.
Я бы сделал так:
Создаем массив int размером N (где N кол-во вершин) - будем использовать его в качестве очереди.
Создаем массив bool размером N (Для отметок уже пройденных вершин).
Далее алгоритм следующий:
Берем первую вершину (город от которого ищем путь), отмечаем ее в массив bool, и номер ее заносим в очередь.
Следующее ниже организуется в цикле, например с помощью while():
Затем берем первую вершину из очереди. По матрице смежности смотрим с какими вершинами она связана, если у этих вершин уже есть метки в массиве bool, то пропускаем их, если меток нет, то берем эти вершины, ставим им метки в массиве bool, а номера загоняем в очередь.
Теперь вопрос когда выйти из цикла. Выйти из цикла нужно в двух случаях: когда мы достигнем второй вершины (это легко проверить по массиву bool), или когда очередь опустеет.
 
Текущее время: 15:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru