Структура данных графа и Algorithms (Пример)
Сара Чен
⚡ Умное резюме
Графовая структура данных — это нелинейная совокупность вершин и ребер, где каждое ребро связывает пару вершин. Графы моделируют реальные сети, такие как карты, социальные связи и веб-страницы, и поддерживают множество мощных алгоритмов.
Что такое граф в структуре данных?
Граф — это нелинейная структура данных, состоящая из вершин и ребер, где вершины содержат информацию или данные, а ребра служат связующим звеном между парой вершин.
Он используется для решения реальных задач, таких как поиск оптимального маршрута к месту назначения, а также маршрутов для телекоммуникаций и социальных сетей. Пользователи рассматриваются как узлы в графе, а провода — это ребра, соединяющие пользователей.
Если ребра представлены как E, а вершины представлены как V, то граф G можно записать как набор вершин и ребер, например Г (В, Е).
Пример графика в структуре данных
Вот простой пример структуры данных типа граф:
Это простой неориентированный граф (один из видов графов). Здесь множество вершин: {A, B, C, D, E, F}. Две вершины образуют ребро. Например, A и B соединены ребром. Однако A и F не соединены никакими ребрами.
Графовая терминология в структуре данных
Ниже приведены некоторые важные термины, используемые в структуре данных графа:
| Срок | Описание |
|---|---|
| Вершина | Каждый элемент данных называется вершиной или узлом. На изображении выше вершинами обозначены A, B, C, D и E. |
| Край (Дуга) | Ребро (дуга), соединяющее две вершины, называется ребром. Оно имеет два конца и обозначается как (начальная вершина, конечная вершина). |
| Ненаправленный край | Это двунаправленный край. |
| Направленный край | Это однонаправленная грань. |
| Взвешенное преимущество | Ребро, на котором находится значение. |
| Степень | В графе количество рёбер, соединяющих вершину, называется степенью. |
| Инградус | Общее количество входящих ребер, соединенных с вершиной. |
| Выходящая степень | Общее количество исходящих ребер, соединенных с вершиной. |
| Автопетля | Ребро называется петлей, если две его конечные точки совпадают. |
| Смежность | Вершины считаются смежными, если между ними проходит ребро. |
Типы графов в структуре данных
Вот список наиболее распространенных типы графиков в структуре данных:
- Направленный график
- Ненаправленный граф
- Взвешенный график
- Двунаправленный граф
- Бесконечный граф
- Нулевой график
- Тривиальный граф
- Мультиграф
- Полный график
- Связанный граф
- Циклический график
- Направленный ациклический граф (DAG)
- График цикла
- Двудольный граф
- Граф Эйлера
- График Гамильтона
Как представить граф в структуре данных?
Граф обычно хранится в памяти с использованием одного из двух представлений. Выбор влияет на объем памяти, используемой графом, и на скорость выполнения типичных операций.
- Матрица смежности: Двумерный массив V × V, где ячейка [i][j] равна 1 (или весу ребра), если ребро существует между вершинами i и j, и 0 в противном случае. Он позволяет выполнить поиск ребер за O(1) раз, но использует пространство O(V²), что делает его наилучшим для плотных графов.
- Список смежности: Массив списков, в котором каждая вершина хранит список своих соседних вершин. Он использует пространство O(V + E) и эффективен для разреженных графов, поэтому его используют в большинстве реальных графов.
Более подробно об этом можно прочитать в представление графа в виде списка смежности и матрицы учебное пособие.
Применение структуры данных графа
Графы имеют множество применений. Существует множество алгоритмов, использующих графы. Вот некоторые из областей применения графов:
- Google Карты используют графики для определения пересечения двух дорог и вычисления расстояния между двумя точками. Например, Дейкстрадля определения кратчайшего расстояния между местом отправления и местом назначения.
- Facebook использует графы для поиска общих друзей пользователей. Его алгоритм рассматривает каждого пользователя как узел графа.
- Для распределения ресурсов используется ориентированный ациклический граф (DAG). Он проверяет зависимость ресурсов.
- Google Поисковые системы используют графы для ранжирования веб-сайтов.
- Картаping Устройство использует структуру данных типа граф.
- A Маршрутизатор и его протокол использует граф для определения пути к месту назначения.
