Курсы по программированию

Формула программиста
основатель — Волосатов Евгений Витольдович

Коллекция графа

Мы рассмотрим основные коллекции в языке C#.
Поэкспериментируем с ними, сравним их быстродействие.
Далее, познакомимся с теорией графов. Создадим класс
для представления графа в памяти компьютера.
Сделаем визуальное отображения графа и
составим алгоритмы поиска вширь и глубь,
с использованием коллекций Стек и Очередь.




Хочу купить!

Купить в рассрочку за мегахеши

Цена: 800 p.


Список уроков | фото | видео

# Название видеоурока Решило Рейтинг Доступ
1 ArrayList 00:12:16 41 чел. ★ 5 Done
  На этом уроке мы обсудим план занятий,
вспомни былые времена голых массивов,
и выясним, зачем же нужны коллекции.
Начнём знакомство с самой простой
коллекции ArrayList и немного
поэкспериментируем с ней.

Отчёт отправил: 6861. Den Andreevich Выполнено за 30 мин. [Показать отчёт]
Научился: Формировать коллекции, применять различные встроенные методы по ним. Узнал, что по-умолчанию коллекция рассчитана на 4 элемента .  
Сложности: Вникать в нюансы применения строенных методов ArrayList . 
Комментарии: Поигрался с методами Insert - добавление элемента в заданную позицию, Clone - копирование эл-ов одной коллекции в другую, Capacity - отображение текущей ёмкости коллекции и TrimToSize - "обрезание" текущей ёмкости до общего кол-ва добавленных эл-ов . 
2 List 00:12:57 41 чел. ★ 5 Done
  На этом уроке мы поработаем с типизированной коллекцией List.
Обсудим её преимущества, по сравнению с ArrayList,
добавим несколько элементов, отсортируем их и даже найдём их сумму.
Перебор элементов мы организуем двумя разными способами -
через итератор и обычным foreach().
Отчёт отправил: 6861. Den Andreevich Выполнено за 30 мин. [Показать отчёт]
Научился: Использовать типизированные коллекции, не позволяющие вносить данные разных типов. Узнал, что типизированные коллекции хранят данные, согласно их значению. Применению Enumerator-а для прохождения по всем элементам списка. Экспериментам со встроенными методами типизированных коллекций : Sort() - сортировка элементов в порядке возрастания , Sum() - общая сумма элементов , ForEach() - выполнение заданной операции для каждого элемента списка, Max/Min - нахождение соответственно максимального и минимального значений в списке.  
Сложности: Ничего. 
Комментарии: Урок понравился. Идём дальше ) . 
3 Array vs List 00:11:04 40 чел. ★ 5 Done
  На этом уроке мы сравним эффективность использования
ArrayList, List<> и простого массива.
Победителем окажется типизированная коллекция List<>.
Очень интеренсо сравнивать эффективность,
нам в этом поможет флагманский класс Stopwatch.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 30 мин. [Показать отчёт]
Научился: Познакомился с типизированной коллекцией List<>, классом ArrayList с динамически изменяемым размером. Сравнил эффективность использования вышеуказанных типов с разным количеством и типом аргументов.  
Сложности: Заняло время добавление своих операций. В итоге ограничился добавлением строкового и булевого типов данных с фиксированием времени их обработки. 
Комментарии: Урок понравился. Как всегда интересно и познавательно . 
4 ListDictionary 00:15:19 40 чел. ★ 5 Done
  На этом уроке мы начнём рассматривать три класса,
которые похожи по функциональности, но очень сильно отличаются
по реализации, это: ListDictionary, Hashtable, HybridDictionary.
Эти коллекции хранят пару значений: ключ - значение.
Они нетипизированные и работают с объектами.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 00 мин. [Показать отчёт]
Научился: Ознакомился с классом ListDictionary, отсутствием его привязки к типам хранимых эл-ов, поэкспериментировал с различными его методами.  
Сложности: Сложностей не было. 
Комментарии: Получился довольно лёгкий и интересный урок. 
5 Hashtable 00:11:56 39 чел. ★ 4.9 Done
  На этом уроке мы поработаем с Hashtable - каким именно
образом в неё складываются значения и почему она будет
работать, даже если хеш-функция вернёт одинаковые значения.
Также мы увидим, что порядок элементов путается,
а сами значения хранятся в очень хитром виде.
В конце урока мы сделаем всё то же самое с гибридным классом.
Самостоятельное задание: сравнить скорость работы этих коллекций.
1 этап: создать МНОГО коллекций по 8 и по 9 элементов (ОТДЕЛЬНО).
2 этап: создать ОДНУ коллекцию из ОГРОМНОГО количества элементов.
Подвести итоги и в отчёте написать вывод.
Отчёт отправил: 6861. Den Andreevich Выполнено за 2 час. 00 мин. [Показать отчёт]
Научился: Создавать набор элементов на базе ListDictionary, Hashtable и HybridDictionary . Удалось сравнить время отработки каждого из классов при формировании различных комбинаций большого кол-ва эл-ов : ListDictionary на порядок уступил по времени отработки двум другим классам (Hashtable и HybridDictionary), которые показали практически одинаковые результаты .  
Сложности: Особых сложностей не было. Наоборот - интересно . 
Комментарии: Урок понравился. Осталось понимание базового применения вышеуказанных классов. 
6 BitArray 00:14:00 39 чел. ★ 4.9 Done
  На этом уроке мы поработаем с интересной коллекцией BitArray,
которая позволяет компактно хранить большие массивы двоичных данных.

Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 00 мин. [Показать отчёт]
Научился: Применять битовый массив BitArray, а также некоторые его методы на практике . 
Сложности: Сложностей не было . Интересно было поэкспериментировать с методами OR, Set, SetALL, And . 
Комментарии: Всё отлично, идём дальше . 
7 Граф 00:13:48 39 чел. ★ 4.9 Done
  На этом уроке я дам определение графа своими словами,
всё, что запомнил с момента учёбы в университете.
В конце урока мы зададимся вопросом -
как хранить граф в памяти компьютера.
Отчёт отправил: 6861. Den Andreevich Выполнено за 2 час. 00 мин. [Показать отчёт]
Научился: Получил представление о графе и его разновидностях, методах представления.  
Сложности: Определиться с вариантом хранения графа { цвета вершин, смежные вершины } . В конечном итоге остановился на варианте списка классов, в которых и хранятся цвета вершин со списком смежности . Насколько верно понял задание - покажут ваши отзывы ) . 
Комментарии: Интересно продолжение .  
8 Вершины 00:14:15 39 чел. ★ 4.9 Done
  На этом уроке мы начнём создавать класс Граф
для хранения графа и работы с ним.
На уроке мы создадим всё, что касается вершин.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 00 мин. [Показать отчёт]
Научился: Применять русские названия методов ), перечисление Цвет, узнал об итераторах (yield return), создали часть класса Граф по формированию вершин . 
Сложности: Разобраться с назначением yield return . В качестве варианта формирования рёбер остановился на HybridDictionary(); учитывая что их кол-во будет больше 20ти . В качестве параметров можно передавать номера смежных вершин.  
Комментарии: Хороший урок - довольно много вопросов вызвал ) . 
9 Рёбра 00:12:47 38 чел. ★ 4.9 Done
  На этом уроке мы содадим колекцию для хранения рёбер.
Опишем методы добавления рёбер и перебора смежных вершин.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 30 мин. [Показать отчёт]
Научился: Дополнили класс Граф новыми методами (некоторые с исп-ем yield return). В итоге получили завершённую структуру по формированию заданного графа.  
Сложности: Сложностей не было. 
Комментарии: Спасибо за урок - всё понравилось. 
10 Инициация 00:11:15 38 чел. ★ 5 Done
  На этом уроке мы создадим экземпляр нашего графа
и добавим в него все его элементы по образцу.
Самостоятельное задание - вывести граф на экран.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 30 мин. [Показать отчёт]
Научился: Применять Label для вывода псевдографики на форму при заданных координатах лев. верхнего угла метки. 
Сложности: Ничего . Понадобилось время для подбора нужных координат , дабы картинка соответствовала графу . 
Комментарии: Жду продолжения ) . 
11 Отображение 00:16:18 38 чел. ★ 5 Done
  На этом уроке мы выведем граф на экран: и вершины и рёбра.
Отчёт отправил: 6861. Den Andreevich Выполнено за 30 мин. [Показать отчёт]
Научился: Выводить на экран заданную структуру графа . 
Сложности: После формирования нужных нам методов оценить логику работы алгоритма вцелом .  
Комментарии: Всё понравилось - идём дальше . 
12 Шахматная доска 00:19:58 38 чел. ★ 5 Done
  На этом уроке мы создадим граф в виде Шахматной доски.
И организуем её вывод на экран.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 30 мин. [Показать отчёт]
Научился: Формировать граф в виде шахматной доски и выводить его на экран . 
Сложности: Особых сложностей не было .  
Комментарии: Хороший урок, идём дальше ) .  
13 Широкий поиск 00:14:59 38 чел. ★ 5 Done
  На этом уроке мы познакомимся с алгоритмом поиска вширь.
Мы проработаем весь алгоритм на конкретном примере.
Самостоятельное задание - выбрать граф и также с ним поработать.
Отчёт отправил: 6861. Den Andreevich Выполнено за 35 мин. [Показать отчёт]
Научился: Проработке графа с помощью алгоритма поиска в ширину. 
Сложности: Сложностей не было. 
Комментарии: Начало как говорится интригующее - жду продолжения ) . 
14 Широкий алгоритм 00:14:12 36 чел. ★ 5 Done
  На этом уроке мы напишем алгоритм поиска вширь.
Однако, запустить его не удастся. Почему?
Это вам самостоятельное задание, разобраться
в причине, и найти способ, как это исправить.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 00 мин. [Показать отчёт]
Научился: Реализации алгоритма поиска вширь на уровне кода, поиску причин возникновения Exception-a "Collection was modified; enumeration operation may not execute".  
Сложности: Особых сложностей не было . Понадобилось время для пошаговой проверки алгоритма. 
Комментарии: Урок понравился тем, что пришлось разбираться в причинах возникшей ошибки. Выяснил, что при исп-ии foreach (int nr in ВсеВершины()) в методе УстановитьЦвет(Цвет цвет), Hashtable вершины вернул при 1м проходе номер 12й вершины, т.е. эл-ты расположились в обратном порядке (по убыванию). Заменив строку foreach (int nr in ВсеВершины()) на for (int nr = 0; nr < вершины.Count; nr++) алгоритм последовательно прошёл все вершины (от 0 до 12й) и уже без exception-a. Второй момент, в классе ПоискВШирь исправил строку граф.УстановитьЦвет(Граф.Цвет.чёрный) на граф.УстановитьЦвет(a, Граф.Цвет.чёрный) - иначе все вершины графа будут окрашиваться чёрным при извлечении 1го эл-та из очереди. Если не прав - жду ваших замечаний . 
15 Широкий пошаговый ход 00:11:46 35 чел. ★ 5 Done
  На этом уроке мы исправишм ошибку из прошлого урока
и пройдёмся пошагово по всему алгоритму.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 00 мин. [Показать отчёт]
Научился: Пошаговой проработке алгоритма поиска вширь, окрашиванию меток (Label) - они же вершины графа : для этого передаю список вершин list
16 Визуализация процесса 00:14:07 30 чел. ★ 5 Done
  На этом уроке мы создадим делегат "Покраска"
и через него реализуем отображение процесса.

Отчёт отправил: 6861. Den Andreevich Выполнено за 30 мин. [Показать отчёт]
Научился: Применять делегат для окрашивания вершин графа . 
Сложности: Ничего 
Комментарии: Предлагаю заменить panel1.Refresh() + ConnectLabels() на list[nr].Refresh() - то же самое но без морганий ) .  
17 Глубокий поиск 00:09:58 30 чел. ★ 5 Done
  На этом уроке мы познакомимся с алгоритмом поиска вглубь.
Мы проработаем весь алгоритм на конкретном примере.
Самостоятельное задание - выбрать граф и также с ним поработать.
Отчёт отправил: 6861. Den Andreevich Выполнено за 1 час. 30 мин. [Показать отчёт]
Научился: Проработке алгоритма поиска вглубь на примере различных графов. 
Сложности: Ничего . 
Комментарии: Спасибо за задание - пришлось немного пофантазировать . 
18 Глубокий алгоритм 00:15:07 30 чел. ★ 5 Done
  На этом уроке мы напишем алгоритм поиска вглубь.
Вернее сказать - скопипастим. И пофилософствуем.
На этом же уроке посмотрим, как он работает.
Отчёт отправил: 6861. Den Andreevich Выполнено за 20 мин. [Показать отчёт]
Научился: Применять алгоритм поиска пути вглубь . Узнал для каких целей его применяют. 
Сложности: Ничего 
Комментарии: Спасибо большое за урок . 
19 ФИНАЛЬНЫЙ УРОК 30 чел. ★ 5 Done
  Поздравляю с окончанием курса!
Оставь отзыв об этом курсе.

Какой курс ты будешь проходить следующим?
Отчёт отправил: 6861. Den Andreevich Выполнено за 30 мин. [Показать отчёт]
Научился: Познакомился с применением на практике различных коллекций (ArrayList, List, ListDictionary, Hashtable и HybridDictionary), а также их встроенных методов . Выяснил, что по скорости обработки различных комбинаций большого кол-ва эл-ов ListDictionary на порядок уступил по времени отработки двум другим классам : Hashtable и HybridDictionary, которые показали практически одинаковые результаты . Применять битовый массив BitArray, а также некоторые его методы на практике . Получил представление о графе и его разновидностях, методах представления, применять русские названия методов , перечисление , узнал об итераторах (yield return). Формировать граф в виде шахматной доски либо опр-ой формы и выводить его на экран с последующим поиском пути Вширь и Вглубь . При этом узнал о специфике применения foreach() и HashTable().  
Сложности: При выполнении самостоятельных заданий определиться с вариантом хранения графа { цвета вершин, смежные вершины }, найти причину возникновения Exception-a при отработке foreach() и HashTable(), разобраться с общей логикой работы программы. 
Комментарии: Хочу от всей души поблагодарить за коллекционный курс графопостроения ) ! Материала для применения и размышлений - более чем ! После данного курса планирую закончить "Бинарная жизнь" и переключиться на курсы "Игра Сокобан", "Графоциклы", "Итератор" . Конечно же в планах пройти все предложенные курсы на данный момент - главное двигаться дальше .  
  Итого:   19 видеоуроков общей продолжительностью 4 час. 06 мин. 30 чел. ★ 4.98  
  Финалисты:   Максим,   Alcatraz,   Дмитрий,   Tekashnik,   Denis,   Иван,   Дмитрий 199,   Николай,   Михаил,   Дмитрий,   Ender,   Платон,   Владимир,   Андрей Н.,   Владимир Борисенко,   Максим Лапшинов,   Permitin Alexey,   Новопашин Владимир,   Максим Саратов,   Алексей В.,   Den Andreevich,   Елена,   Станислав,   Сергей Соколов,   Yefim,   Алексей Малышев,   Александр,   Сергей,   Денис,   chokayes .

Начинаем практику по языку C#




Чтобы стать хорошим программистом — нужно писать программы. На нашем сайте очень много практических упражнений.

После заполнения формы ты будешь подписан на рассылку «C# Вебинары и Видеоуроки», у тебя появится доступ к видеоурокам и консольным задачам.

Несколько раз в неделю тебе будут приходить письма — приглашения на вебинары, информация об акциях и скидках, полезная информация по C#.

Ты в любой момент сможешь отписаться от рассылки.
Научился: Работать со встроенными классами списков, такими как: List, ListDictionary, HashTable, HybridTable. Также основам работы с графами, их заполнению и перебору с использованием списков.
Трудности: Большое количество новой терминологии и понятий, enumerable и иже с ним. HashTable тоже сложный объект, т.к. там еще хеш-функция внутри и много математики, о которой мало что известно.
Очень полезный курс. Учитывая, что большинство программ так или иначе работают со списками, то, чтобы не изобретать велосипеды с массивами, хорошо бы сразу знать какие уже классы разработаны.
Научился: Разобрали алгоритмы поиска в глубь и в ширь
Я считаю, что курс просто отличный. Мало того, что мы узнаем как работает стек и очередь, еще мы разберем 2 алгоритма прохода по графу, а также увидим воочию как работают эти алгоритмы. Если немного доработать самостоятельно, можно прикрутить поиск кратчайшего пути. А понимание такого механизма очень поможет в спортивном программировании! Единственный (как мне кажется) недочет, так это то, что в курсе используются IEnumerable. Мне, как не проходившему по данному типу видеокурс, было немного тяжело, хоть и интуитивно понятно, как это работает. В общем и целом, я рекомендую этот курс всем, кто хочет еще глубже погрузиться в атмосферу программирования, а также всем, кто захочет когда нибудь участвовать в олимпиадах и различных конкурсах по программированию. Между прочим, алгоритм поиска кратчайшего пути является основным алгоритмом на ежегодном конкурсе Russian AI Cup (соревнование по программированию ИИ)