Loading...

Алгоритми за напреднали: обхождане на графи

avatar Мария Вълчева 3 минути 260
Алгоритми за напреднали: обхождане на графи

Ако вече си навлязъл в света на алгоритмите, знаеш, че те неотменно вървят ръка за ръка със структурите от данни. Очакват те курсове за алгоритми за напреднали с различни езици – Algorithms Advanced with C#, както и Algorithms Advanced with Java, които ще ти разкрият тази връзка, ще те запознаят с най-популярните техники за програмиране и ще ти помогнат да развиеш уменията си допълнително.

По повод предстоящите курсове, днес ще припомним на кратко какво представляват графите и ще видим кои са едни от ключовите алгоритми, които могат да ти помогнат в работата с тях. Тези алгоритми са част и от практическата ти подготовка по време на курсовете, и ще ги видиш как работят на практика.

Какво са графите?

Графите са едни от най-разпространените и използвани структури от данни в програмирането. Основната причина за това е, че множество проблеми могат да бъдат представени с помощта на граф и съответно да бъдат решени бързо и ефикасно с някоя от множеството съществуващи техники, които могат да се прилагат с тази структура от данни.

Като такава, графът представлява начина, по който са свързани елементите в едно множество. Но дори и да не използваш такава структура за всяко свое решение, самото ѝ познаване ще ти помогне да развиеш допълнително алгоритмичното си мислене и да подобриш подхода си при решаването на задачите си.

Графите се характеризират с т.нар. върхове (също възли, точки) и ребра. Сред типичните приложения на структурата от данни е намирането на път между два върха от нея. А предвид това колко разпространена техника за програмиране е, можеш да прилагаш и редица алгоритми, част от които ще разгледаме в следващите редове, а самият ти, както споменах, ще изучаваш задълбочено по време на курса, който избереш, и ще видиш как работят на практика.

Намиране на най-кратък път

Алгоритъмът на Дийкстра се използва за намирането на най-краткия път в ориентиран или неориентиран граф с неотрицателни тегла на ребрата. Това е и сред най-популярните алгоритми, които могат да решат тази задача. Тъй като работи само при графи с неотрицателни тегла, съществуват алтернативи като алгоритъмът на Белман-Форд, който ще ти позволи да работиш с граф с отрицателни тегла на ребрата. Именно това го прави по-гъвкав от този на Дийкстра, но е по-бавен като изпълнение.

Защо го отбелязвам? Едно от най-важните решения при използването на алгоритми ще бъде дали да оптимизираш по време или по памет. Както вероятно вече знаеш, паметта е много по-достъпен ресурс от времето, затова и трябва внимателно да направиш подбора на алгоритмите, които ще използваш. И с двата, споменати дотук, ще имаш възможност да работиш по време на предстоящото обучение, с езика, който избереш.

Минимално покриващо дърво

Граф, в който съществува път от всеки връх до всеки друг, наричаме свързан. Във всеки свързан граф ще откриеш т.нар. свързващо дърво или под-граф, включващ всички върхове в себе си. По време на обученията ще се научиш да работиш с познатото като минимално покриващо дърво (minimum spanning tree, MST). Такова дърво има оптимална сума от теглата на ребрата – най-малка.

Два са основните начини, по които можеш да намериш MST на графа, с който работиш. Единият е чрез алгоритъма на Крускал, който е тип алчен алгоритъм и на всяка стъпка добавя реброто с най-ниско тегло, което няма да формира цикъл в дървото (т.е. поне един от върховете не трябва вече да е част от MST).

Другият начин е да използваш алгоритъма на Прим, който по своето естество също е алчен алгоритъм. Той ти позволява да избереш конкретния връх, от който да започнеш, като отново се добавят последователно ребрата с най-ниски тегла.

Тези и още много детайли ще откриеш в курсовете за напреднали. Можеш да избираш между обучение с Java или C#, затова е важно самият ти да използваш достатъчно уверено един от двата езика. Освен, че ще се запознаеш с водещи алгоритми, ще надградиш уменията си в динамичното оптимиране и амортизационния анализ. Важно е да си запознат с основните похвати за решаване на алгоритмични проблеми и да имаш познания по структури от данни, за да вземеш максимума от обучението. Ако си готов, избери курса за теб:

Запиши се за Algorithms Advanced with C# ТУК

Запиши се за Algorithms Advanced with Java ТУК

Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.