Skuteczny programista potrzebuje solidnego zrozumienia struktur danych i algorytmów. Rozmowy techniczne często sprawdzają Twoje umiejętności rozwiązywania problemów i krytycznego myślenia.
Wykresy są jedną z wielu ważnych struktur danych w programowaniu. W większości przypadków zrozumienie wykresów i rozwiązywanie problemów opartych na wykresach nie przychodzi łatwo.
Co to jest wykres i co musisz o nim wiedzieć?
Co to jest wykres?
Wykres to nieliniowa struktura danych, która ma węzły (lub wierzchołki) z łączącymi je krawędziami. Wszystkie drzewa są podtypami wykresów, ale nie wszystkie wykresy są drzewami, a wykres jest strukturą danych, z której pochodzą drzewa.
Chociaż możesz budować struktury danych w JavaScript i innych językach, możesz zaimplementować wykres na różne sposoby. Najpopularniejsze podejścia to listy krawędzi, listy sąsiedztwa, oraz macierze sąsiedztwa.
The Przewodnik Khan Academy dotyczący przedstawiania wykresów jest doskonałym źródłem informacji o tym, jak przedstawiać wykres.
Istnieje wiele różnych typów wykresów. Jedno wspólne rozróżnienie to między skierowany oraz bezkierunkowy wykresy; pojawiają się one często w wyzwaniach związanych z kodowaniem i w rzeczywistych zastosowaniach.
Rodzaje wykresów
- Kierowany wykres: Wykres, w którym wszystkie krawędzie mają kierunek, określany również jako dwuznak.
- Wykres nieskierowany: Wykres nieskierowany jest również nazywany wykresem dwukierunkowym. W grafach nieskierowanych kierunek krawędzi nie ma znaczenia, a przemierzanie może przebiegać w dowolnym kierunku.
- Wykres ważony: Wykres ważony to wykres, którego węzły i krawędzie mają powiązaną wartość. W większości przypadków ta wartość reprezentuje koszt eksploracji tego węzła lub krawędzi.
- Wykres skończony: Wykres, który ma skończoną liczbę węzłów i krawędzi.
- Nieskończony wykres: Wykres, który ma nieskończoną liczbę węzłów i krawędzi.
- Wykres trywialny: Wykres, który ma tylko jeden węzeł i nie ma krawędzi.
- Prosty wykres: Gdy tylko jedna krawędź łączy każdą parę węzłów grafu, nazywa się to grafem prostym.
- Wykres zerowy: Graf zerowy to graf, który nie ma krawędzi łączących jego węzły.
- Multigraf: W multigrafie co najmniej para węzłów ma więcej niż jedną łączącą je krawędź. W multigrafach nie ma pętli własnych.
- Pełny wykres: Kompletny graf to graf, w którym każdy węzeł łączy się z każdym innym węzłem na grafie. Znany jest również jako pełny wykres.
- Pseudograf: Wykres, który ma własną pętlę poza innymi krawędziami grafu, nazywany jest pseudografem.
- Wykres regularny: Zwykły wykres to wykres, w którym wszystkie węzły mają równe stopnie; tj. każdy węzeł ma taką samą liczbę sąsiadów.
- Połączony wykres: Graf spójny to po prostu dowolny graf, w którym łączą się dowolne dwa węzły; czyli graf z co najmniej jedną ścieżką pomiędzy każdymi dwoma węzłami grafu.
- Odłączony wykres: Rozłączony wykres jest bezpośrednim przeciwieństwem połączonego wykresu. W rozłączonym grafie nie ma krawędzi łączących węzły grafu, tak jak w a zero wykres.
- Wykres cykliczny: Wykres cykliczny to wykres zawierający co najmniej jeden cykl wykresu (ścieżka, która kończy się tam, gdzie się zaczęła).
- Wykres acykliczny: Wykres acykliczny to wykres bez cykli. Może być skierowany lub nieukierunkowany.
- Podpunkt: Wykres podrzędny to wykres pochodny. Jest to graf utworzony z węzłów i krawędzi będących podzbiorami innego grafu.
A pętla na wykresie jest krawędzią, która zaczyna się od węzła i kończy się w tym samym węźle. Dlatego też pętla własna jest pętlą nad tylko jednym węzłem grafu, jak widać na pseudografie.
Algorytmy przechodzenia przez wykres
Będąc rodzajem nieliniowej struktury danych, przechodzenie przez wykres jest dość trudne. Przemierzanie wykresu oznacza przechodzenie i badanie każdego węzła, pod warunkiem, że istnieje prawidłowa ścieżka przez krawędzie. Algorytmy przechodzenia przez wykres są głównie dwojakiego rodzaju.
- Wyszukiwanie według szerokości (BFS): Wyszukiwanie wszerz to algorytm przechodzenia przez graf, który odwiedza węzeł grafu i eksploruje jego sąsiadów przed przejściem do któregokolwiek z jego węzłów podrzędnych. Chociaż możesz rozpocząć przechodzenie po grafie z dowolnego wybranego węzła, Węzeł główny jest zwykle preferowanym punktem wyjścia.
- Wyszukiwanie według głębokości (DFS): Jest to drugi główny algorytm przechodzenia przez graf. Odwiedza węzeł grafu i eksploruje węzły lub gałęzie podrzędne przed przejściem do następnego węzła — to znaczy najpierw zagłębia się, zanim przejdzie do szerokiego.
Przeszukiwanie wszerz jest zalecanym algorytmem do znajdowania ścieżek między dwoma węzłami tak szybko, jak to możliwe, zwłaszcza najkrótszej ścieżki.
Wyszukiwanie w głąb jest najczęściej zalecane, gdy chcesz odwiedzić każdy węzeł na wykresie. Oba algorytmy przechodzenia działają dobrze w każdym przypadku, ale jeden może być prostszy i bardziej zoptymalizowany niż drugi w wybranych scenariuszach.
Prosta ilustracja może pomóc lepiej zrozumieć oba algorytmy. Pomyśl o stanach kraju jako wykresie i spróbuj sprawdzić, czy dwa stany, X oraz Tak, są połączone. Poszukiwania w głąb mogą przebiegać na ścieżce prawie po całym kraju, nie zdając sobie z tego sprawy wystarczająco wcześnie Tak to tylko 2 stany od X.
Zaletą wyszukiwania wszerz jest to, że zachowuje ono możliwie największą bliskość do bieżącego węzła przed przejściem do następnego. Znajdzie połączenie między X oraz Tak w krótkim czasie bez konieczności zwiedzania całego kraju.
Kolejną istotną różnicą między tymi dwoma algorytmami jest sposób ich implementacji w kodzie. Wyszukiwanie wszerz to an algorytm iteracyjny i korzysta z kolejka, podczas gdy wyszukiwanie w głąb jest zwykle implementowane jako a algorytm rekurencyjny który wykorzystuje stos.
Poniżej znajduje się kilka pseudokodów demonstrujących implementację obu algorytmów.
Wyszukiwanie wszerz
bfs (Wykres G, GraphNode root) {
wynajmować q być Nowy Kolejka// zaznacz root jako odwiedzony
root.visited = PRAWDA// dodaj root do kolejki
q.kolejka(źródło)
podczas gdy (q nie jest pusty) {
wynajmować bieżący być q.dequeue() // usuń przedni element w kolejce
for (sąsiedzi n prądu w G) {
jeśli (n jestnie jeszcze odwiedzone) {
// dodaj do kolejki - byś mógł też eksplorować sąsiadów
q.kolejka(n)
n.odwiedzone = PRAWDA
}
}
}
}
Głębokość wyszukiwania na pierwszym miejscu
dfs (Wykres G, GraphNode root) {
// przypadek podstawowy
jeśli (korzeń to zero) zwrócić// zaznacz root jako odwiedzony
root.visited = PRAWDA
for (sąsiedzi n korzenia w G)
jeśli (n jestnie jeszcze odwiedzone)
dfs (G, n) // wywołanie rekurencyjne
}
Kilka innych algorytmów przechodzenia przez grafy wywodzi się z przeszukiwania wszerz i w głąb. Najpopularniejsze z nich to:
- Wyszukiwanie dwukierunkowe: Ten algorytm jest zoptymalizowanym sposobem znajdowania najkrótszej ścieżki między dwoma węzłami. Używa dwóch wyszukiwań wszerz, które kolidują, jeśli istnieje ścieżka.
- Sortowanie topologiczne: To jest używane w grafy skierowane aby posortować węzły w żądanej kolejności. Nie można zastosować sortowania topologicznego do wykresów nieskierowanych lub wykresów z cyklami.
- Algorytm Dijkstry: To też jest rodzaj BFS. Jest również używany do znalezienia najkrótszej ścieżki między dwoma węzłami w a ważony wykres ukierunkowany, który może mieć cykle lub nie.
Często zadawane pytania do wywiadu oparte na wykresach
Wykresy są jednymi z najważniejszych struktury danych, które powinien znać każdy programista. Podczas wywiadów technicznych często pojawiają się pytania na ten temat i możesz napotkać klasyczne problemy związane z tym tematem. Należą do nich problemy takie jak „sędzia miasta”, „liczba wysp” i „podróżujący sprzedawca”.
To tylko kilka z wielu popularnych problemów wywiadu opartych na wykresach. Możesz je wypróbować LeetKod, HackerRank, lub GeeksforGeeks.
Zrozumienie grafowych struktur danych i algorytmów
Wykresy są przydatne nie tylko podczas wywiadów technicznych. Mają też rzeczywiste przypadki użycia, takie jak in sieci, mapy, oraz systemy lotnicze do znajdowania tras. Są również wykorzystywane w podstawowej logice systemów komputerowych.
Wykresy doskonale nadają się do porządkowania danych i pomagają nam wizualizować złożone problemy. Wykresy powinny być jednak używane tylko wtedy, gdy jest to absolutnie konieczne, aby zapobiec złożoności miejsca lub problemom z pamięcią.