имеет принципиальное
имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.
Матрица смежности - это двумерный массив размерности N*N.
A[i,j]=
Для хранения перечня ребер необходим двумерный массив R
размерности M*2. Строка массива описывает ребро.
3.2. Поиск в графе
Множество алгоритмов на графах требует просмотра вершин графа. Рассмотрим их.
3.2.1. Поиск в глубину
Идея метода. Поиск начинается с некоторой фиксированной вершины v. Рассматривается вершина u, смежная с v. Она выбирается. Процесс повторяется с вершиной u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не рассмотренных ранее (новых), то возвращаемся из вершины q к вершине, которая была до нее. В том случае, когда это вершина v, процесс просмотра закончен. Очевидно, что для
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
