andrey

Путь к Файлу: /Документы для форматирования / Кошелев / Динамические структуры данных / Ориентированные графы.ppt

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   15
Пользователь:   andrey
Добавлен:   05.01.2015
Размер:   192.0 КБ
СКАЧАТЬ

Наверх страницы

Содержимое презентации:

Слайд 1

1 Ориентированные графы

Слайд 2

2 Представление графа в памяти ►Матрица смежности ►Список соседних вершин

Слайд 3

3 Представление: матрица смежности ►Представляет собой двумерный массив размером V*V, где V – количество вершин 1 2 3 4 1 0 1 0 1 2 0 0 1 0 3 1 1 0 1 4 0 0 1 0 Существует ребро из вершины 4 в вершину 3 НЕ существует ребро из вершины 4 в вершину 3 Вершины графа

Слайд 4

4 Матрица смежности «+» ► Простота реализации алгоритмов; ► Скорость обработки алгоритмов. «-» ► Не обеспечивает эффективное добавление и удаление вершин; ► Самое неэкономичное по расходу памяти

Слайд 5

5 Матрица смежности: использование ►Количество вершин не более 100; ►В случае, когда количество ребер превышает количество вершин.

Слайд 6

6 Представление: списки вершин Граф представляется списком вершин, каждая из которых содержит указатель на связанные вершины. 1 2 3 4 1  3 2  1  3 3  4 4  2

Слайд 7

7 Списки вершин «+» ► Возможность добавления элементов; ► Эффективность использования памяти. «-» ► Низкая скорость обработки;

Слайд 8

8 Списки вершин: описание type uk_v=^vetvy vetvy=record flag:boolean; data:byte; next:uk_v; end; Информационное поле узла графа Ссылочное поле для хранения списка смежных услуг Признак посещения

Слайд 9

9 Списки вершин: описание const n=4; Var graph:array[1..n] of uk_v; Количество вершин графа Массив списков вершин смежности

Слайд 10

10 Граф: формирование procedure add(ANode:uk_v); var pnew:uk_v; begin while pnew^.data<>0 do begin new(pNew); writeln('Vvedite cm ver'); readln(pnew^.data); pnew^.flag:=true; pNew^.next:=nil; ANode^.next:=pnew; ANode:=pnew; end; end; Формирование списка смежных вершин

Слайд 11

11 Граф: формирование procedure form(ANode:uk_v); var pNew,tek,Anode2:uk_v; begin Anode2:=ANode; while pNew^.data<>0 do begin new(pNew); pNew^.next_v:=nil; pnew^.flag:=true; writeln('Vvedite ver'); readln(pnew^.data); Anode^.next_v:=pnew; add(ANode2^.next); end; end; Формирование списка вершин Формирование списка смежных вершин для каждой

Слайд 12

12 Способы обхода графов ►Обход в глубину ►Обход в ширину

Слайд 13

13 Обход в глубину 1 2 3 4 1  3 2  1  3 3  4 4  2 1 3 2 4

Слайд 14

14 procedure Print(r: uk_v); var t:uk_v; begin t:=r; Write (r^.data:5); r^.Flag: =FALSE; while t^.next<>Nil do begin if t^.next^.flag then print(t^.next) t:=t^.next; end; end; Выводим и помечаем как посещенную Просматриваем все смежные вершины Просматриваем смежную Переходим на следующую смежную

Слайд 15

15 Обход в ширину 1 2 3 4 1  3 2  1  3 3  4 4  2 1 3 4 2

Слайд 16

16 Обход в ширину procedure Print(r: uk_v); var t:uk_v; begin t:=r; Write (r^.data:5); r^.Flag:=FALSE; while t^.next_v<>Nil do begin if t^.next^.flag then print(t^.next) while t^.data<> t^.next^.data do t:=t^.next_v; end; end; Выводим и помечаем как посещенную Перемещаемся к вершине с данным значением

Слайд 17

17 Вывод всех путей 1  3 2  1  3 3  4 4  2 1 2 3 4 • Сформировать списки всех путей • Вывести каждый

Слайд 18

18 Вывод всех путей Максимальное количество путей N(N-1)

Слайд 19

19 Вывод всех путей procedure Print(r: uk_v); var t:uk_v; begin {добавление элемента в список} while t^.next<>Nil do begin {проверка вхождения вершины в список, рекурсивный вызов} end; end;

Слайд 20

20 Нахождение минимального Среди полученного массива списков найти самый короткий

Слайд 21

21 Резюме ► Граф – это … ► Ориентированный граф - … ► Путь из вершины К в вершину М - … ► Цикл - … ► Способы организации графов в ОЗУ ► Матрица смежности - … ► Список связанных вершин - … ► Существуют два способа обхода графа – это …

Слайд 22

22 Резюме ►Порядок вывода элементов при обходе в глубину 1 3 2 4 5 ►Порядок вывода элементов при обходе в ширину 1 3 4 5 2 1 2 3 4 5


Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

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

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика