Лабораторная работа №4. Структуры и алгоритмы обработки данных. Поиск в глубину в графе.
Состав работы
|
|
Работа представляет собой файл, который можно открыть в программе:
- Microsoft Word
Описание
Лабораторная работа №4. Структуры и алгоритмы обработки данных. Поиск в глубину в графе.
Постановка задачи:
Задан граф. Осуществить прохождение вершин заданного графа в соответствии с обходом этого графа согласно алгоритму «Поиск в глубину» в порядке возрастания первоначальной нумерации вершин графа.
Алгоритм прохождения вершин графа
1. Заносим в стек первую вершину.
2. Заносим в список посещенных первую вершину.
3. Выделяем визуально первую вершину.
4. Пока количество элементов в стеке больше нуля:
4.1. Текущей вершине приравниваем вершину стека.
4.2. Перебираем все вершины графа:
4.2.1. Если эта вершина имеет общее ребро с текущей и эта вершина не содержится в списке посещенных, то
4.2.1.1. Заносим эту вершину в стек.
4.2.1.2. Заносим эту вершину в список посещенных.
4.2.1.3. Выделяем визуально ребро, соединяющее текущую и эту вершину.
4.2.1.4. Выделяем визуально эту вершину.
4.3. Если у текущей вершины нет смежных вершин, то
4.3.1. Удаляем вершину стека.
Входные данные:
• vertices[] – массив вершин графа.
• edges[] – массив граней графа.
Вспомогательные данные:
• vertices – список вершин графа.
• stack – стек для промежуточного хранения вершин графа.
• visited – список посещенных вершин графа.
• node – переменная для временного хранения вершины графа.
Выходные данные:
• statusObhod – текстовое поле для вывода последовательности прохождения графа.
Постановка задачи:
Задан граф. Осуществить прохождение вершин заданного графа в соответствии с обходом этого графа согласно алгоритму «Поиск в глубину» в порядке возрастания первоначальной нумерации вершин графа.
Алгоритм прохождения вершин графа
1. Заносим в стек первую вершину.
2. Заносим в список посещенных первую вершину.
3. Выделяем визуально первую вершину.
4. Пока количество элементов в стеке больше нуля:
4.1. Текущей вершине приравниваем вершину стека.
4.2. Перебираем все вершины графа:
4.2.1. Если эта вершина имеет общее ребро с текущей и эта вершина не содержится в списке посещенных, то
4.2.1.1. Заносим эту вершину в стек.
4.2.1.2. Заносим эту вершину в список посещенных.
4.2.1.3. Выделяем визуально ребро, соединяющее текущую и эту вершину.
4.2.1.4. Выделяем визуально эту вершину.
4.3. Если у текущей вершины нет смежных вершин, то
4.3.1. Удаляем вершину стека.
Входные данные:
• vertices[] – массив вершин графа.
• edges[] – массив граней графа.
Вспомогательные данные:
• vertices – список вершин графа.
• stack – стек для промежуточного хранения вершин графа.
• visited – список посещенных вершин графа.
• node – переменная для временного хранения вершины графа.
Выходные данные:
• statusObhod – текстовое поле для вывода последовательности прохождения графа.
Дополнительная информация
2020
Похожие материалы
Структуры и алгоритмы обработки данных. Лабораторная работа №4
sibguter
: 5 июня 2018
Тема: Индексация и быстрый поиск
Цель работы: Изучение методов построения индексных массивов и быстрого поиска с использованием индексации.
Порядок выполнения работы:
1. Написать программу «Телефонный справочник», которая обрабатывает данные об абонентах телефонной станции. Каждый абонент имеет имя, адрес, телефонный номер. В программе описать массив абонентов (назовем его справочник). В справочнике должно быть не менее 10 элементов, которые заполняются либо программно, либо считываются из файла
49 руб.
Лабораторная работа №4. Структуры и алгоритмы обработки данных
tanzor
: 8 июля 2014
Цель работы: Освоить методы построения индексных массивов и быстрого поиска в массиве.
Порядок выполнения работы:
Написать программу “Телефонный справочник”, которая обрабатывает данные об абонентах телефонной станции. Каждый абонент имеет имя, адрес, телефонный номер. В программе описать массив абонентов (назовем его справочник). В справочнике должно быть не менее 20 элементов, которые заполняются либо программно, либо считываются из файла.
С помощью индексов и фильтров (номер задания выбираетс
120 руб.
Структуры и алгоритмы обработки данных. Лабораторная работа №4
piligrim-24
: 26 октября 2011
Написать программу “Телефонный справочник”, которая обрабатывает данные об абонентах телефонной станции. Каждый абонент имеет имя, адрес, телефонный номер. В программе описать массив абонентов (назовем его справочник). В справочнике должно быть не менее 20 элементов, которые заполняются либо программно, либо считываются из файла.
С помощью индексов и фильтров упорядочить справочник по имени и телефонному номеру по возрастанию.
50 руб.
Структуры и алгоритмы обработки данных. Лабораторная работа 4
jashma28
: 8 октября 2011
Тема: Индексация и быстрый поиск.
Цель работы: Освоить методы построения индексных массивов и быстрого поиска в массиве.
Порядок выполнения работы:
Написать программу “Телефонный справочник”, которая обрабатывает данные об абонентах телефонной станции. Каждый абонент имеет имя, адрес, телефонный номер. В программе описать массив абонентов (назовем его справочник). В справочнике должно быть не менее 20 элементов, которые заполняются либо программно, либо считываются из файла.
С помощью индексо
800 руб.
«Структуры и алгоритмы обработки данных» Лабораторная работа № 4
1231233
: 19 сентября 2010
Вариант № 9
Написать программу «Телефонный справочник», которая обрабатывает данные об абонентах телефонной станции. Каждый абонент имеет имя, адрес, телефонный номер. В программе описать массив абонентов (назовем его справочник). В справочнике должно быть не менее 20 элементов, которые заполняются либо программно, либо считываются из файла.
С помощью индексов и фильтров (номер задания выбирается по последней цифре шифра)
23 руб.
Структуры и алгоритмы обработки данных. Лабораторная работа №4. Вариант №4
tpogih
: 13 сентября 2014
Тема: Индексация и быстрый поиск.
Цель работы: Освоить методы построения индексных массивов и быстрого поиска в массиве.
Порядок выполнения работы:
Написать программу “Телефонный справочник”, которая обрабатывает данные об абонентах телефонной станции. Каждый абонент имеет имя, адрес, телефонный номер. В программе описать массив абонентов (назовем его справочник). В справочнике должно быть не менее 20 элементов, которые заполняются либо программно, либо считываются из файла.
С помощью индексо
45 руб.
Лабораторная работа №4. 3 семестр. Структуры и алгоритмы обработки данных
oksana
: 22 марта 2015
Вариант 1
1.Разработать процедуру построения двоичного Б-дерева.
2.Вычислить среднюю высоту двоичного Б-дерева для n=10, 50, 100, 200, 400 (n -количество вершин в дереве) и заполнить таблицу следующего вида. Проанализировать полученные результаты, сравнить их с теоретическими оценками и результатами из лабораторной работы 3.
100 руб.
Структуры и алгоритмы обработки данных (2-я часть). Лабораторная работа №4
nick0x01
: 21 июня 2014
Задание для выполнения лаб. работы №4
Тема: Построение двоичного Б-дерева.
Цель работы: Освоить построение двоичного Б-дерева.
Порядок выполнения работы:
1. Разработать процедуру построения двоичного Б-дерева.
2. Вычислить среднюю высоту двоичного Б-дерева для n=10, 50, 100, 200, 400 (n -количество вершин в дереве) и заполнить таблицу следующего вида. Проанализировать полученные результаты, сравнить их с теоретическими оценками и результатами из лабораторной работы 3.
69 руб.
Другие работы
Анатомо-физиологические особенности органов кровообращения и сердечно-сосудистой системы
alfFRED
: 31 декабря 2013
ВВЕДЕНИЕ................................................................................................ 2
Глава I. Анатомо-физиологические особенности органов кровобращения и сердечно-сосудистой системы................................................................................... 3
1.1. Врожденные пороки сердца............................................................... 5
1.2. Пороки с обогащением малого круга кровообращения.................. 7
Глава 2. Анатомо-физиологические особеннос
Экзамен по дисциплине «Представление графической информации»
1231233
: 23 января 2012
Задание:
1. Палитра в графических форматах. Структура растровых файлов
2. Подсчитать энтропию следующего сообщения:
10010011
Вопрос №1:
Палитра в графических форматах.
Палитра (карта цветов, индексов, таблица цветов) — представляет собой одномерный массив цветовых величин.
23 руб.
Средства связи с подвижными объектами. Лабораторная работа
hedgehog
: 7 апреля 2014
1. Лабораторное задание
1.1 Познакомиться с компьютерной программой “ОКАMURА” (см. приложение).
1.2 Приобрести навык расчета зоны обслуживания радиосети для определённых технических условий (задача 1 контрольной работы).
1.3 Получить экспериментально зависимость размеров и конфигурации зоны обслуживания сети подвижной радиосвязи от:
- характера рельефа местности.
- параметров передатчика базовой станции
- параметров приемника
150 руб.
Гидравлика и гидравлические машины 2009 ДВГУПС Задача 1.2.10 Вариант 8
Z24
: 25 октября 2025
Вертикальный цилиндрический резервуар для хранения нефтепродуктов диаметром D закрыт полусферической крышкой весом G и сообщается с атмосферой через трубу диаметром d (рис. 1.7). Плотность нефтепродуктов ρ, свободная поверхность размещается на высоте H от плоскости разъема. Определить количество болтов, крепящих крышку к резервуару, если один болт воспринимает усилие F.
150 руб.