Основы программирования. Представление графов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Основы программирования. Представление графов, слайд №1

Основы программирования. Представление графов, слайд №2

Основы программирования. Представление графов, слайд №3

Основы программирования. Представление графов, слайд №4

Основы программирования. Представление графов, слайд №5

Основы программирования. Представление графов, слайд №6

Основы программирования. Представление графов, слайд №7

Основы программирования. Представление графов, слайд №8

Основы программирования. Представление графов, слайд №9

Основы программирования. Представление графов, слайд №10

Основы программирования. Представление графов, слайд №11

Основы программирования. Представление графов, слайд №12

Основы программирования. Представление графов, слайд №13

Основы программирования. Представление графов, слайд №14

Основы программирования. Представление графов, слайд №15

Основы программирования. Представление графов, слайд №16

Основы программирования. Представление графов, слайд №17

Основы программирования. Представление графов, слайд №18

Основы программирования. Представление графов, слайд №19

Основы программирования. Представление графов, слайд №20

Основы программирования. Представление графов, слайд №21

Основы программирования. Представление графов, слайд №22

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Основы программирования. Представление графов. Доклад-сообщение содержит 22 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

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

Основы программирования Представление графов

Слайд 2

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

Графы Граф задается двумя множествами: вершин и ребер. Каждое ребро соединяет две вершины, т.е. может быть задано парой имен (номеров) вершин. Условно можно говорить, что ребро ab определяет возможность перехода из вершины a в вершину b. В неориентированном графе задание ребра ab определяет 2 возможных перехода: из a в b и из b в a. В ориентированном графе задание дуги ab определяет только переход из a в b. Обратный переход возможен если задана также дуга ba. Графы часто представляют графически: точки (вершины) соединяют отрезками линий (ребрами) или стрелками (дугами ориентированного графа).

Слайд 3

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

Графическое представление Неориентированный Ориентированный f e d f e d a b c a b c Существует несколько способов задания графа: матрица смежности определяет для всех пар вершин соединяются ли они ребрами (дугами) списки смежных вершин определяют для каждой вершины, с какими вершинами она связана матрица инцидентности определяет инцидентность всех вершин ребрам (используется очень редко) матрица весов – аналог матрицы смежности (вместо единиц и нулей задаются веса ребер массив ребер или дуг (массив пар вершин).

Слайд 4

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

Матрицы смежности Неориентированный Ориентированный f e d f e d a b c a b c a b c d e f a b c d e f a 0 1 0 0 1 1 a 0 0 0 0 1 1 b 1 0 1 0 1 1 b 1 0 0 0 1 0 c 0 1 0 0 0 0 c 0 1 0 0 0 0 d 0 0 0 0 0 0 d 0 0 0 0 0 0 e 1 1 0 0 0 0 e 0 0 0 0 0 0 f 1 1 0 0 0 0 f 0 1 0 0 0 0 Очевидно, что в программах используются не имена, а номера вершин графа.

Слайд 5

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

Списки смежных вершин Неориентированный Ориентированный f e d f e d a b c a b c a b-e-f a e-f b a-c-e-f b a-e c b c b d d e a-b e f a-b f b В отличие от матрицы смежности списки содержат только смежные вершины.

Слайд 6

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

Матрицы инцидентности Неориентированный Ориентированный f e d f e d a b c a b c a b c d e f a b c d e f ab 1 1 0 0 0 0 ba 1 0 0 0 0 0 bc 0 1 1 0 0 0 cb 0 0 1 0 0 0 ae 1 0 0 0 1 0 ae 1 0 0 0 0 0 af 1 0 0 0 0 1 af 1 0 0 0 0 0 be 0 1 0 0 1 0 be 0 1 0 0 0 0 fb 0 1 0 0 0 1 fb 0 0 0 0 0 1 В программах используются не имена, а номера вершин и ребер графа.

Слайд 7

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

Матрицы весов Неориентированный Ориентированный f e d f e d 3 6 3 3 6 3 6 2 6 2 a 4 b c a 4 b c a b c d e f a b c d e f a ∞ 4 ∞ ∞ 6 3 a ∞ ∞ ∞ ∞ 6 3 b 4 ∞ 2 ∞ 3 6 b 4 ∞ ∞ ∞ 3 ∞ c ∞ 2 ∞ ∞ ∞ ∞ c ∞ 2 ∞ ∞ ∞ ∞ d ∞ ∞ ∞ ∞ ∞ ∞ d ∞ ∞ ∞ ∞ ∞ ∞ e 6 3 ∞ ∞ ∞ ∞ e ∞ ∞ ∞ ∞ ∞ ∞ f 3 6 ∞ ∞ ∞ ∞ f ∞ 6 ∞ ∞ ∞ ∞ Бесконечные веса используются, т.к. обычно требуется найти объекты с минимальным весом (пути).

Слайд 8

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

Массивы ребер (дуг) Неориентированный Ориентированный f e d f e d a b c a b c a b b a b c c b a f a f a e a e f b f b b e b e Массив ребер удобно использовать для ввода.

Слайд 9

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

Массивы ребер (дуг) с весами Неориентированный Ориентированный f e d f e d 3 6 3 3 6 3 6 2 6 2 a 4 b c a 4 b c a b 4 b a 4 b c 2 c b 2 a f 3 a f 3 a e 6 a e 6 f b 6 f b 6 b e 3 b e 3 Списки смежных вершин взвешенного графа содержат пары «номер смежной вершины, вес ребра».

Слайд 10

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

Классы для представления графов Мы будем использовать 3 способа представления графа: матрицей смежности, списками смежных вершин и матрицей весов. Для этого мы создадим, соответственно, классы MGraph, LGraph, WGraph с набором базовых методов и будем добавлять к ним дополнительные методы, реализующие некоторые алгоритмы на графах.

Слайд 11

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

Класс MGraph Класс для представления графа с помощью матрицы смежности: class MGraph { bool **mat; // матрица смежности int vernum; // число вершин bool oriented; // true - орграф public: MGraph(int vnum, bool orient); ~MGraph(); void input_edges(); bool is_oriented() { return oriented; } int get_vernum() { return vernum; } bool is_edge(int a, int b); };

Слайд 12

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

Конструктор и деструктор MGraph MGraph::MGraph(int vnum, bool orient) { mat = new bool* [vnum]; for (int i = 0; i < vnum; i++) mat[i] = new bool[n]; vernum = vnum; oriented = orient; } MGraph::~MGraph() { for (int i = 0; i < vernum; i++) delete [] mat[i]; delete [] mat; }

Слайд 13

$Ввод ребер (дуг) для MGraph void MGraph::input_edges() { int i, j; for (i = 0; i < vernum; i++) for (j = 0; j < vernum; j++) mat[i][j] = false; while...$

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

Ввод ребер (дуг) для MGraph void MGraph::input_edges() { int i, j; for (i = 0; i < vernum; i++) for (j = 0; j < vernum; j++) mat[i][j] = false; while (true) { cin >> i >> j; if (i < 0 || i >= vernum) return; if (j < 0 || j >= vernum) return; mat[i][j] = true; if (!oriented) mat[j][i] = true; } }

Слайд 14

$Проверка существования ребра MGraph bool MGraph::is_edge(int a, int b) { if (a < 0 || a >= vernum) return false; if (b < 0 || b >= vernum) return...$

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

Проверка существования ребра MGraph bool MGraph::is_edge(int a, int b) { if (a < 0 || a >= vernum) return false; if (b < 0 || b >= vernum) return false; return mat[a][b]; }

Слайд 15

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

Класс LGraph Класс для представления графа с помощью списков смежных вершин: class LGraph { List *lst; // списки смежных вершин int vernum; // число вершин bool oriented; // true - орграф public: LGraph(int vnum, bool orient); ~LGraph(); void input_edges(); bool is_oriented() { return oriented; } int get_vernum() { return vernum; } bool is_edge(int a, int b); };

Слайд 16

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

Конструктор и деструктор LGraph LGraph::LGraph(int vnum, bool orient) { lst = new List[vnum]; vernum = vnum; oriented = orient; } LGraph::~LGraph() { delete [] lst; }

Слайд 17

$Ввод ребер (дуг) для LGraph void LGraph::input_edges() { int i, j; for (i = 0; i < vernum; i++) lst[i].clear(); while (true) { cin >> i >> j; if (i <...$

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

Ввод ребер (дуг) для LGraph void LGraph::input_edges() { int i, j; for (i = 0; i < vernum; i++) lst[i].clear(); while (true) { cin >> i >> j; if (i < 0 || i >= vernum) return; if (j < 0 || j >= vernum) return; lst[i].push_back(j); if (!oriented) lst[j].push_back(i); } }

Слайд 18

$Проверка существования ребра LGraph bool LGraph::is_edge(int a, int b) { if (a < 0 || a >= vernum) return false; if (b < 0 || b >= vernum) return...$

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

Проверка существования ребра LGraph bool LGraph::is_edge(int a, int b) { if (a < 0 || a >= vernum) return false; if (b < 0 || b >= vernum) return false; if (lst[a].find(b) >= 0) return true; return false; }

Слайд 19

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

Класс WGraph Класс для представления взвешенного графа с помощью матрицы весов: #define INF 1e30 class WGraph { double **mat; // матрица весов int vernum; // число вершин bool oriented; // true - орграф public: WGraph(int vnum, bool orient); ~WGraph(); void input_edges(); bool is_oriented() { return oriented; } int get_vernum() { return vernum; } double edge_weight(int a, int b); };

Слайд 20

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

Конструктор и деструктор WGraph WGraph::WGraph(int vnum, bool orient) { mat = new double* [vnum]; for (int i = 0; i < vnum; i++) mat[i] = new double[n]; vernum = vnum; oriented = orient; } WGraph::~WGraph() { for (int i = 0; i < vernum; i++) delete [] mat[i]; delete [] mat; }

Слайд 21

$Ввод ребер (дуг) с весами для WGraph void WGraph::input_edges() { int i, j; double w; for (i = 0; i < vernum; i++) for (j = 0; j < vernum; j++)...$

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

Ввод ребер (дуг) с весами для WGraph void WGraph::input_edges() { int i, j; double w; for (i = 0; i < vernum; i++) for (j = 0; j < vernum; j++) mat[i][j] = INF; while (true) { cin >> i >> j >> w; if (i < 0 || i >= vernum) return; if (j < 0 || j >= vernum) return; mat[i][j] = w; if (!oriented) mat[j][i] = w; } }

Слайд 22

$Получение веса ребра WGraph double WGraph::edge_weight(int a, int b) { if (a < 0 || a >= vernum) return INF; if (b < 0 || b >= vernum) return INF;...$

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

Получение веса ребра WGraph double WGraph::edge_weight(int a, int b) { if (a < 0 || a >= vernum) return INF; if (b < 0 || b >= vernum) return INF; return mat[a][b]; }