Лабораторная работа №6 граф граф совокупность точек, соединенных линиями. Точки называются вершинами, или узлами



Download 225,2 Kb.
bet3/5
Sana30.03.2022
Hajmi225,2 Kb.
#517077
TuriЛабораторная работа
1   2   3   4   5
Bog'liq
Задача лабораторная работа №6

Недостатки списка смежности:

  • При работе с насыщенными графами (с большим количеством рёбер) скорости может не хватать.

  • Нет быстрого способа проверить, существует ли ребро между двумя вершинами.

  • Количество вершин графа должно быть известно заранее.

  • Для взвешенных графов приходится хранить список, элементы которого должны содержать два значащих поля, что усложняет код:

    • номер вершины, с которой соединяется текущая;

    • вес ребра.


Список рёбер
В списке рёбер в каждой строке записываются две смежные вершины и вес соединяющего их ребра (для взвешенного графа).
Количество строк в списке ребер всегда должно быть равно величине, получающейся в результате сложения ориентированных рёбер с удвоенным количеством неориентированных рёбер.

Какой способ представления графа лучше? Ответ зависит от отношения между числом вершин и числом рёбер. Число ребер может быть довольно малым (такого же порядка, как и количество вершин) или довольно большим (если граф является полным). Графы с большим числом рёбер называют плотными, с малым — разреженными. Плотные графы удобнее хранить в виде матрицы смежности, разреженные — в виде списка смежности.


Алгоритмы обхода графов


Основными алгоритмами обхода графов являются



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

  • вначале посещается корень – произвольно выбранный узел,

  • затем – все потомки данного узла,

  • после этого посещаются потомки потомков и т.д.

Вершины просматриваются в порядке возрастания их расстояния от корня.
Алгоритм прекращает свою работу после обхода всех вершин графа, либо в случае выполнения требуемого условия (например, найти кратчайший путь из вершины 1 в вершину 6).
Каждая вершина может находиться в одном из 3 состояний:

  • 0 — оранжевый – необнаруженная вершина;

  • 1 — зеленый – обнаруженная, но не посещенная вершина;

  • 2 — серый – обработанная вершина.

Фиолетовый – рассматриваемая вершина.


Задача 1.
Задан набор неповторяющихся пар (Ai,Aj), Ai, Aj принадлежат множеству А={A1, A2, ..., An}. Необходимо составить цепочку максимальной длины по правилу
(Ai,Aj)+(Aj,Ak)=(Ai,Aj,Ak).
При образовании этой цепочки любая пара может быть использована не более одного раза.

Download 225,2 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish