24. Различные представления графа

Для реализации графа в виде списка инцидентности можно использовать следующий тип:

Type List = ^S;

S = record;

inf: Byte;

next: List;

end;

Тогда граф задается следующим образом:

Var Gr: array[1..n] of List;

Теперь обратимся к процедуре обхода графа. Это вспомогательный алгоритм, который позволяет просмотреть все вершины графа, проанализировать все информационные поля. Если рассматривать обход графа в глубину, то существуют два типа алгоритмов: рекурсивный и нерекурсивный.

На языке Pascal процедура обхода в глубину будет выглядеть следующим образом:

Procedure Obhod(gr: Graph; k: Byte);

Var g: Graph; l: List;

Begin

nov[k]:= false;

g:= gr;

While g^.inf <> k do

g:= g^.next;

l:= g^.smeg;

While l <> nil do begin

If nov[l^.inf] then Obhod(gr, l^.inf);

l:= l^.next;

End;

End;

Представление графа списком списков

Граф можно определить с помощью списка списков следующим образом:

Type List = ^Tlist;

Tlist = record

inf: Byte;

next: List;

end;

Graph = ^TGpaph;

TGpaph = record

inf: Byte;

smeg: List;

next: Graph;

end;

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

Приведем процедуру обхода графа в ширину на псевдокоде:

Procedure Obhod2(v);

Begin

queue = O;

queue <= v;

nov[v] = False;

While queue <> O do

Begin

p <= queue;

For u in spisok(p) do

If nov[u] then

Begin

nov[u]:= False;

queue <= u;

End;

End;

End;

Автор: Цветкова А.В.

<< Назад: Понятие графа. Способы представления графа

>> Вперед: Объектный тип в Pascal. Понятие объекта, его описание и использование

Рекомендуем интересные статьи раздела Конспекты лекций, шпаргалки:

▪ Нотариат. Шпаргалка

▪ Основы менеджмента. Шпаргалка

▪ Экспериментальная психология. Конспект лекций

Смотрите другие статьи раздела Конспекты лекций, шпаргалки.

Читайте и пишите полезные комментарии к этой статье.

<< Назад

Последние новости науки и техники, новинки электроники:

Большой адронный коллайдер прекращает работу 16.01.2026

Физика элементарных частиц - одна из самых передовых областей науки, где каждый эксперимент может изменить наше понимание мироздания. Центральным инструментом этих исследований является Большой адронный коллайдер (LHC), уникальный ускоритель частиц, позволяющий изучать самые фундаментальные законы природы. Недавно стало известно, что LHC временно прекращает свою работу для масштабной модернизации, которая подготовит его к новому этапу экспериментов с гораздо большей производительностью. Коллайдер, расположенный в подземном тоннеле вдоль швейцарско-французской границы, создает столкновения частиц на невероятно высоких энергиях. Именно здесь в 2012 году ученые открыли бозон Хиггса - ключевую частицу, объясняющую, почему другие элементарные частицы имеют массу. Это открытие стало одним из самых значимых событий современной физики и подтвердило предсказания Стандартной модели. Причиной временной остановки LHC стало развертывание проекта High-Luminosity LHC (HL-LHC). Модернизация позв ...>>

Робот-бармен AI Barmen 16.01.2026

Американские инженеры создали AI Barmen - робота-бармена, способного не только готовить коктейли, но и запоминать предпочтения гостей. AI Barmen представляет собой автономную систему, которую можно устанавливать практически в любых местах - от баров и ресторанов до гостиниц, аэропортов и корпоративных мероприятий. Робот сочетает механический манипулятор с интеллектуальной программой, которая подбирает напитки на основе истории заказов конкретного пользователя. Гости могут оставаться анонимными или разрешить системе запоминать их вкусы, что позволяет получать одинаково качественный персонализированный коктейль в любой точке, где установлен AI Barmen. Робот готовит широкий спектр коктейлей с высокой точностью, контролирует запасы ингредиентов и автоматически ведет учет, что снижает затраты и минимизирует ошибки. Для работы устройства достаточно стандартной розетки, подключение к воде не требуется, что делает его мобильным и удобным для эксплуатации в самых разных условиях. Систе ...>>

Стерильного нейтрино не существует 15.01.2026

В физике элементарных частиц поиск новых, пока не обнаруженных объектов играет ключевую роль в понимании устройства Вселенной. Иногда такие поиски приводят к громким открытиям, а иногда - к не менее важным отрицательным результатам, которые позволяют отбросить неверные направления. Именно к таким случаям относится недавний вывод ученых о судьбе стерильного нейтрино - одной из самых интригующих гипотетических частиц последних десятилетий. Исследователи из американской лаборатории Fermilab официально сообщили, что им не удалось найти доказательства существования стерильного нейтрино. К такому выводу пришла команда эксперимента MicroBooNE после многолетнего анализа столкновений нейтрино, которые ранее рассматривались как возможный намек на существование четвертого типа этих частиц. Предполагалось, что стерильное нейтрино взаимодействует с материей исключительно через гравитацию, что делало его крайне трудным объектом для обнаружения. В рамках современной физики нейтрино известны в т ...>>

Случайная новость из Архива Поэзия и здоровье 05.02.2005 Любопытную статистику по продолжительности жизни литераторов собрал Джеймс Кауфман из Калифорнийского университета (США). На основании 1987 дат жизни выдающихся романистов, поэтов, драматургов, авторов документальной литературы из Восточной Европы, Северной Америки, Китая и Турции Кауфман рассчитал, что средняя продолжительность жизни поэтов 62,2 года, драматургов - 63,4 года, романистов - 66 лет, документалистов - 67,9 года. Наибольший разрыв между поэтами и авторами "литературы факта" отмечен в Северной Америке: 66,2 и 72,7 года соответственно. Автор исследования считает, что жизнь поэтам сокращает их повышенная эмоциональность. Но, возможно, все дело в том, что современные поэты пишут не тем размером. Исследования немецких медиков показывают, что настоящая классическая поэзия может быть полезной для здоровья. Ученые одного из частных немецких университетов заставили 20 добровольцев маршировать в спортивном зале молча или читая наизусть строфы Гомера. Оказалось, что декламация гекзаметра способствует установлению правильного ритма дыхания и сердцебиения. Ритм гекзаметра с шестью ударными слогами на строку заставлял участников опыта дышать глубже и спокойнее, частота вдохов и выдохов снижалась с 15 до 12 в минуту, а вслед за тем ровнее становился пульс. Авторы исследования говорят, что "Одиссея" и "Илиада" не заменят лекарств, но могут служить вспомогательной терапией, дешевой и без побочных эффектов. К тому же заучивание стихов улучшает память.

Другие интересные новости:

▪ Щитовые термостаты серии 7T81 от Finder

▪ Следы гигантов

▪ Во льдах Антарктиды появилась гигантская дыра

▪ Морской закон под сомнением

▪ Робот с копытами

Лента новостей науки и техники, новинок электроники

Интересные материалы Бесплатной технической библиотеки:

▪ раздел сайта Электрику. Подборка статей

▪ статья Египетская работа. Крылатое выражение

▪ статья Что такое эсперанто? Подробный ответ

▪ статья Ночной сторож детского сада. Должностная инструкция

▪ статья Ремонт гарнитуры Nokia HS-23. Энциклопедия радиоэлектроники и электротехники

▪ статья Однопереходные транзисторы серии КТ133. Энциклопедия радиоэлектроники и электротехники

Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2026