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

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

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

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

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

Вот пример ориентированного графа.

• Мы можем перейти от узла A к D.
• Однако мы не можем перейти от узла D к узлу A, поскольку ребро указывает от A к D.
• Поскольку в графе нет весов, путешествие из вершины A в D будет стоить столько же, сколько путешествие из D в F.

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

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

Вот простой пример неориентированного графа.

На приведенном выше графике

• Мы можем переместиться из А в Б
• Мы также можем перейти из B в A.
• Ребра не содержат направлений.

Это пример неориентированного графа с конечным числом вершин и ребер без весов.

Взвешенный график

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

Вот пример взвешенного графика (направленного).

• От А до Б есть преимущество, а вес равен 5, значит, переход из А в Б обойдется нам в 5.
• Точка ведет в B, но в этом графе B не имеет прямого ребра над A. Поэтому мы не можем путешествовать из B в A.
• Однако если мы хотим перейти от A к F, есть несколько путей. Пути: ADF, ABF. АПД будет стоить (10+11) или 21.
• Здесь путь ABF будет стоить (5+15) или 20. Здесь мы добавляем вес каждого ребра пути.

Вот пример неориентированного графика с весами:

Здесь край имеет вес, но не имеет направления. Значит, путешествие из вершины A в D будет стоить 10 и наоборот.

Двунаправленный граф

Двунаправленные и неориентированные графы имеют общее свойство. То есть

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

Например:

• Здесь перемещение из A в D или из D в A будет стоить 10.
• В двунаправленном графе между двумя вершинами может быть два ребра.

Рассмотрим пример:

Путешествие из A в D обойдется нам в 17, а путешествие из D в A — в 12. Таким образом, мы не можем назначить два разных веса, если это неориентированный граф.

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

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

Вот пример бесконечного графика:

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

Нулевой граф содержит только узлы или вершины, но не имеет ребер. Если задан граф G = (V, E), где V — вершины, а E — ребра, он будет нулевым, если количество ребер E равно нулю.

Вот пример нулевого графика:

Тривиальный граф

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

Вот пример тривиального графика:

Мультиграф

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

Вот пример мультиграфа:

Из B в A есть два ребра. Более того, в вершине E есть петля. Приведенный выше граф представляет собой ориентированный граф без весов на ребрах.

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

Граф является полным, если каждая вершина имеет направленные или неориентированные ребра со всеми остальными вершинами.

Предположим, что общее количество вершин V и каждая вершина имеет ровно V-1 ребер. Тогда этот график будет называться полным графом. В этом типе графа каждая вершина соединена со всеми другими вершинами через ребра.

Вот пример полного графа с пятью вершинами:

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

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

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

Вот пример связанного графа:

Вот некоторое объяснение приведенного выше «примера полного графика»:

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

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

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

Вот пример циклического графика:

Здесь вершины A, B и C образуют цикл.

Внутри графа может быть несколько циклов.

Направленный ациклический граф (DAG)

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

Вот простой пример направленного ациклического графа (DAG):

График цикла

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

Вот пример графика цикла:

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

Эти виды Графики — это особые виды графов, в которых вершины назначаются двум наборам.

Двудольный граф должен следовать правилу:

• Два набора вершин должны быть различными, что означает, что все вершины должны быть разделены на две группы или множества.
• Один и тот же набор Вершины не должны образовывать ребра.

Граф Эйлера

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

Вот пример графика Эйлера:

Все вершины имеют четные степени. Вершины A, D, E и H имеют две степени. Здесь узел C имеет четыре степени, что является четным.

График Гамильтона

Граф Гамильтона — это связный граф, в котором вы можете посетить все вершины из данной вершины, не посещая один и тот же узел повторно и не используя одно и то же ребро. Этот вид связного графа известен как «граф Гамильтона». Путь, который вы посещаете, чтобы проверить, является ли данный график графом Гамильтона или нет, известен как гамильтонов путь.

Вот простой пример графика Гамильтона:

На этом изображении мы можем посетить все вершины любого узла в приведенном выше графике. Один из путей может быть АДЧБЕ. Также возможно найти цикл Гамильтона. Цикл Гамильтона начинается и заканчивается в одной и той же вершине. Итак, цикл Гамильтона будет АДЧБЕА.