🗊Презентация Списки (окончание). Графы. Лекция 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 (first-in-first-out) – первый вошел, первый вышел
Описание слайда:
Очередь Очередью называется линейный список, в котором все включения производятся на одном конце списка, все исключения – на другом его конце 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) -- уничтожает очередь
Описание слайда:
Операции работы с очередью 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;
Описание слайда:
Реализация очереди с помощью списка 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; } int empty(const Queue *q) { return q->front == NULL; }
Описание слайда:
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;
Описание слайда:
Реализация очереди с помощью циклического буфера 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; }
Описание слайда:
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; }
Описание слайда:
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; }
Описание слайда:
Пример работы с очередью 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) и (с, d) равны, если а = с и b = d Почему? Чем отличается упорядоченная пара от множества {а, b}?
Описание слайда:
Упорядоченная пара Пусть А и В – множества Упорядоченная пара (а, 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)}
Описание слайда:
Декартово произведение Декартовым произведением АхВ множеств 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.
Описание слайда:
Отношения Пусть А и В —множества Отношением из А в В называется любое подмножество множества АхВ 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 на непересекающиеся подмножества, называемые классами эквивалентности Приведите примеры каждого вида отношений
Описание слайда:
Виды отношений Пусть 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 называются дугами (ребрами) Если отношение R несимметричное, то граф ориентированный Если отношение R симметричное, то граф неориентированный

Слайд 19


Изображение графов на плоскости Вершины графа изображают точками Дуги графа изображают прямо- или криволинейных отрезков Пример изображения графа на плоскости A={1, 2, 3, 4} , R = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}
Описание слайда:
Изображение графов на плоскости Вершины графа изображают точками Дуги графа изображают прямо- или криволинейных отрезков Пример изображения графа на плоскости 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)}
Описание слайда:
Изображение графов на плоскости Изображения дуг графа могут пересекаться -- точки пересечения не являются вершинами Граф, который можно изобразить на плоскости без пересечений дуг, называется планарным. Пример различных изображений графа на плоскости 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
Описание слайда:
Дуги графа Пара (а, 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
Описание слайда:
Путь и цикл в графе Последовательность вершин (а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, называется базовой Вершина, степень по выходу которой равна 0, называется листом (концевой вершиной)

Слайд 26


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