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

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. Список смежности

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

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

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

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

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

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

  • Проверьте, присутствует ли элемент в графе.
  • Обход графа.
  • Добавить элементы (вершины, ребра) в граф.
  • Нахождение пути от одной вершины к другой.
Виртуальный хостинг со скидкой 10 процентов
Виртуальный хостинг со скидкой 10 процентов
EVILEG предлагает надёжный хостинг со скидкой 10% на виртуальный хостинг и 5% на VPS
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
TT
13 июня 2019 г. 19:01
Taimoor Tanweer

C++ - Тест 001. Первая программа и типы данных

  • Результат:66баллов,
  • Очки рейтинга-1
TT
13 июня 2019 г. 18:51
Taimoor Tanweer

C++ - Тест 002. Константы

  • Результат:75баллов,
  • Очки рейтинга2
ВМ
13 июня 2019 г. 12:30
Ваня Мороз

C++ - Тест 001. Первая программа и типы данных

  • Результат:100баллов,
  • Очки рейтинга10
Последние комментарии
i
17 июня 2019 г. 6:10
ingenfly

Только по осям xAxis2, уAxis2 значения начинаются с 0. Почему-то xAxis2 и xAxis не синхронизированы по данным. Ну и QCustomPlot последний.
16 июня 2019 г. 20:21
Евгений Легоцкой

Добрый день. Ну точно также добавляете ту же самую информацию на ось xAxis2, только добавляете другое форматирование customPlot->xAxis2->setDateTimeFormat("hh:mm"); если я ...
EF
14 июня 2019 г. 13:56
Egor Fomin

Спасибо за ваш ответ, у меня получилось реализовать это. Тем не менее появилась другая проблема, поэтому опять надеюсь на вашу помощь. Скажем, я уже выставил точки и они соеденены. Когда я нач...
d
13 июня 2019 г. 14:47
damix

Можно классу, который описывает точку, добавить сигнал, который подавать (emit), когда точка перемещается (переопределить mouseMoveEvent или mouseReleaseEvent). Так вот эти сигналы у каждой из...
i
13 июня 2019 г. 14:09
ingenfly

Здравствайте! Подскажите, пожалуйста: customPlot->xAxis2->setTickLabels(true); //Здесь включается отображение данных на оси xAxis2. а можно как-то продублировать информацию cus...
Сейчас обсуждают на форуме
I
19 июня 2019 г. 13:41
Intruder

Всем добрый день. При разборе XML файла наткнулся на тег вот такого плана: <TagName attribute1="value1" attribute2="value2" /> При попытке проверить на наличие такого элеме...
19 июня 2019 г. 12:55
Михаиллл

Скажите пожалуйста, как его в таком случае перемещать и удалять?
18 июня 2019 г. 19:50
Дмитрий

Большое спасибо! SDK заработал.К сожалению удалось продвинутся только на один шаг. При сборке чистого проекта NDK выдаёт следующие ошибки C:\Android\ndk-bundle/toolchains/arm-linux-andr...
18 июня 2019 г. 16:59
Михаиллл

Добрый день.В этом учебнике представлен код INSTALLED_APPS = ( ... 'rest_framework', 'snippets.apps.SnippetsConfig',) На строчке 'snippets.apps.SnippetsConf...
18 июня 2019 г. 14:24
Михаиллл

Спасибо, работает.Послушаю вашего совета.
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

EVILEG
О нас
Услуги
Присоединяйтесь к нам
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB