Graphs

Почему вас это должно волновать? Многие проблемы реального мира не представляются естественным образом в виде простой последовательности или иерархии. Рассмотрим: Города, соединенные дорогами Люди, связанные дружбой Компьютеры, подключенные через сеть Веб-страницы, связанные гиперссылками Курсы, связанные предварительными условиями Социальные сети Карты и навигационные системы Эти отношения можно представить с помощью графика. Графы — одна из наиболее важных структур данных в информатике, поскольку они позволяют нам моделировать отношения между объектами. Они являются основой таких алгоритмов, как: Поиск в ширину (BFS) Поиск в глубину (DFS) Алгоритм Дейкстры Алгоритм Беллмана-Форда Алгоритм Флойда-Уоршалла Алгоритм Прима Алгоритм Краскала Топологическая сортировка Проблема Предположим, у колледжа есть несколько кампусов: Ченнаи Бангалор Коимбатур Мадурай Диндигул Некоторые кампусы соединены дорогами: Ченнаи ─── Бангалор │ │ Коимбатур ─── Мадурай │ │ Диндигул Теперь предположим, что мы хотим ответить на такие вопросы, как: Есть ли дорога из Ченнаи в Мадурай? Какой самый короткий маршрут? Какие города связаны между собой? Что будет, если снести дорогу? Какой самый дешевый способ c