Типы графиков в структуре данных с примерами
Сара Чен
⚡ Умное резюме
Графы в структурах данных представляют собой нелинейные совокупности вершин и ребер, классифицируемые по типу структуры на семейства, такие как ориентированные, неориентированные, взвешенные, циклические, ациклические, полные, связные, двудольные, эйлеровы и гамильтоновы графы.
Граф — это нелинейная структура данных, состоящая из вершин и рёбер. Вершины содержат информацию или данные, а рёбра служат связующим звеном между парами вершин.
Графы могут быть разных типов, в зависимости от расположения узлов и ребер. Вот некоторые важные типы графов:
Направленный график
Ребра ориентированного графа снабжены стрелками, указывающими направление. Стрелка определяет, куда направлено ребро или где оно заканчивается. Вот пример ориентированного графа.
Направленный график
- Мы можем перейти от узла A к D.
- Однако мы не можем перейти от узла D к узлу A, поскольку ребро указывает от A к D.
- Поскольку в графе нет весов, путешествие из вершины A в D будет стоить столько же, сколько путешествие из D в F.
Ненаправленный граф
Неориентированный граф содержит рёбра без указателей. Это означает, что мы можем перемещаться в обратном направлении между двумя вершинами. Вот простой пример неориентированного графа.
Ненаправленный граф
На приведенном выше графике
- Мы можем переместиться из точки А в точку В.
- Мы также можем перейти из B в A.
- Ребра не содержат направлений.
Это пример неориентированного графа, имеющего конечное число вершин и ребер без весов.
Взвешенный график
Граф, в ребрах которого указаны веса или стоимости, называется взвешенным графом. Числовое значение обычно представляет собой стоимость перемещения от одной вершины к другой. Как ориентированные, так и неориентированные графы могут иметь веса на своих ребрах. Вот пример взвешенного графа (ориентированного).
Ориентированный граф с весом
- От точки А до точки В есть ребро, и его вес равен 5, что означает, что перемещение из точки А в точку В обойдется нам в 5.
- Точка А указывает на точку В, но в этом графе точка В не имеет прямого ребра над точкой А. Следовательно, мы не можем перейти из точки В в точку А.
- Однако, если мы хотим перейти из A в F, существует несколько путей. Это пути ADF и ABF. Путь ADF будет стоить (10+11) или 21.
- Здесь путь ABF будет стоить (5+15) или 20. Здесь мы суммируем вес каждого ребра в пути.
Вот пример неориентированного графа с весами:
Неориентированный граф с весом
Здесь край имеет вес, но не имеет направления. Значит, путешествие из вершины A в D будет стоить 10 и наоборот.
Двунаправленный граф
Двунаправленные и неориентированные графы обладают общим свойством. А именно:
- Как правило, неориентированный граф может иметь одно ребро между двумя вершинами.
Например:
- Здесь перемещение из A в D или из D в A будет стоить 10.
- В двунаправленном графе между двумя вершинами может быть два ребра.
Вот пример:
Двунаправленный граф
Путешествие из точки А в точку D обойдется нам в 17, а путешествие из точки D в точку А — в 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 имеет четыре степени, что является четным числом.
График Гамильтона
Гамильтонов граф — это связный граф, в котором можно пройти через все вершины из данной вершины, не возвращаясь к той же самой вершине и не используя то же самое ребро. Такой связный граф известен как «гамильтонов граф». Путь, который вы проходите, чтобы проверить, является ли данный граф гамильтоновым или нет, называется гамильтоновым путем. Вот простой пример гамильтоновского графа:
На этом изображении мы можем посетить все вершины любого узла в приведенном выше графике. Один из путей может быть АДЧБЕТакже можно найти гамильтонов цикл. Гамильтонов цикл начинается и заканчивается в одной и той же вершине. Таким образом, гамильтонов цикл будет представлять собой АДЧБЕА.
