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 тысяч взрослых участников, регулярно собирая данные об их питании, физической активнос ...>>

Случайная новость из Архива Емкость аккумуляторов повышена в 10 раз 14.08.2013 Японская компания Shin-Etsu Chemical разработала технологию, которая позволяет в 10 повысить емкость аккумуляторов для мобильных устройств. Суть технологии заключается в замене графита в литиево-ионных аккумуляторах на кремниевый материал. Благодаря новой технологии смартфоны и планшеты смогут работать от одной зарядки до 10 дней, тогда как сейчас в режиме активной эксплуатации это лишь один-два дня. Современные гаджеты отличаются небольшим временем автономной работы, что связано с их размерами и особенностью работы, когда устройство регулярно ищет доступные беспроводные сети для подключения к интернету, регулярно получает из интернета различную информацию и т.д. Новый материал стоит дороже графита, однако, как подчеркивает Nikkei, данный прорыв избавит пользователей от необходимости заряжать смартфон каждый день или раз в два дня, поэтому цена новой технологии является не такой уж высокой. Помимо аккумуляторов для мобильных устройств, новый материал может использоваться в батареях для электромобилей, утверждают в Shin-Etsu Chemical. По словам представителей Shin-Etsu Chemical, к коммерческому производству аккумуляторов нового типа производители смогут приступить примерно через 3-4 года. Shin-Etsu Chemical - основанная в 1926 г. крупнейшая химическая компания в Японии, занимающаяся производством полимеров, изделий из кремния для полупроводниковой промышленности, фоторезистов, искусственного кварца и других материалов. С рыночной капитализацией в $28,7 млрд и годовыми продажами в $12,7 млрд компания занимает 450-ю строчку в списке 2000 крупнейших компаний мира по версии журнала Forbes. Аккумуляторные батареи - одна из наиболее актуальных сфер для работы инженеров различных компаний. Так, в апреле 2013 г. разработчики одного из американских стартапов объявили, что им удалось улучшить свойства электродов литиево-ионных батарей, что повысило их емкость на 30%.

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

▪ Чем мельче, тем прочнее

▪ Вращающиеся нейтронные звезды для проверки и калибровки атомных часов

▪ Эффективные аккумуляторы на базе магния

▪ Пленочные конденсаторы ECQUA класса X2

▪ Новая технология 3D-печати сложных объектов на основе целлюлозы

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

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

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

▪ статья Каравелла. История изобретения и производства

▪ статья Почему Землю называют голубой планетой? Подробный ответ

▪ статья Дефекты скрытой электропроводки. Справочник

▪ статья Кампешевые чернила. Простые рецепты и советы

▪ статья Пироэлектрический эффект. Энциклопедия радиоэлектроники и электротехники

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

www.diagram.com.ua
2000-2026