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

Нажмите для полного просмотра!
Списки (окончание). Графы. Лекция 9, 10, слайд №1 Списки (окончание). Графы. Лекция 9, 10, слайд №2 Списки (окончание). Графы. Лекция 9, 10, слайд №3 Списки (окончание). Графы. Лекция 9, 10, слайд №4 Списки (окончание). Графы. Лекция 9, 10, слайд №5 Списки (окончание). Графы. Лекция 9, 10, слайд №6 Списки (окончание). Графы. Лекция 9, 10, слайд №7 Списки (окончание). Графы. Лекция 9, 10, слайд №8 Списки (окончание). Графы. Лекция 9, 10, слайд №9 Списки (окончание). Графы. Лекция 9, 10, слайд №10 Списки (окончание). Графы. Лекция 9, 10, слайд №11 Списки (окончание). Графы. Лекция 9, 10, слайд №12 Списки (окончание). Графы. Лекция 9, 10, слайд №13 Списки (окончание). Графы. Лекция 9, 10, слайд №14 Списки (окончание). Графы. Лекция 9, 10, слайд №15 Списки (окончание). Графы. Лекция 9, 10, слайд №16 Списки (окончание). Графы. Лекция 9, 10, слайд №17 Списки (окончание). Графы. Лекция 9, 10, слайд №18 Списки (окончание). Графы. Лекция 9, 10, слайд №19 Списки (окончание). Графы. Лекция 9, 10, слайд №20 Списки (окончание). Графы. Лекция 9, 10, слайд №21 Списки (окончание). Графы. Лекция 9, 10, слайд №22 Списки (окончание). Графы. Лекция 9, 10, слайд №23 Списки (окончание). Графы. Лекция 9, 10, слайд №24 Списки (окончание). Графы. Лекция 9, 10, слайд №25 Списки (окончание). Графы. Лекция 9, 10, слайд №26 Списки (окончание). Графы. Лекция 9, 10, слайд №27 Списки (окончание). Графы. Лекция 9, 10, слайд №28 Списки (окончание). Графы. Лекция 9, 10, слайд №29 Списки (окончание). Графы. Лекция 9, 10, слайд №30 Списки (окончание). Графы. Лекция 9, 10, слайд №31 Списки (окончание). Графы. Лекция 9, 10, слайд №32 Списки (окончание). Графы. Лекция 9, 10, слайд №33 Списки (окончание). Графы. Лекция 9, 10, слайд №34 Списки (окончание). Графы. Лекция 9, 10, слайд №35 Списки (окончание). Графы. Лекция 9, 10, слайд №36 Списки (окончание). Графы. Лекция 9, 10, слайд №37 Списки (окончание). Графы. Лекция 9, 10, слайд №38 Списки (окончание). Графы. Лекция 9, 10, слайд №39 Списки (окончание). Графы. Лекция 9, 10, слайд №40

Содержание

Вы можете ознакомиться и скачать презентацию на тему Списки (окончание). Графы. Лекция 9, 10. Доклад-сообщение содержит 40 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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


Слайд 1


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

Слайд 2


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

Слайд 3


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

Слайд 4


Операции работы с очередью create(&Q) – создает очередь makeempty (&Q) – делает очередь Q пустой front (&Q) – выдает значение первого элемента...
Описание слайда:
Операции работы с очередью 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;...
Описание слайда:
Реализация очереди с помощью списка 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; }
Описание слайда:
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; }...
Описание слайда:
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 *...
Описание слайда:
Реализация очереди с помощью циклического буфера 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) {...
Описание слайда:
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 ==...
Описание слайда:
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",...
Описание слайда:
Пример работы с очередью 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) очередь с двумя концами Деком называется линейный список, в котором включения и исключения производятся на обоих концах...
Описание слайда:
Дек (double-ended queue) очередь с двумя концами Деком называется линейный список, в котором включения и исключения производятся на обоих концах списка

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 17


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

Слайд 18


Графы Графом называется пара (А, R), где А — конечное множество, а R — отношение на множестве А Элементы А называются вершинами (узлами) Элементы R...
Описание слайда:
Графы Графом называется пара (А, 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)R называется дугой (ребром) графа G Дуга выходит из вершины а и входит в вершину b Вершина а предшествует вершине b, а вершина b следует за вершиной a Вершина b смежна с вершиной a

Слайд 22


Путь и цикл в графе Последовательность вершин (а0, а1, ... ,аn), n≥1, называется путем (маршрутом) длины n из вершины а0 в вершину аn, если для...
Описание слайда:
Путь и цикл в графе Последовательность вершин (а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 )
Описание слайда:
Путь и цикл в графе 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, называется базовой Вершина, степень по выходу которой равна 0, называется листом (концевой вершиной)

Слайд 26


Дуга и путь в ациклическом графе Пусть (a, b) – дуга в ациклическом графе Вершина a называется прямым предком b, b называется прямым потомком a Если...
Описание слайда:
Дуга и путь в ациклическом графе Пусть (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, в...
Описание слайда:
Матрица смежностей Пусть дан граф G = (V,E), N = |V|, M = |E| Матрица смежностей для графа G – это матрица A размера NхN, состоящая из 0 и 1, в которой A[i, j]=1 тогда и только тогда, когда есть ребро из узла i в узел j

Слайд 28


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

Слайд 29


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

Слайд 30


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

Слайд 31


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

Слайд 32


Алгоритм поиска в ширину Пусть дан граф G и выбрана некоторая его вершина s Поиск в ширину вычисляет для каждой вершины u два номера П[u]...
Описание слайда:
Алгоритм поиска в ширину Пусть дан граф 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


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

Слайд 34


Алгоритм поиска в ширину BFS (матрица смежности граф G, число вершин n, вершина s) { for (u = 0; u < n; u++) d[u] = n; // почему? d[s] = 0; put(s,...
Описание слайда:
Алгоритм поиска в ширину 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


Метод поиска в ширину
Описание слайда:
Метод поиска в ширину

Слайд 36


Метод поиска в ширину
Описание слайда:
Метод поиска в ширину

Слайд 37


Метод поиска в ширину
Описание слайда:
Метод поиска в ширину

Слайд 38


Метод поиска в ширину
Описание слайда:
Метод поиска в ширину

Слайд 39


Метод поиска в ширину
Описание слайда:
Метод поиска в ширину

Слайд 40


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



Похожие презентации
Mypresentation.ru
Загрузить презентацию