Руководство по структуре данных графа

Руководство по структуре данных графа

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





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



СДЕЛАТЬ ВИДЕО ДНЯ

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





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

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

Визуальное представление графика

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



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

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



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

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