Граф. Структура данных.

Tree, Алгоритм, Дерево

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

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

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

Тогда весь facebook - это совокупность узлов и ребер. Это потому, что facebook использует структуру данных графа для хранения своих данных.

Точнее, граф - это структура данных (V, E), которая состоит из:

  • Коллекция вершин V.
  • Набор ребер E, представленный в виде упорядоченных пар вершин (u, v).

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

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}

Терминология графа

  • Смежность.
    Говорят, что вершина смежна с другой вершиной, если есть ребро, соединяющее их.
    Вершины 2 и 3 не являются смежными, потому что между ними нет ребра.

  • Путь.
    Последовательность ребер, которая позволяет вам перейти от вершины A к вершине B, называется путем.
    0-1, 1-2 и 0-2 являются путями от вершины 0 до вершины 2.

  • Ориентированный граф.
    Граф, в котором есть ребро (u, v) не обязательно означает, что также имеется ребро (v, u). Ребра в таком графике представлены стрелками, чтобы показать направление ребра.

Способы представления графа

Графы обычно представлены двумя способами:

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

Матрица смежности - это двумерный (2D) массив V x V вершин. Каждая строка и столбец представляют вершину.

Если значение любого элемента a[i][j] равно 1, это означает, что существует ребро, соединяющее вершину i и вершину j.

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

Поскольку это неориентированный граф, для ребра (0,2) нам также нужно отметить ребро (2,0), делая матрицу смежности симметричной относительно диагонали.

Поиск ребер (проверка, существует ли ребро между вершиной A и вершиной B), чрезвычайно быстр в представлении матрицы смежности, но мы должны зарезервировать пространство для каждой возможной связи между всеми вершинами (V x V), поэтому для этого требуется больше места.

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

Список смежности представляет собой граф в виде массива связанного списка.

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

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

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

Операции над графами

Наиболее распространенные операции над графами:

  • Проверьте, присутствует ли элемент в графе.
  • Обход графа.
  • Добавить элементы (вершины, ребра) в граф.
  • Нахождение пути от одной вершины к другой.
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
D
Aug. 16, 2019, 12:58 p.m.
Damir

C++ - Тест 003. Условия и циклы

  • Result:92points,
  • Rating points8
D
Aug. 16, 2019, 12:46 p.m.
Damir

C++ - Test 005. Structures and Classes

  • Result:75points,
  • Rating points2
u
Aug. 14, 2019, 2:55 p.m.
unrealproro

C++ - Test 005. Structures and Classes

  • Result:83points,
  • Rating points4
Last comments
D
Aug. 17, 2019, 9:04 a.m.
Damir

github ChekableTView Правой групповая смена значения при перетаскивании левой как обычно.
Aug. 16, 2019, 1:03 p.m.
Evgenij Legotskoj

Потому, что в минуте 60 секунд
Aug. 16, 2019, 12:16 p.m.
Dmitrij

а почему делитель 60000, а не 1000?
g
Aug. 14, 2019, 1:27 a.m.
grig_p

Спасибо большое. Получилось
Aug. 13, 2019, 10:43 a.m.
Evgenij Legotskoj

Самая главная проблема в том, что у вас это константные переменные, и инициализируется они один единственный раз при запуске программы. Поэтому делать динамический перевод в таком случае у …
Now discuss on the forum
Aug. 17, 2019, 1:53 p.m.
Ruslan Polupan

Не очень понятен вопрос. База одна или их несколько?
Aug. 15, 2019, 3:19 a.m.
Mihailll

Плюсы и qml отличаются, с++ логичней
Aug. 14, 2019, 8:20 a.m.
Evgenij Legotskoj

Да это не столько баги QML, сколько поведение JavaScript, который используется в нём. Из-за отсутствия строгой типизации получаем некоторые проблемы с преобразованием типов. в итоге, на первый в…
Aug. 14, 2019, 2:33 a.m.
BlinCT

Ошибка найдена) недосмотрел.
Aug. 13, 2019, 3:52 a.m.
Evgenij Legotskoj

Бери остаток от деления #include <QCoreApplication>#include <QTime>#include <QDebug>int main(int argc, char *argv[]){ QCoreApplication a(argc, argv); QTime time…
Looking for a Job?
14,000.00 руб. - 40,000.00 руб.
Разработчик Qt
Annino, Moscow Oblast, Russia
5,000.00 руб. - 15,000.00 руб.
Дизайнер
Moskovskiy, Moscow, Russia
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

For registered users on the site there is a minimum amount of advertising

EVILEG
About
Services
Join us
© EVILEG 2015-2019
Recommend hosting TIMEWEB