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

В этом базовом коде я покажу представление графа в виде списка смежности и дам краткий обзор алгоритмов, общих для графов.

Как представить график с помощью узлов:

Для большинства задач с графами (тех, которые не дают вам сетку/двухмерный массив) вы хотите использовать список смежности. Здесь у каждого узла есть список других узлов, к которым он подключен.

Перейдем к реализации. Для представления графа я использую карту (словарь, ассоциативный массив), где ключом является узел, а значением является список узлов, к которым он подключен. Это называется списком смежности.

В строках 6–8 вы видите, что каждый узел будет иметь список узлов, к которым он подключен.

Итак, небольшой пример. На самом деле в большинстве вопросов о графе для представления узлов используется что-то другое.

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

Вот пример:

А вот как это будет выглядеть в коде:

Для городов, из которых нет исходящих рейсов, я просто даю им пустой список.

Это оба примера невзвешенных диаграмм.

С невзвешенным графом вы обычно выполняете поиск в глубину (DFS) или поиск в ширину (BFS). Вот как будет выглядеть код для них:

Вы заметите, что для перехода от поиска в глубину к поиску в ширину мы изменили только 1 строку кода.

Если бы мы использовали наш график городов, вот как города были бы напечатаны, если бы мы начали с «Атланты» для поиска в глубину по сравнению с поиском в ширину:

Временная сложность:

DFS: O(n), где n — количество узлов в графе, потому что мы идем к каждому узлу.

BFS: O(n), где n — количество узлов в графе, потому что мы идем к каждому узлу.

Пространственная сложность:

DFS: O(n), где n — количество узлов в графе, потому что мы используем дополнительные структуры данных. Наш набор в конечном итоге будет хранить все n узлов в нашем графе. И наш стек toVisit будет хранить каждый узел не более одного раза.

BFS: O(n), где n — количество узлов в графе. Наш набор в конечном итоге будет хранить все n узлов в нашем графе. И наша очередь toVisit будет хранить каждый узел не более одного раза.

Это еще не все. Будет статья конкретно об алгоритмах работы с графами, таких как DFS, BFS и алгоритм Дейкстры, а также еще одна статья о том, как работать с графом, когда у вас есть двумерная сетка.

Представление взвешенного графика:

Иногда ваш граф будет иметь веса, что означает, что переход от одного узла к другому связан с затратами.

Вот как выглядел бы наш пример с городами, если бы мы добавили расходы:

Мы все еще можем использовать наше представление из предыдущего, но нам нужно добавить стоимость. Для этого я использую класс Pair. В нем хранится город и стоимость его достижения. Класс выглядит так:

В других языках вы, вероятно, могли бы использовать кортеж или массив со строкой и целым числом, но это то, что я обычно использую.

Вот как мы теперь будем представлять наш график с затратами:

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

На высоком уровне алгоритм Дейкстры представляет собой BFS, использующий очередь с приоритетом. В алгоритме Дейкстры вы используете приоритетную очередь, упорядоченную по тому, насколько близко узел находится к началу.

Вот как это будет выглядеть:

С помощью алгоритма Дейкстры вы можете посетить узел графа более одного раза, если к нему есть более короткий путь. Вы также можете изменить способ упорядочения приоритетной очереди, чтобы изменить способ перемещения по графику. Вот порядок посещения графа, если мы начали с Атланты:

Временная сложность и пространственная сложность:

Я все еще сомневаюсь в сложности этого алгоритма во времени и пространстве, поэтому, пожалуйста, обратитесь к ресурсу Беркли для лучшего обзора времени выполнения.

Вот и все для представления графиков! Будут и другие статьи, посвященные соответствующим темам. Я планирую написать статью специально о поиске в глубину, поиске в ширину и алгоритме Дейкстры. Мы также не рассказали, как построить путь с помощью этих алгоритмов. Кроме того, я хотел бы рассказать, когда сетка используется для представления графика.

Ресурсы:

Вот статьи, из которых я взял информацию для этого поста: