✅ Граф в структуре данных - Изучите терминологию и основные операции

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

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

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

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

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

Пример из реального мира

Лучший пример графиков в реальном мире - это Facebook. Каждый человек в Facebook является узлом и связан через ребра. A - друг B. B - друг C и так далее.

терминологической

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

1. Представление графа. Обычно граф представляется в виде пары множеств (V, E). V - это множество вершин или узлов. E - множество ребер. В приведенном выше примере
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)

2. Узел или вершина: элементы графа связаны через ребра.

3. Края: путь или линия между двумя вершинами графа.

4. Смежные узлы. Два узла называются смежными, если они соединены через ребро. В приведенном выше примере узел A смежен с узлами B, C и D, но не с узлом E.

5. Путь: Путь - это последовательность ребер между двумя узлами. По сути, это обход, начинающийся в одном узле и заканчивающийся в другом. В приведенном выше примере существует множество путей от узла A к узлу E.

Путь (A, E) = (AB, BE)
ИЛИ
Путь (A, E) = (AC, CD, DE)
ИЛИ
Путь (A, E) = (AD, DE)

6. Ненаправленный граф. Ненаправленный граф - это тот, в котором ребра не указывают конкретное направление. Края являются двунаправленными.

пример

Таким образом, в этом примере ребро AC может проходить от A до C и от C до A. Подобно всем ребрам. Путь от узла B к узлу C будет либо (BA, AC), либо (BD, DC).

7. Направленный граф. Направленный граф - это тот, в котором ребра можно перемещать только в указанном направлении.

пример

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

8. Взвешенный график. Взвешенный график - это тот, в котором ребра связаны с весом. Как правило, это стоимость пересечения края.

пример

Таким образом, в том же примере теперь ребра имеют определенный вес, связанный с ними. Существует два возможных пути между узлом А и узлом Е.
Path1 = (AB, BD, DE), Weight1 = 3 + 2 + 5 = 10
Path2 = (AC, CD, DE), Weight2 = 1 + 3 + 5 = 9
Ясно, что предпочтительнее было бы Path2, если целью является достижение узла E из узла A с минимальными затратами.

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

Вот основные операции графа, упомянутые ниже

1. Добавить / удалить Vertex

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

2. Добавить / удалить Edge

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

3. Поиск в ширину (BFS)

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

пример

Обход вышеупомянутого графа в стиле BFS будет результатом A -> B -> C -> D -> E -> F -> G. Алгоритм начинается с узла A и пересекает все смежные узлы B, C и D. Он отмечает все четыре узла как посещенные. Как только все соседние узлы A пройдены, алгоритм переходит к первому соседнему узлу A и повторяет ту же процедуру. В этом случае узел представляет собой B, а смежные узлы с B - это E и F. Затем соседние узлы с C проходят. Как только все узлы посещены, операция заканчивается.

4. Поиск в глубину (DFS)

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

пример

Обход вышеупомянутого графа в стиле BFS будет результатом A -> B -> E -> F -> C -> G -> D. Алгоритм начинается с узла A и пересекает все его дочерние узлы. Как только он встречает B, кажется, что у него есть дополнительные дочерние узлы. Таким образом, дочерние узлы B проходят перед тем, как перейти к следующему дочернему узлу A.

Реальные графические реализации

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

Вывод - график в структуре данных

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

Граф в структуре данных - Изучите терминологию и основные операции