Эффективному программисту необходимо глубокое понимание структур данных и алгоритмов. Технические собеседования часто проверяют ваши навыки решения проблем и критического мышления.

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

Что такое график и что нужно о нем знать?

Что такое график?

Граф — это нелинейная структура данных, которая имеет узлы (или вершины) с соединяющими их ребрами. Все деревья являются подтипами графов, но не все графы являются деревьями, а граф — это структура данных, из которой произошли деревья.

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

Руководство Академии Хана по представлению графиков — отличный ресурс для изучения того, как представлять график.

Существует множество различных типов графиков. Одно общее различие между

instagram viewer
направленный а также ненаправленный графики; они часто возникают в задачах кодирования и в реальных условиях.

Типы графиков

  1. Ориентированный граф: Граф, в котором все ребра имеют направление, также называется диграф.
  2. Неориентированный граф: Неориентированный граф также известен как двусторонний граф. В неориентированных графах направление ребер не имеет значения, и обход может идти в любом направлении.
  3. Взвешенный график: Взвешенный граф — это граф, узлы и ребра которого имеют связанное значение. В большинстве случаев это значение представляет стоимость исследования этого узла или ребра.
  4. Конечный граф: Граф с конечным числом узлов и ребер.
  5. Бесконечный график: Граф с бесконечным количеством узлов и ребер.
  6. Тривиальный график: Граф, который имеет только один узел и не имеет ребер.
  7. Простой график: Когда только одно ребро соединяет каждую пару узлов графа, он называется простым графом.
  8. Нулевой график: Нулевой граф — это граф, у которого нет ребер, соединяющих его узлы.
  9. Мультиграф: В мультиграфе по крайней мере пара узлов имеет более одного соединяющего их ребра. В мультиграфах нет петель.
  10. Полный график: Полный граф — это граф, в котором каждый узел соединяется с каждым другим узлом в графе. Он также известен как полный график.
  11. Псевдограф: Граф, который имеет петлю помимо других ребер графа, называется псевдографом.
  12. Обычный график: Обычный граф — это граф, в котором все узлы имеют одинаковую степень; то есть каждый узел имеет одинаковое количество соседей.
  13. Связанный граф: Связный граф — это просто любой граф, в котором любые два узла соединяются; то есть граф с хотя бы одним путем между каждыми двумя узлами графа.
  14. Отключенный график: Несвязный граф — это прямая противоположность связному графу. В несвязном графе нет ребер, соединяющих узлы графа, например, в нулевой график.
  15. Циклический график: Циклический граф — это граф, содержащий хотя бы один цикл графа (путь, который заканчивается там, где он начался).
  16. Ациклический граф: Ациклический граф — это граф, вообще не содержащий циклов. Оно может быть как направленным, так и ненаправленным.
  17. Подграф: Подграф — это производный граф. Это граф, сформированный из узлов и ребер, которые являются подмножествами другого графа.

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

Алгоритмы обхода графа

Будучи типом нелинейной структуры данных, обход графа довольно сложен. Обход графа означает прохождение и исследование каждого узла при наличии допустимого пути через ребра. Алгоритмы обхода графа в основном бывают двух типов.

  1. Поиск в ширину (BFS): Поиск в ширину — это алгоритм обхода графа, который посещает узел графа и исследует его соседей, прежде чем перейти к любому из его дочерних узлов. Хотя вы можете начать обход графа с любого выбранного узла, корневой узел обычно является предпочтительной отправной точкой.
  2. Поиск в глубину (DFS): Это второй основной алгоритм обхода графа. Он посещает узел графа и исследует его дочерние узлы или ветви, прежде чем перейти к следующему узлу, то есть сначала углубляется, а затем расширяется.

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

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

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

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

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

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

Поиск в ширину

bfs (График G, корень GraphNode) {
позволять быть новый Очередь
// помечаем корень как посещенный
 root.visited = истинный


// добавляем корень в очередь
д.enqueue(корень)
пока (q не пустой) {
позволять текущий будет q.dequeue() // удалить передний элемент в очереди
 для (соседей n тока в G) {
если (н являетсянет еще не побывал) {
// добавить в очередь, чтобы можно было исследовать и его соседей
д.enqueue(н)
 n.посетили = истинный
 }
 }
 }
}

Поиск в глубину

dfs (График G, корень GraphNode) {
// базовый вариант
если (корень нулевой) возвращаться
// помечаем корень как посещенный
 root.visited = истинный
for (соседи n корня в G)
если (н являетсянет еще побывал)
 dfs (G, п) // рекурсивный вызов
}

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

  • Двунаправленный поиск: Этот алгоритм представляет собой оптимизированный способ поиска кратчайшего пути между двумя узлами. Он использует два поиска в ширину, которые сталкиваются, если есть путь.
  • Топологическая сортировка: Это используется в ориентированные графы для сортировки узлов в нужном порядке. Вы не можете применить топологическую сортировку к неориентированным графам или графам с циклами.
  • Алгоритм Дейкстры: Это тоже тип BFS. Он также используется для поиска кратчайшего пути между двумя узлами в сети. взвешенный ориентированный граф, который может иметь циклы или нет.

Общие вопросы на собеседовании на основе графиков

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

Это лишь некоторые из многих популярных задач интервью на основе графов. Вы можете попробовать их на LeetCode, ХакерРанг, или же GeeksforGeeks.

Понимание структур данных графа и алгоритмов

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

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