Една задача за загрявка и обсъждане на идеята за обхождане в широчина.

Задача 1. Да се състави функция, която проверява дали даден граф е дърво, прилагайки алгоритъм за обхождане в широчина.

Още малко "подгряващи" задачи.

Задача 2. Да се състави функция, която по даден връх намира списъка от всички негови преки родители, т.е. върховете, от които върха е достижим с дъга (бащи).

Задачата да се реши и във вариант, в който се търсят всички бащи на списък от върхове. При тази задача може да се отбележи, че е възможно в случай на наличие на цикъл някой връх да се окаже родител сам на себе си.

Задача 3. Да се състави функция, която по даден списък от върхове намира списъка на всички съседи на тези върхове.

Задача 4. Да се състави функция, която намира всички "братовчеди" на даден връх в граф.

Братовчед на даден връх i ще наричаме връх ще наричаме връх, който има общ дядо с i. Дядо ще наричаме всеки баща на баща на i. Тази функция ествествено ще използва решенията на горните две задачи. Отново може да се коментира, че в случай на наличие на цикъл е възможно даден връх да се окаже баща, дядо и дори братовчед сам на себе си.

Последно модифициране: събота, 12 ноември 2011, 17:38