Список смежности¶

Более пространственно-экономичным способом реализации разреженного графа является использование списка смежности. В таком представлении мы храним основной список из всех вершин объекта Graph, каждый из элементов которого поддерживает перечень из связанных с ним вершин. В нашей реализации класса Vertex в качестве последнего будет использоваться словарь, где ключами станут вершины, а значениями - веса. Рисунок 4 иллюстрирует представление графа с рисунка 2 в виде списка смежности.

Рисунок 4: Представление графа в виде списка смежности.

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