Структура данных графа и Algorithms (Пример)
Сара Чен
Что такое граф в структуре данных?
Граф — это нелинейная структура данных, состоящая из вершин и ребер, где вершины содержат информацию или данные, а ребра работают как связующее звено между парой вершин.
Он используется для решения реальных текстовых задач, таких как поиск наилучшего маршрута к месту назначения, а также маршрута для телекоммуникаций и социальных сетей. Пользователи считаются узлом в графике, а провода — это ребра, соединяющие пользователей.
Если ребра представлены как E, а вершины представлены как V, то граф G можно записать как набор вершин и ребер, например G (V, E)
Пример графика в структуре данных
Вот простой пример структуры данных графа:
Это простой неориентированный граф (один из видов графов). Здесь набор вершин: {A, B, C,D,E,F}. Две вершины создают ребро. Например, A и B связаны ребром. Однако A и F не связаны никакими ребрами.
Графовая терминология в структуре данных
Ниже приведены некоторые важные термины, используемые в структуре данных графа:
| Срок | Описание |
|---|---|
| Вершина | Любой элемент данных называется вершиной или узлом. На изображении выше A, B, C, D и E — вершины. |
| Край (Дуга) | Соединяющие связи между двумя узлами или вершинами называются ребрами (дугами). Он имеет два конца и обозначается как (startingVertex, endVertex). |
| Ненаправленный край | Это двунаправленный край. |
| Направленный край | Это однонаправленная грань. |
| Взвешенное преимущество | Край, имеющий ценность. |
| Степень | В Graph количество ребер, соединенных с вершиной, называется степенью. |
| Инградус | Общее количество входящих ребер, соединенных с вершиной. |
| Выходящая степень | Общее количество исходящих ребер, соединенных с вершиной. |
| Автопетля | Ребро называется петлей, если две его конечные точки совпадают. |
| Смежность | Вершины называются смежными, если ребро соединено. |
Типы графов в структуре данных
Вот список наиболее распространенных типы графиков в структуре данных:
- Направленный график
- Ненаправленный граф
- Взвешенный график
- Двунаправленный граф
- Бесконечный граф
- Нулевой график
- Тривиальный граф
- Мультиграф
- Полный график
- Связанный граф
- Циклический график
- Направленный ациклический граф (DAG)
- График цикла
- Двудольный граф
- Граф Эйлера
- График Гамильтона
Применение структуры данных графа
График имеет множество вариантов использования. Существует множество алгоритмов, которые часто используют графы. Вот некоторые из применений Graph:
- Карты Google используют графики, чтобы найти пересечение двух дорог и рассчитать расстояние между двумя местами.
Например, Дейкстра, для поиска кратчайшего расстояния между источником и местом назначения. - Facebook использует Graphs, чтобы найти общего друга пользователей. Его алгоритм рассматривает каждого пользователя как узел графа.
- Для распределения ресурсов используется DAG (Direct Acyclic Graph). Он проверяет зависимость ресурсов.
- Поисковая система Google использует графики для создания рейтинга веб-сайтов.
- Устройство отображения использует структуру данных графа.
- Маршрутизатор и протокол t использует Graph для изучения пути назначения.
