Skip to content

NotBadAlgorithm/BFS

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

5 Commits
 
 
 
 
 
 
 
 

Repository files navigation

Поиск в ширину

Код основан на книге "Грокаем Алгоритмы" Адитьи Бхаргавы

Теория

Поиск в ширину (англ. breadth-first search, BFS) — один из методов обхода графа. Используется в незвешенных графах.

Использование кода

В файле input.txt описывается граф, в котором мы ищем кратчайшее расстояние между исходным узлом Вы и излом с желаемым свойством продавец. Причём кратчайшее расстояние будет таковым, если можно будет добраться до нужного узла через минимальное количество узлов посредников.

image

В данном случае Том является ближайшим человеком с нужными свойствами, но если бы, например, Боб был таким человеком, то алгоритм закончил работу на нём и даже не переходил к Тому.

После окончания работы программы выводятся имя нужного человека с его свойства или выводится фраза "Такого человека нет", если мы не смогли найти во всё графе человека с нужным свойством.

В файле input.txt сначала указывается название исходного узла - Вы, откуда начинается поиск. Потом указывается желаемое свойство у искомого человека.

Дальше следует флаг ввода заполнения графа - граф: (не важно в каком регистре) Потом в нескольких строках вводится название n-го узла и название его соседей (потомков, друзей). Например у Баба есть двое друзей:

    Боб Анудж Пегги

Потом в файле должен быть указан флаг заполнения свойств людей в графе - свойства: (не важно в каком регистре). Дальше следуют строки описывающие свойства человека. Например так можно записать свойства Алисы:

    Алиса Менеджер сноубордист

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

About

Поиск в ширину

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages