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

Редакция Без Сменки
Честно. Понятно. С душой.

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

Рассмотрим два способа представления ориентированных и неориентированных графов (граф ориентированный, если у него заданы направления движения) 🌐

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

В данном способе заполняется матрицу размером V x V, где V- количество вершин графа:

A[i][j] = 1 — если существует ребро из i в j(в случае ориентированного графа записываем стоимость перехода из i в j
A[i][j] = 0 — ребра нет

(пример смотри на картинке)

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

В данном способе используется список D содержащий V списков. В каждом списке D[V] содержатся все вершины U, так что между V и U есть ребро.

(пример смотри на картинке)

Где вы учитесь?

Вам также будет интересно

«На дне» Максима Горького | цитаты
▪ Михаил Иванов Костылев, 54 года «Кто тебя – кроме черта – любит?» (Сатин) «Освободи меня… от мужа! Сними с меня петлю эту…» (Василиса) ▪...
Разбор стихотворения для ЕГЭ 2026 по литературе
Сделали разбор стихотворения Евгения Евтушенко «Осень», которое поможет вам в одной из сложных тем ЕГЭ 2026 по литературе. В произведении отражены...
ЗАПЯТЫЕ В ССП
Ставится: 🔸 между простыми предложениями, входящими в состав сложного предложения, ставится запятая. Настало утро, и все разошлись по домам. ...
ПРОЦЕНТ
А что такое процент? 🔸 Процент — математическое понятие, которое произошло от латинского per cent – на сотню, и означает оно «сотая доля» или «сотая...
БУЛЕВЫ ФУНКЦИИ
Основные булевые функции: 1️⃣ Тождество, эквивалентность. ▪️Обозначается: ~, ≡. ▪️Выражение истинно, если слева и справа одинаковые значения. ...
Шпаргалка по теории вероятности
Случайности не случайны... Всё решает вероятность событий! В ЕГЭ по математике целых два задания на теорию вероятностей, поэтому стоит уделить ей...

0 комментария

Авторизуйтесь, чтобы оставить комментарий.