имеет принципиальное


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


Hosted by uCoz