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

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

▪ Медицинская статистика. Конспект лекций

▪ Семейное право. Конспект лекций

▪ История культуры. Шпаргалка

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

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

<< Назад

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

Дети, растущие рядом с природой, обретают крепкие кости 02.03.2026

Влияние окружающей среды на здоровье человека становится все более очевидным, особенно в детском возрасте. Новое исследование, опубликованное в журнале JAMA Network Open, показывает, что близость к природе напрямую связана с крепостью костей у детей. Ученые установили, что у детей, чьи дома окружены природными территориями в радиусе 1000 метров на 25% больше обычного, риск развития крайне низкой плотности костей снижается на 65%. Для проведения исследования были проанализированы данные более 300 детей, проживающих в городских, пригородных и сельских районах Фландрии в Бельгии. Плотность костной ткани у детей в возрасте от четырех до шести лет оценивалась с помощью ультразвуковых методов. Такой подход позволил безопасно и точно измерить состояние костей на ранних этапах формирования скелета. При анализе учитывались ключевые факторы, влияющие на рост и развитие детей: возраст, вес, рост, этническая принадлежность и уровень образования матери. На основании этих параметров исследоват ...>>

Самовосстанавливающаяся инфраструктура будущего 02.03.2026

Современные мосты и бетонные конструкции по всему миру сталкиваются с проблемой устаревания и износа. Многие сооружения, построенные до 1980-х годов, постепенно теряют свою несущую способность, что требует дорогого ремонта или полной замены. Недавние разработки ученых из Швейцарских федеральных лабораторий материаловедения и технологий (Empa) предлагают инновационное решение - систему укрепления бетонных конструкций с помощью "умной стали", способной самостоятельно устранять трещины и повреждения. В основе новой технологии лежит арматура из сплава на основе железа с эффектом памяти формы (Fe-SMA). Этот материал обладает уникальным свойством: при нагревании до 190-200 °C стержни стремятся вернуться к своей первоначальной конфигурации. В бетонной конструкции это создает внутреннее напряжение, которое затягивает трещины и выравнивает деформированные элементы, существенно повышая прочность и долговечность сооружений. Актуальность разработки объясняется критическим состоянием инфрастр ...>>

Поцелуи полезны для здоровья 01.03.2026

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

Случайная новость из Архива Выставка домашних роботов 21.11.2000 В Иокогаме (Япония) завершилась первая всемирная выставка домашних роботов "РОБОДЕКС-2000". Большинство представленных на выставке роботов не имеют сегодня практического применения и являются чем-то вроде очень дорогой игрушки. Цена некоторых роботов (например, робот, танцующий под музыку Чайковского, аквариумные роботы, танцующие собаки и роботы-футболисты), уже поступивших в продажу в Японии, достигает $20 тыс. По мнению специалистов, сегодня компьютерная индустрия и уровень развития технологий еще недостаточны для того, чтобы домашние роботы нашли массовое применение. Но уже в течение ближайших лет реальностью могут стать машины, которые самостоятельно будут убирать квартиру, мыть посуду или приглядывать за детьми в отсутствие родителей.

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

▪ Мужской и женский мозг сотрудничают по-разному

▪ Растения на рабочем столе снижают стресс

▪ Туннель затыкается огромной пробкой

▪ Мужчины склонны к ожирению чаще, чем женщины

▪ Рекорд автоматической подводной лодки

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

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

▪ раздел сайта Сварочное оборудование. Подборка статей

▪ статья Все о монтажных кадрах. Искусство видео

▪ статья Как долго длится Фауст Гете? Подробный ответ

▪ статья Орхидея. Легенды, выращивание, способы применения

▪ статья Радиолюбительские расчеты. Справочник

▪ статья Частоты телевизионных каналов, используемых в России. Энциклопедия радиоэлектроники и электротехники

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

www.diagram.com.ua
2000-2026