Шестерёнки алгоритм (графы) кратко

Привет, сегодня поговорим про шестерёнки алгоритм графы , обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое шестерёнки алгоритм графы , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

шестеpенок пpонумеpованы от 0 до N (N<=10). Задана матрица соединений паp шестеpенoк в виде C[i,j]=1, если шестеpня с номеpом i находится в зацеплении с шестеpней j, где 1<=i

Решение

Будем обозначать вращение по часовой стрелке нулем, против единицей. Сначала припишем шестерне с заданным номером число нуль. На следующем шаге всем шестерням, сцепленным с заданной, будут приписаны числа 1 (они будут вращаться в противоположную шестерне 1 сторону). Далее всем шестерням, находящимся в зацеплении с занумерованными на предыдущем шаге, припишем значения 0 и и.т.д.

Процесс будем повторять до тех пор, пока либо на очередном шаге ни одной шестерне не будет приписано новое значение, и тогда шестерню с заданным номером удастся повернуть, и число рассмотренных шестеренок и есть искомое число пришедших в движение, либо на каком-то шаге пометка шестерни изменяется с 1 на 0 или с 0 на 1, и тогда система в движение не придет.

Значение направления поворота шестеренке будем хранить в массиве rotate. Об этом говорит сайт https://intellect.icu . Для обхода шестеренок и присвоения значений массиву rotate будем использовать поиск в ширину.

Формальное описание

Gears()
1. Создать матрицу смежности для графа.
2. Прочитать номер стартовой шестеренки.
3. Произвести поиск в ширину со стартовой вершины (пп.3.1-3.5):
   3.1. Инициализировать значения массива направлений значениями -1.
   3.2. Задать направление вращения стартовой вершины нулем.
   3.3. Добавить стартовую вершину в очередь.
   3.4. Пока очередь не пуста и не произошло замены вращения шестеренки,
        повторять пп. 3.4.1-3.4.5:
        3.4.1. Получить текущую вершину из очереди.
        3.4.2. Найти все инцедентные вершины.
        3.4.3. Если для найденной вершины не было установлено направление
               вращения, то установить вращение отличное от направления
               предыдущей шестеренки и добавить вершину в очередь.
        3.4.4. Если найденная вершина имеет такое же направление вращение,
               как и предыдущая, то считать, что произошла замена вращения
               шестеренки.
        3.4.5. Удалить вершину из очереди.
4. Если замены не произошло, то считать, что система шестеренок будет 
   вращаться и найти количество вращающихся шестеренок; 
   иначе считать, что система вращаться не будет.   

Пример графа из двух компонент связности для задачи "Шестеренки".

Если запустить любую шестеренку из первой компоненты (№0-№6), то система будет вращаться, причем шестеренки с однаковым направлением вращения обозначены одним цветом. Если запустить любую шестеренку из второй компоенты связности (№7-№11), то система вращаться не будет, так как шестеренки 8 и 9 будут иметь одинаковые направления вращения.

На этом все! Теперь вы знаете все про шестерёнки алгоритм графы , Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое шестерёнки алгоритм графы и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов