Ефективният програмист се нуждае от солидно разбиране на структурите от данни и алгоритмите. Техническите интервюта често ще тестват вашите умения за решаване на проблеми и критично мислене.
Графиките са една от многото важни структури от данни в програмирането. В повечето случаи разбирането на графиките и решаването на базирани на графики проблеми не е лесно.
Какво е графика и какво трябва да знаете за нея?
Какво е графика?
Графът е нелинейна структура от данни, която има възли (или върхове) с ръбове, които ги свързват. Всички дървета са подвидове на графики, но не всички графики са дървета, а графиката е структурата от данни, от която произхождат дърветата.
Въпреки че можете изграждане на структури от данни в JavaScript и други езици, можете да реализирате графика по различни начини. Най-популярните подходи са крайни списъци, списъци със съседство, и матрици на съседство.
The Ръководство на Khan Academy за представяне на графики е чудесен ресурс за научаване как да представяте графика.
Има много различни видове графики. Една обща разлика е между
насочени и нережисиран графики; те се появяват често при предизвикателства при кодиране и употреби в реалния живот.Видове графики
- Насочена графика: Графика, в която всички ръбове имат посока, наричана още диграф.
- Неориентирана графика: Неориентираната графика е известна още като двупосочна графика. В неориентираните графи посоката на ръбовете няма значение и преминаването може да върви във всяка посока.
- Претеглена графика: Претеглена графика е графика, чиито възли и ръбове имат свързана стойност. В повечето случаи тази стойност представлява разходите за изследване на този възел или ръб.
- Крайна графика: Граф, който има краен брой възли и ръбове.
- Безкрайна графика: Графика, която има безкрайно количество възли и ръбове.
- Тривиална графика: Графика, която има само един възел и няма ръб.
- Проста графика: Когато само едно ребро свързва всяка двойка възли на графика, тя се нарича проста графа.
- Нулева графика: Нулева графа е графа, която няма ръбове, свързващи нейните възли.
- Мултиграф: В мултиграф поне двойка възли имат повече от един ръб, който ги свързва. В мултиграфите няма самоцикли.
- Пълна графика: Пълна графика е графика, в която всеки възел се свързва с всеки друг възел в графиката. Известен е още като a пълна графика.
- Псевдо графика: Граф, който има самозавъртане встрани от други ръбове на графика, се нарича псевдограф.
- Редовна графика: Редовна графика е графика, в която всички възли имат равни степени; всеки възел има еднакъв брой съседи.
- Свързана графика: Свързан граф е просто всеки график, в който всеки два възела се свързват; т.е. графика с поне един път между всеки два възела на графиката.
- Прекъсната графика: Несвързаният граф е пряката противоположност на свързания граф. В несвързана графика няма ръбове, свързващи възлите на графиката, като например в a нула графика.
- Циклична графика: Циклична графика е графика, съдържаща поне един цикъл на графиката (път, който завършва там, където е започнал).
- Ациклична графика: Ациклична графика е графика без никакви цикли. Може да бъде насочен или ненасочен.
- Подграф: Подграфът е производна графика. Това е графика, образувана от възли и ръбове, които са подмножества на друга графика.
А цикъл в графика е ребро, което започва от възел и завършва в същия възел. Следователно, а самопримка е цикъл върху само един възел на графиката, както се вижда в псевдо графика.
Алгоритми за обхождане на графика
Тъй като е вид нелинейна структура от данни, преминаването през графика е доста сложно. Обхождането на графика означава преминаване през и изследване на всеки възел, при условие че има валиден път през ръбовете. Алгоритмите за обхождане на графики са основно два типа.
- Търсене в ширина (BFS): Търсенето в ширина е алгоритъм за обхождане на графика, който посещава възел на графика и изследва неговите съседи, преди да премине към някой от дъщерните му възли. Въпреки че можете да започнете да обхождате графика от всеки избран възел, the коренов възел обикновено е предпочитаната отправна точка.
- Първо търсене в дълбочина (DFS): Това е вторият основен алгоритъм за обхождане на графика. Той посещава възел на графа и изследва неговите дъщерни възли или разклонения, преди да продължи към следващия възел – тоест първо навлиза дълбоко, преди да се разшири.
Търсенето в ширина е препоръчителният алгоритъм за намиране на пътища между два възела възможно най-бързо, особено най-краткия път.
Търсенето първо в дълбочина се препоръчва най-вече, когато искате да посетите всеки възел в графиката. И двата алгоритъма за преминаване работят добре във всеки случай, но единият може да е по-прост и по-оптимизиран от другия в избрани сценарии.
Една проста илюстрация може да помогне за по-доброто разбиране на двата алгоритъма. Мислете за щатите на една държава като графика и се опитайте да проверите дали два щата, х и Y, са свързани. Първото търсене в дълбочина може да тръгне по пътя почти из страната, без да осъзнае това достатъчно рано Y е само на 2 щата от х.
Предимството на търсенето в ширина е, че поддържа възможно най-голяма близост до текущия възел, преди да премине към следващия. Ще открие връзката между х и Y за кратко време, без да се налага да изследвате цялата страна.
Друга основна разлика между тези два алгоритъма е в начина, по който са имплементирани в кода. Търсенето първо в ширина е итеративен алгоритъм и използва a опашка, докато търсенето първо в дълбочина обикновено се изпълнява като a рекурсивен алгоритъм който се възползва от стек.
По-долу е даден псевдокод, демонстриращ изпълнението на двата алгоритъма.
Търсене в ширина
bfs (Graph G, корен на GraphNode) {
позволявам q бъде нов Опашка// маркирайте root като посетен
root.visited = вярно// добавяне на root към опашката
р.поставяне на опашка(корен)
докато (q не е празна) {
позволявам текущият бъде q.dequeue() // премахване на предния елемент в опашката
за (съседи n на текущия в G) {
ако (н ене още посетен) {
// добавете към опашката - така че можете да изследвате и съседите му
р.поставяне на опашка(н)
n.visited = вярно
}
}
}
}
Първо търсене в дълбочина
dfs (Graph G, корен на GraphNode) {
// основен случай
ако (коренът е нула) връщане// маркирайте root като посетен
root.visited = вярно
за (съседи n на корен в G)
ако (н ене все още посетен)
dfs (G, n) // рекурсивно извикване
}
Няколко други алгоритъма за обхождане на графики произлизат от търсене първо в ширина и първо в дълбочина. Най-популярните са:
- Двупосочно търсене: Този алгоритъм е оптимизиран начин за намиране на най-краткия път между два възела. Той използва две търсения в ширина, които се сблъскват, ако има път.
- Топологично сортиране: Това се използва в насочени графи за сортиране на възлите в желания ред. Не можете да приложите топологично сортиране към неориентирани графики или графики с цикли.
- Алгоритъмът на Дейкстра: Това също е вид BFS. Използва се и за намиране на най-краткия път между два възела в a претеглена насочена графа, които могат да имат или не цикли.
Често срещани въпроси за интервю, базирани на графики
Графиките са сред важните структури от данни, които всеки програмист трябва да знае. Често възникват въпроси по тази тема в техническите интервюта и може да срещнете някои класически проблеми, свързани с темата. Те включват проблеми като "градски съдия", "брой острови" и "пътуващ търговец".
Това са само няколко от многото популярни задачи за интервю, базирани на графики. Можете да ги изпробвате LeetCode, HackerRank, или GeeksforGeeks.
Разбиране на графични структури от данни и алгоритми
Графиките не са полезни само за технически интервюта. Те също имат случаи на използване в реалния свят, като например в работа в мрежа, карти, и авиокомпанийни системи за намиране на маршрути. Те се използват и в основната логика на компютърните системи.
Графиките са отлични за организиране на данни и ни помагат да визуализираме сложни проблеми. Графиките обаче трябва да се използват само когато е абсолютно необходимо, за да се предотвратят проблеми с пространствената сложност или паметта.
