Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    Сам записывает клиентов и напоминает им о визите;
    Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом
  • Поиск в ширину






    При поиске в ширину, после посещения первой вершины, посещаются все соседние с ней вершины. Потом посещаются все вершины, находящиеся на расстоянии двух ребер от начальной. При каждом новом шаге посещаются вершины, расстояние от которых до начальной на единицу больше предыдущего. Чтобы предотвратить повторное посещение вершин, необходимо вести список посещенных вершин. Для хранения временных данных, необходимых для работы алгоритма, используется очередь – упорядоченная последовательность элементов, в которой новые элементы добавляются в конец, а старые удаляются из начала.

    Таким образом, основная идея поиска в ширину заключается в том, что сначала исследуются все вершины, смежные с начальной вершиной (вершина с которой начинается обход). Эти вершины находятся на расстоянии 1 от начальной. Затем исследуются все вершины на расстоянии 2 от начальной, затем все на расстоянии 3 и т.д. Обратим внимание, что при этом для каждой вершины сразу находятся длина кратчайшего маршрута от начальной вершины.

    Алгоритм поиска в ширину

    Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная (и заносится в очередь).

    Шаг 2. Посещается первая вершина из очереди (если она не помечена как посещенная). Все ее соседние вершины заносятся в очередь. После этого она удаляется из очереди.

    Шаг 3. Повторяется шаг 2 до тех пор, пока очередь не пуста

     

    //Описание функции алгоритма поиска в ширинуvoid Breadth_First_Search(int n, int **Graph, bool *Visited, int Node){ int *List = new int[n]; //очередь int Count, Head; // указатели очереди int i; // начальная инициализация for (i = 0; i < n; i++) List[i] = 0; Count = Head = 0; // помещение в очередь вершины Node List[Count++] = Node; Visited[Node] = true; while (Head < Count) { //взятие вершины из очереди Node = List[Head++]; cout < < Node + 1 < < endl; // просмотр всех вершин, связанных с вершиной Node for (i = 0; i < n; i++) // если вершина ранее не просмотрена if (Graph[Node][i] & &! Visited[i]){ // заносим ее в очередь List[Count++] = i; Visited[i] = true; } }}

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.