Списки (окончание). Графы. Лекция 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

Слайд 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",...$

Описание слайда:

Пример работы с очередью 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

Описание слайда:

Метод поиска в ширину

Слайд 36

Описание слайда:

Метод поиска в ширину

Слайд 37

Описание слайда:

Метод поиска в ширину

Слайд 38

Описание слайда:

Метод поиска в ширину

Слайд 39

Описание слайда:

Метод поиска в ширину

Слайд 40

Описание слайда:

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