Типы графиков в структуре данных и приложениях

Введение

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

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

Изучите науку о данных, чтобы получить преимущество над конкурентами

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

Типы графиков в структурах данных

Структура данных — это практический стандарт хранения данных для всех языков, таких как структура данных графа python или структура данных графа java. Овладение всеми типами графов должно быть приоритетом для всех, кто стремится изучать структуры данных. Поскольку теория графов имеет много реальных приложений, они становятся жизненно важными в структурах данных.

Различные типы графиков в структурах данных могут быть перечислены ниже:

1. Нулевой график

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

2. Конечный граф

Если количество ребер и узлов в графе состоит из конечного числа, то такой граф называется конечным графом.

3. Бесконечный график

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

4. Простой график

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

5. Мультиграф

Если пара узлов соединена с несколькими ребрами в графе, то такой граф называется мультиграфом. Мультиграф не состоит из петель. В мультиграфе могут существовать два типа ребер. Они есть:

• Параллельные края

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

• Петля

Это ребро, исходная и конечная вершины которого совпадают.

Ознакомьтесь с нашими программами по науке о данных в США

6. Направленный граф

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

7. Неориентированный граф

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

8. Связанный граф

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

9. Отключенный график

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

10. Полный график

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

11. Циклический график

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

12. Обычный график

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

13. Двудольный граф

Чтобы граф был двудольным, он должен удовлетворять следующим критериям.

• Граф должен быть разбит на множества вершин.
• Ребра должны образовываться только между одной группой узлов с другой стороны. Это правило предотвращает соединение между двумя вершинами одного и того же набора узлов.
• Две группы не должны иметь общих вершин между собой.

Граф, удовлетворяющий всем приведенным выше правилам, следует считать двудольным графом.

14. Размеченный график

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

15. Направленный ациклический граф

Ориентированный ациклический граф — это комбинация ориентированного и ациклического графов, в которой ориентированные ребра графа не образуют никакой формы цикла. Наоборот, ориентированный циклический граф — это граф с ориентированными ребрами, образующий цикл.

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

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

1. Карты Google

В Картах Google структуры данных графа определяют и вычисляют транспортную систему. Когда дорога встречается с другой дорогой и образует перекресток, она считается узлом, а дорога между двумя такими узлами считается ребром. Таким образом, Google Maps находит кратчайший и самый быстрый путь к месту назначения, используя структуру графических данных.

2. Фейсбук

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

3. Всемирная паутина

Всемирная паутина является примером ориентированного графа. Это также основная идея системы ранжирования Google. В системе World Wide Web каждый веб-сайт и веб-приложение рассматриваются как узел или вершины, а ссылки с одного веб-сайта на другой считаются краем.

4. Операционная система

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

5. Картографическая система

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

6. Microsoft Excel

Направленные ациклические графы или DAG используются в Microsoft Excel.

7. Алгоритм Дейкстры

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

8. Рейсовые сети:

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

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

Начните свой путь в качестве специалиста по данным

Если вы хотите стать специалистом по данным и тактично обращаться с данными, используя различные графики, которые мы изучили, ознакомьтесь с обширным набором курсов по науке о данных на upGrad. Одним из самых популярных курсов является курс PG-IIITB по науке о данных , отличный курс для начинающих и начинающих специалистов по данным, чтобы начать работу!

Вот что предлагает курс.

• Карьерная поддержка на 360 градусов от отраслевых экспертов и наставников
• Практический опыт работы с отраслевыми проектами и подробные тематические исследования для оценки регулярного прогресса
• Общение с экспертами по науке о данных во всех секторах по всему миру

Вы также можете проверить все другие курсы upGrad по науке о данных .