Презентация Списки (окончание). Графы. Лекция 9, 10 онлайн

На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Списки (окончание). Графы. Лекция 9, 10 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 40 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.

Презентации » Устройства и комплектующие » Списки (окончание). Графы. Лекция 9, 10

Просмотр ВСЕЙ презентации! ЖМИТЕ

Оцените презентацию от 1 до 5 баллов!

Смотреть онлайн
Скачать

Тип файла:

ppt / pptx (powerpoint)
Всего слайдов:

40 слайдов
Для класса:

1,2,3,4,5,6,7,8,9,10,11
Размер файла:

186.91 kB
Просмотров:

79
Скачиваний:

0
Автор:

неизвестен

Слайды и текст к этой презентации:

№1 слайд

Содержание слайда: списки (окончание). Графы Лекция 9, 10

№2 слайд

Содержание слайда: План лекции Очередь Реализация с помощью списка Реализация с помощью циклического буфера Графы Определения Вычисление кратчайших расстояний с помощью очереди

№3 слайд

Содержание слайда: Очередь Очередью называется линейный список, в котором все включения производятся на одном конце списка, все исключения – на другом его конце FIFO (first-in-first-out) – первый вошел, первый вышел

№4 слайд

Содержание слайда: Операции работы с очередью create(&Q) – создает очередь makeempty (&Q) – делает очередь Q пустой front (&Q) – выдает значение первого элемента очереди, не удаляя его get(&Q) – выдает значение первого элемента очереди и удаляет его из очереди put(&Q, x) – помещает в конец очереди Q новый элемент со значением x empty (&Q) -- если очередь пуста, то 1 (истина), иначе 0 (ложь) destroy(&Q) -- уничтожает очередь

№5 слайд

Содержание слайда: Реализация очереди с помощью списка struct Element { T value; struct Element * next; }; struct Queue { struct Element * front; struct Element * back; }; typedef struct Queue Queue; typedef Element * ptrElement;

№6 слайд

Содержание слайда: Create, put void create(Queue *q) { q->front = q->back = NULL; }

№7 слайд

Содержание слайда: Get, empty T get(Queue *q) { ptrElement p = q->front; T a = p->value; q->front = p->next; free(p); if (q->front == NULL) q->back = NULL; return a; } int empty(const Queue *q) { return q->front == NULL; }

№8 слайд

Содержание слайда: Реализация очереди с помощью циклического буфера struct Queue { T *value; int front; int back; int size; }; typedef struct Queue Queue; typedef T * ptrElement;

№9 слайд

Содержание слайда: Create, put void create(Queue *q, int size) { q->value = malloc(*q->value*size); q->front = q->back = 0; q->size = size; } void put(Queue *q, T a) { q->value[q->back] = a; // Как узнать, что в очереди нет места? q->back = (q->back+1) % q->size; }

№10 слайд

Содержание слайда: Get, empty T get(Queue *q) { T a = q->value[q->front]; q->front = (q->front+1) % q->size; return a; } int empty(const Queue *q) { return q->front == q->back; }

№11 слайд

Содержание слайда: Пример работы с очередью int main() { Queue Q; create(&Q, 100); put(&Q, 5); put(&Q, 7); while (!empty(Q)) { int b = get(Q); printf("%d\n", b); } destroy(&Q); return 0; }

№12 слайд

Содержание слайда: Дек (double-ended queue) очередь с двумя концами Деком называется линейный список, в котором включения и исключения производятся на обоих концах списка

№13 слайд

Содержание слайда: Графы Очередь Реализация с помощью списка Реализация с помощью циклического буфера Графы Определения Вычисление кратчайших расстояний с помощью очереди

№14 слайд

Содержание слайда: Упорядоченная пара Пусть А и В – множества Упорядоченная пара (а, b), состоящая из аА и bB, это конечное множество {a, {a, b}} Упорядоченные пары (а, b) и (с, d) равны, если а = с и b = d Почему? Чем отличается упорядоченная пара от множества {а, b}?

№15 слайд

Содержание слайда: Декартово произведение Декартовым произведением АхВ множеств A и B называется множество упорядоченных пар { (а, b) | аА и bB } Пример A = {1, 2} В = {2, 3, 4} AхB = {(1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4)}

№16 слайд

Содержание слайда: Отношения Пусть А и В —множества Отношением из А в В называется любое подмножество множества АхВ A называется областью определения отношения R В называется множеством значений отношения R Факт (а, b)R сокращенно записывается аRb Отношение {(b, а) | (а, b)  R} называется обратным к отношению R и часто обозначается через R-1.

№17 слайд

Содержание слайда: Виды отношений Пусть A—множество Отношение R называется на А рефлексивным, если аRа для всех a из А симметричным, если аRb влечет bRa для a и b из A транзитивным, если для любых а, b и с из A из аRb и bRс следует аRс Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности Отношение эквивалентности на множестве A разбивает множество A на непересекающиеся подмножества, называемые классами эквивалентности Приведите примеры каждого вида отношений

№18 слайд

Содержание слайда: Графы Графом называется пара (А, R), где А — конечное множество, а R — отношение на множестве А Элементы А называются вершинами (узлами) Элементы R называются дугами (ребрами) Если отношение R несимметричное, то граф ориентированный Если отношение R симметричное, то граф неориентированный

№19 слайд

Содержание слайда: Изображение графов на плоскости Вершины графа изображают точками Дуги графа изображают прямо- или криволинейных отрезков Пример изображения графа на плоскости A={1, 2, 3, 4} , R = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}

№20 слайд

Содержание слайда: Изображение графов на плоскости Изображения дуг графа могут пересекаться -- точки пересечения не являются вершинами Граф, который можно изобразить на плоскости без пересечений дуг, называется планарным. Пример различных изображений графа на плоскости A={1, 2, 3, 4} , R = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 1)}

№21 слайд

Содержание слайда: Дуги графа Пара (а, b)R называется дугой (ребром) графа G Дуга выходит из вершины а и входит в вершину b Вершина а предшествует вершине b, а вершина b следует за вершиной a Вершина b смежна с вершиной a

№22 слайд

Содержание слайда: Путь и цикл в графе Последовательность вершин (а0, а1, ... ,аn), n≥1, называется путем (маршрутом) длины n из вершины а0 в вершину аn, если для каждого 1≤i≤n существует дуга, выходящая из вершины аi-1 и входящая в вершину аi Если существует путь из вершины а0 в вершину аn, то говорят, что аn достижима из а0 Циклом называется путь (а0, а1, ...,аn), т.ч. а0 = аn

№23 слайд

Содержание слайда: Путь и цикл в графе A={1, 2, 3, 4} R = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)} Путь ( 1, 2, 4, 3 ) Цикл ( 1, 2, 3, 4, 1 )

№24 слайд

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

№25 слайд

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

№26 слайд

Содержание слайда: Дуга и путь в ациклическом графе Пусть (a, b) – дуга в ациклическом графе Вершина a называется прямым предком b, b называется прямым потомком a Если существует путь из a в b, то a называется предком b, b называется потомком a

№27 слайд

Содержание слайда: Матрица смежностей Пусть дан граф G = (V,E), N = |V|, M = |E| Матрица смежностей для графа G – это матрица A размера NхN, состоящая из 0 и 1, в которой A[i, j]=1 тогда и только тогда, когда есть ребро из узла i в узел j

№28 слайд

Содержание слайда: Матрица инцидентностей Матрица инцидентностей для графа G – это матрица B размера NхM, в которой

№29 слайд

Содержание слайда: Списки смежностей Списком смежностей для узла v называется список всех узлов w, смежных с v

№30 слайд

Содержание слайда: Табличное представление списков смежностей

№31 слайд

Содержание слайда: Поиск в ширину в графе Способ нумерации вершин произвольного графа (один из) Проектирование ИС и печатных плат, ... Основа большого числа алгоритмов Поиск кратчайших путей Вычисление максимального потока в графе Проверка связности Breadth-first search, BFS

№32 слайд

Содержание слайда: Алгоритм поиска в ширину Пусть дан граф G и выбрана некоторая его вершина s Поиск в ширину вычисляет для каждой вершины u два номера П[u] предшественика вершины u при поиске в ширину d[u] кратчайшее расстояние от s до u Схема алгоритма Шаг 1: d[s] = 0 Шаг n: обрабатываем все вершины на расстоянии n-1 от s Каждого соседа v вершины u с пометкой d[u] = n-1 нумеруем П[v] = u и d[v] = n

№33 слайд

Содержание слайда:

№34 слайд

Содержание слайда: Алгоритм поиска в ширину BFS (матрица смежности граф G, число вершин n, вершина s) { for (u = 0; u < n; u++) d[u] = n; // почему? d[s] = 0; put(s, Q); while (! empty(Q)) { u = get(Q); for (v = 0; v < n; v++) if (G[v][u] == 1) { // сосед u if (d[v] > d[u]+1) { d[v]= d[u]+1; put(Q, v); }} } }

№35 слайд