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

Введение

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

Некоторыми реальными примерами реализации графа являются телефонные линии или коммутационная сеть. Концепция общего друга на платформе социальных сетей, такой как LinkedIn, Facebook, Instagram и т. д., внутренне реализует граф.

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

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

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

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

Если вы хотите импортировать товар из-за рубежа в Индию, это пример нулевого графика, поскольку это две разные страны.

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

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

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

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

Например, A, B, C и D являются узлами графа, и они соединены по окружности, но поток ребер не определен. Это может быть ABCD, BCDA, DCBA и т. д.

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

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

Например, граф A содержит 4 узла A, B, C, D. Даны следующие направления:

A → B, B → C, C → D, A → C

Если я хочу пройти от А до D, путь может быть -

A → B → C → D или A → C → D

Подключенный график

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

Например, есть два графа ABCD и EFGH. Есть вершина, соединяющая узел D и узел E.

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

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

Взяв пример связного графа, если мы удалим вершину, соединяющую D и E, тогда он станет несвязным графом, имеющим две структуры графа (ABCD и EFGH).

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

Граф подпадает под категорию обычного графа, если он соответствует хотя бы одному из следующих двух условий:

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

б) Каждая вершина графа должна быть смежной.

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

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

В полном графе каждая вершина графа смежна со всеми его вершинами. Это означает, что существует ребро, соединяющее пару вершин в графе. Полный граф с n вершинами имеет nC2 ребер, и этот полный граф представляется как kn.

Например, если граф имеет 3 вершины и каждая вершина имеет хотя бы одно ребро с остальными вершинами, то это граф k3.

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

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

Ациклический график

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

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

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

Например, граф ABCD имеет четыре вершины и четыре ребра, соединенных циклическим образом, и является конечным графом.

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

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

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

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

а) Все вершины графа должны быть разделены на два различных набора вершин X и Y.

б) Все вершины множества X должны быть соединены только с вершинами множества Y некоторыми ребрами. Это означает, что вершины, присутствующие в наборе, не должны быть связаны с вершиной, присутствующей в том же наборе.

c) Оба созданных набора должны быть различными, что означает, что оба не должны иметь в себе одних и тех же вершин.

Планарный график

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

Он используется в системах вращения и комбинаторных картах.

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

Если граф не содержит петель и параллельных ребер, он называется простым графом. Например, граф с узлами ABC и ребрами A → B, B → C и C → A является простым графом.

Мультиграф

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

Псевдограф

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

Например, граф A имеет узлы ABC и ребра в виде A → B, B → C и C → A, а собственный узел из A → A является псевдографом.

График Эйлера

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

Чтобы узнать больше о графах, прочитайте эту [статью Scaler Topics] (https://www.scaler.com/topics/types-of-graphs-in-data-structure/).

Заключение

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

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

• В картах Google графики используются для определения кратчайшего расстояния с помощью алгоритмов Прима и Крускала.

• Связь между общими друзьями в Facebook является примером неориентированного графа.

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