Содержание
- 2. Понятие графа Граф – это совокупность двух конечных множеств: множества точек и множества линий, попарно соединяющих
- 3. Основные понятия теории графов Ориентированный граф (орграф) – граф, у которого все ребра ориентированы, т.е. ребрам
- 4. Основные понятия теории графов Петлей называется ребро, соединяющее вершину саму с собой. Две вершины называются смежными,
- 5. Основные понятия теории графов Маршрутом в графе называется конечная чередующаяся последовательность смежных вершин и ребер, соединяющих
- 6. Основные понятия теории графов Замкнутая цепь называется циклом, если различны все ее вершины, за исключением концевых.
- 7. Основные понятия теории графов Вес вершины – число (действительное, целое или рациональное), поставленное в соответствие данной
- 8. Представление графа в памяти компьютера Выбор структуры данных для хранения графа в памяти компьютера имеет принципиальное
- 9. Представление графа в памяти компьютера
- 10. Представление графа в памяти компьютера Список ребер – это множество, образованное парами смежных вершин. Для его
- 11. Представление графа в памяти компьютера
- 12. Представление графа в памяти компьютера Матрица смежности – это двумерный массив размерности n x n, значения
- 13. Представление графа в памяти компьютера
- 14. Представление графа в памяти компьютера Матрица инцидентности – это двумерный массив размерности n x m, в
- 15. Представление графа в памяти компьютера
- 16. Представление графа в памяти компьютера
- 17. Поиск в графе Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа,
- 18. Поиск в графе Под обходом графов (поиском на графах) понимается процесс систематического просмотра всех ребер или
- 19. Поиск в графе При решении многих задач, использующих графы, необходимы эффективные методы регулярного обхода вершин и
- 20. Поиск в графе При поиске в глубину посещается первая вершина, затем необходимо идти вдоль ребер графа,
- 21. Поиск в графе Процесс оказывается завершенным при возвращении в начальную вершину, причем все смежные с ней
- 22. Поиск в графе Алгоритм поиска в глубину Шаг 1. Всем вершинам графа присваивается значение не посещенная.
- 23. Поиск в графе Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут
- 24. Поиск в графе
- 25. Поиск в графе //Описание функции алгоритма поиска в глубину void Depth_First_Search(int n, int **Graph, bool *Visited,
- 26. Поиск в графе for (int i = 0 ; i if (Graph[Node][i] && !Visited[i]) Depth_First_Search(n,Graph,Visited,i); }
- 27. Поиск в графе Поиск в ширину При поиске в ширину, после посещения первой вершины, посещаются все
- 28. Поиск в графе Чтобы предотвратить повторное посещение вершин, необходимо вести список посещенных вершин. Для хранения временных
- 29. Поиск в графе Таким образом, основная идея поиска в ширину заключается в том, что сначала исследуются
- 30. Поиск в графе Алгоритм поиска в ширину Шаг 1. Всем вершинам графа присваивается значение не посещенная.
- 31. Поиск в графе
- 32. Поиск в графе //Описание функции алгоритма поиска в ширину void Breadth_First_Search(int n, int **Graph, bool *Visited,
- 33. Поиск в графе // начальная инициализация for (i = 0; i List[i] = 0; Count =
- 34. Поиск в графе // помещение в очередь вершины Node List[Count++] = Node; Visited[Node] = true; while
- 35. Поиск в графе // просмотр всех вершин, связанных с вершиной Node for (i = 0 ;
- 55. .
- 99. Скачать презентацию