График как структура данных:
Графики — одна из самых полезных и используемых структур данных в информатике, когда речь идет о моделировании реальной жизни. График очень универсален в том смысле, что вы можете отображать некоторые объекты реального мира на графике в виде узлов, а отношения между этими объектами могут быть представлены в виде ребер.
Есть две основные части графа: узлы (объекты, данные и т. д.) и ребра (соединения, связи между этими узлами).
Мы можем представить граф разными способами. Некоторыми из наиболее распространенных способов являются список ребер, список смежности и матрица смежности. В этой статье мы просто собираемся использовать представление списка смежности графа.
Итак, как мы можем представить приведенный выше граф в списке смежности? (на Питоне)
Приведенный выше график можно записать как:
Обратите внимание, что на этом графике для каждого узла n его дочерние элементы (соседи) помещены в массив. И этот массив называется списком смежности.
Далее мы смотрим, как мы можем пройти через граф.
Алгоритмы поиска
Теперь, когда мы понимаем, как представить граф, но что мы можем с ним сделать. Допустим, приведенный выше граф представляет города как узлы, а ребра представляют собой дороги, соединяющие города. А что, если нас спросят, можем ли мы поехать из одного города в другой?
Нам нужен способ обхода графа, чтобы быть уверенным, что мы можем перейти из одного города в другой. Я определил следующую функцию для решения вопроса. Давайте посмотрим поближе.
