Введение в графики — учебные пособия по структуре данных и алгоритмам

Граф — это нелинейная структура данных, состоящая из вершин и ребер. Вершины иногда также называют узлами, а ребра — линиями или дугами, соединяющими любые два узла в графе. Более формально граф состоит из набора вершин ( V ) и набора ребер ( E ). Граф обозначается через G(E, V).

Компоненты графика

• Вершины: Вершины являются основными единицами графа. Иногда вершины также известны как вершины или узлы. Каждый узел/вершина может быть помечен или не помечен.
• Ребра: ребра рисуются или используются для соединения двух узлов графа. Это может быть упорядоченная пара узлов в ориентированном графе. Ребра могут соединять любые два узла любым возможным способом. Правил нет. Иногда ребра также известны как дуги. Каждое ребро может быть помечено/не помечено.

Типы графиков

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

9. График цикла

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

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

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

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

Направленный граф, не содержащий циклов.

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

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

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

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

Дерево против графика

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

Представление графиков

Существует два способа хранения графика:

• Матрица смежности
• Список смежности

Матрица смежности

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

Список смежности

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

Сравнение матрицы смежности и списка смежности

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

Основные операции с графиками

Ниже приведены основные операции над графом:

• Вставка узлов/ребер в граф — вставьте узел в граф.
• Удаление узлов/ребер в графе — удаление узла из графа.
• Поиск на графиках — поиск объекта на графике.
• Обход графов — обход всех узлов графа.

Использование графиков

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

Реальные приложения графа

Дополнительные ресурсы графика

• Последние статьи о графике
• Практика задач на графике
• Алгоритмы на графиках