Понедельник, 21.09.2020, 06:42
Информатика и ИКТ
Приветствую Вас Гость | RSS
Главная Регистрация Вход
Меню сайта

Yandex_tech

Хабр-news

mail_news

Rambler

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

oszone.net

IT-N-образование

Главная » 2019 » Ноябрь » 23 » Структуры данных для хранения графов: обзор существующих и две «почти новых»
12:47
Структуры данных для хранения графов: обзор существующих и две «почти новых»

Структуры данных для хранения графов: обзор существующих и две «почти новых»

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

Итак, начнем. Но не с самого начала – думаю, что такое граф и какие они бывают (ориентированные, неориентированные, взвешенные, невзвешенные, с множественными ребрами и петлями или без них), мы все уже знаем.

Итак, поехали. Какие же варианты структур данных для «графохранения» мы имеем.
 

1. Матричные структуры данных


1.1 Матрица смежности. Матрица смежности представляет из себя матрицу, где заголовки строк и столбцов соответствуют номерам вершин графа, а само значение каждого ее элемента a(i,j) определяется наличием или отсутствием ребер между вершинами i и j (ясно-понятно, что для неориентированного графа такая матрица будет симметрична, ну или же можно договориться, что все значения мы храним лишь выше главной диагонали). Для невзвешенных графов a(i,j) можно задать количеством ребер из i в j (если нет такого ребра, то a(i,j)= 0), а для взвешенных также – весом (суммарным весом) упомянутых ребер.

Просмотров: 114 | Добавил: niko | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Календарь
«  Ноябрь 2019  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
252627282930

Форма входа

nixp.ru

OpenNet

Новые программы

SLO.ru

Погода
Яндекс.Погода

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Архив записей

    Copyright MyCorp © 2020