Алгоритми за напреднали: обхождане на графи
Ако вече си навлязъл в света на алгоритмите, знаеш, че те неотменно вървят ръка за ръка със структурите от данни. Очакват те курсове за алгоритми за напреднали с различни езици – Algorithms Advanced with C#, както и Algorithms Advanced with Java, които ще ти разкрият тази връзка, ще те запознаят с най-популярните техники за програмиране и ще ти помогнат да развиеш уменията си допълнително.
По повод предстоящите курсове, днес ще припомним на кратко какво представляват графите и ще видим кои са едни от ключовите алгоритми, които могат да ти помогнат в работата с тях. Тези алгоритми са част и от практическата ти подготовка по време на курсовете, и ще ги видиш как работят на практика.
Какво са графите?
Графите са едни от най-разпространените и използвани структури от данни в програмирането. Основната причина за това е, че множество проблеми могат да бъдат представени с помощта на граф и съответно да бъдат решени бързо и ефикасно с някоя от множеството съществуващи техники, които могат да се прилагат с тази структура от данни.
Като такава, графът представлява начина, по който са свързани елементите в едно множество. Но дори и да не използваш такава структура за всяко свое решение, самото ѝ познаване ще ти помогне да развиеш допълнително алгоритмичното си мислене и да подобриш подхода си при решаването на задачите си.
Графите се характеризират с т.нар. върхове (също възли, точки) и ребра. Сред типичните приложения на структурата от данни е намирането на път между два върха от нея. А предвид това колко разпространена техника за програмиране е, можеш да прилагаш и редица алгоритми, част от които ще разгледаме в следващите редове, а самият ти, както споменах, ще изучаваш задълбочено по време на курса, който избереш, и ще видиш как работят на практика.
Намиране на най-кратък път
Алгоритъмът на Дийкстра се използва за намирането на най-краткия път в ориентиран или неориентиран граф с неотрицателни тегла на ребрата. Това е и сред най-популярните алгоритми, които могат да решат тази задача. Тъй като работи само при графи с неотрицателни тегла, съществуват алтернативи като алгоритъмът на Белман-Форд, който ще ти позволи да работиш с граф с отрицателни тегла на ребрата. Именно това го прави по-гъвкав от този на Дийкстра, но е по-бавен като изпълнение.
Защо го отбелязвам? Едно от най-важните решения при използването на алгоритми ще бъде дали да оптимизираш по време или по памет. Както вероятно вече знаеш, паметта е много по-достъпен ресурс от времето, затова и трябва внимателно да направиш подбора на алгоритмите, които ще използваш. И с двата, споменати дотук, ще имаш възможност да работиш по време на предстоящото обучение, с езика, който избереш.
Минимално покриващо дърво
Граф, в който съществува път от всеки връх до всеки друг, наричаме свързан. Във всеки свързан граф ще откриеш т.нар. свързващо дърво или под-граф, включващ всички върхове в себе си. По време на обученията ще се научиш да работиш с познатото като минимално покриващо дърво (minimum spanning tree, MST). Такова дърво има оптимална сума от теглата на ребрата – най-малка.
Два са основните начини, по които можеш да намериш MST на графа, с който работиш. Единият е чрез алгоритъма на Крускал, който е тип алчен алгоритъм и на всяка стъпка добавя реброто с най-ниско тегло, което няма да формира цикъл в дървото (т.е. поне един от върховете не трябва вече да е част от MST).
Другият начин е да използваш алгоритъма на Прим, който по своето естество също е алчен алгоритъм. Той ти позволява да избереш конкретния връх, от който да започнеш, като отново се добавят последователно ребрата с най-ниски тегла.
Тези и още много детайли ще откриеш в курсовете за напреднали. Можеш да избираш между обучение с Java или C#, затова е важно самият ти да използваш достатъчно уверено един от двата езика. Освен, че ще се запознаеш с водещи алгоритми, ще надградиш уменията си в динамичното оптимиране и амортизационния анализ. Важно е да си запознат с основните похвати за решаване на алгоритмични проблеми и да имаш познания по структури от данни, за да вземеш максимума от обучението. Ако си готов, избери курса за теб: