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. Понятие объекта, его описание и использование

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

▪ Лор-заболевания. Конспект лекций

▪ Стратегический менеджмент. Конспект лекций

▪ Информатика и информационные технологии. Шпаргалка

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

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

<< Назад

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

Рыжий ген и ускоренная эволюция 30.04.2026

Вопрос о том, как и насколько быстро меняется человеческий вид, давно занимает биологов и генетиков. Долгое время считалось, что эволюционные процессы происходят крайне медленно, однако новые данные заставляют пересматривать эти представления. Особенно интересные результаты связаны с изменением частоты редких генетических признаков, включая рыжий цвет волос. Рыжеволосость сегодня остается редкой чертой: ее носители составляют менее 2 процентов мирового населения. Однако анализ древней и современной ДНК показывает, что ген, связанный с этим признаком, за последние примерно 10 тысяч лет стал заметно более распространенным, особенно среди популяций Европы. Более того, вместе с ним исследователи фиксируют и другие изменения в генетическом профиле человека, затрагивающие внешность и физиологические особенности. Среди сопутствующих тенденций, выявленных в генетических данных, отмечается увеличение частоты светлой кожи, снижение вероятности мужского облысения, а также некоторые физиолог ...>>

Нейтринный лазер 30.04.2026

Нейтринный лазер - это гипотетическое устройство, способное управлять потоками одних из самых трудноуловимых частиц во Вселенной. Такая разработка открывает новые горизонты в изучении фундаментальных законов природы и может изменить представления о космосе. Идею нового типа излучателя представили физики из Massachusetts Institute of Technology, предложив лазер, который вместо света генерирует поток нейтрино. Эти частицы, почти не взаимодействующие с материей, настолько слабо проявляют себя, что их часто называют "частицами-призраками". Тем не менее они пронизывают все вокруг: по оценкам, триллионы нейтрино ежесекундно проходят через человеческое тело, не оставляя следа. Несмотря на их колоссальную распространенность во Вселенной, нейтрино остаются одними из наименее изученных частиц. Их крайне сложно регистрировать, а еще сложнее контролировать, поэтому традиционно их получают в крупных установках вроде ядерных реакторов или ускорителей частиц. Такие комплексы требуют огромных за ...>>

Мороженое не такое вредное, как принято считать 29.04.2026

В питании часто встречаются продукты, которые одновременно вызывают удовольствие и сомнения с точки зрения здоровья. К таким относится и мороженое: оно воспринимается как типичный десерт с высоким содержанием сахара и жиров, однако современные научные данные постепенно усложняют это привычное представление. Долгое время считалось, что мороженое не может быть частью рационального питания, однако исследования последних лет показывают более неоднозначную картину. Ученые подчеркивают, что влияние этого продукта на организм зависит не только от его сладости или калорийности, но и от состава, качества ингредиентов и общего образа жизни человека. Одни из наиболее масштабных данных были получены в рамках долгосрочных наблюдений в США, включавших проекты Nurses Health Study, Nurses Health Study II и Health Professionals Follow-Up Study. В этих исследованиях на протяжении 20-40 лет наблюдали примерно 190 тысяч взрослых участников, регулярно собирая данные об их питании, физической активнос ...>>

Случайная новость из Архива Вселенная под угрозой темной энергии 02.08.2012 Около 70% всей Вселенной составляет темная энергия, поэтому логично предположить, что именно она решает окончательную судьбу нашего мироздания. Группа китайских исследователей задалась вопросом: насколько от нее зависит продолжительность жизни Вселенной? Результат был обескураживающим. Благодаря бурному развитию современной космологии в последние три десятилетия ученые получили возможные ответы на важные вопросы: откуда появилось все вокруг и куда оно уйдет. Стандартная модель поясняет: Вселенная образовалась в результате мощного расширения и Большого взрыва. Однако для предсказания дальнейшей судьбы Вселенной необходимо тщательно проанализировать роль темной энергии в существовании мироздания. Пока точно никто не знает, что собой представляет темная энергия, поэтому теоретики могут опираться лишь на косвенные наблюдения и на расчет отношения давления к плотности темной энергии (W). Поскольку именно свойства темной энергии решают дальнейшую судьбу Вселенной, то расчет параметров загадочной субстанции может многое рассказать о нашем будущем. В частности, если W меньше, чем -1, плотность темной энергии будет расти до бесконечности и ее гравитационное отталкивание разорвет все объекты во Вселенной. Это будет "судный день" для всего мироздания, которое закончит существование в привычном нам виде. Один из наиболее интригующих вопросов: если конец света наступит, то когда? Используя метод анализа Монте-Карло с цепями Маркова, авторы подсчитали, что конец Вселенной наступит не позднее чем через 103,5 млрд лет, а с 95,4% вероятностью - через 16,7 млрд. Другими словами, в худшем случае Вселенная уже прожила около половины своей жизни, и через 16,7 млрд лет ее буквально разорвет в клочья. Наблюдения показывают, что параметр W в будущем скорее всего будет меньше, чем -1, а, значит, конец неизбежен. Если это так, появляется еще один интересный вопрос: что случится с гравитационно связанными объектами, такими как галактики и звезды? К сожалению, судьба даже крупных объектов печальна: гравитационное отталкивание темной энергии будет постоянно увеличиваться и в итоге она преодолеет все силы, удерживающие звезды и планеты вместе. Ни один объект, будь то супергалактика или небольшой астероид не избежит апокалипсиса и будет уничтожен. Например, в худшем сценарии (через 16,7 млрд. лет) Млечный Путь разорвет за 32,9 млн. лет до нового Большого взрыва. Земля вырвется за пределы Солнечной системы за 2 месяца до конца света, Луна покинет наше небо за 5 дней, а за 16 минут до гибели Вселенной наша планета взорвется.

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

▪ Ветрогенератор работает при любой погоде

▪ 64-слойные микросхемы флэш-памяти 3D NAND BiCS 64 ГБ

▪ Компьютерный корпус с пылесосом

▪ Широкополосный лазер

▪ Выявлена причина снижения яркости светодиодов

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

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

▪ раздел сайта Инструкции по эксплуатации. Подборка статей

▪ статья Правила поведения около водоемов. Основы безопасной жизнедеятельности

▪ статья Что случилось бы, если бы не было пыли? Подробный ответ

▪ статья Погрузка, транспортировка, разгрузка и хранение взрывоопасных и пожароопасных веществ и материалов. Типовая инструкция по охране труда

▪ статья Усилитель на микросхеме TDA1518, 2х11 ватт. Энциклопедия радиоэлектроники и электротехники

▪ статья Как перестроить звук в видеомагнитофоне на наш стандарт. Энциклопедия радиоэлектроники и электротехники

[an error occurred while processing this directive] Оставьте свой комментарий к этой статье:

www.diagram.com.ua
2000-2026