На этом шаге рассмотрим реализацию графа.
Для начала необходимо реализовать граф на программном уровне. Граф состоит из нескольких узлов. И каждый узел соединяется с соседними узлами. Как выразить отношение типа "Вы → Боб"? Вам уже известна структура данных, способная выражать отношения: хеш-таблица, которая связывает ключ со значением. В данном случае узел должен быть связан со всеми его соседями.
А вот как это записывается на Python:
graph = {}
graph["Алекса"] = ["Алиса", "Боб", "Клэр"]Обратите внимание: элемент "Алекс" ("Вы") отображается на массив. Следовательно, результатом выражения graph["Алекс"] является массив всех ваших соседей.
Граф - всего лишь набор узлов и ребер, поэтому для представления графа на Python ничего больше не потребуется. А как насчет большего графа, например такого:
Код на языке Python выглядит так:
graph = {}
graph["Алекса"] = ["Алиса", "Боб", "Клэр"]
graph["Алиса"] = ["Пэгги","Чак"]
graph["Клэр"] = ["Филипп"]
graph["Боб"] = ["Филипп","Анна"]
graph["Пэгги"] = []
graph["Чак"] = []
graph["Филипп"] = []
graph["Анна"] = []На следующем шаге рассмотрим реализацию алгоритма поиска в ширину.
