Een effectieve programmeur heeft een gedegen kennis van datastructuren en algoritmen nodig. Technische interviews testen vaak uw probleemoplossende en kritisch denkvermogen.
Grafieken zijn een van de vele belangrijke datastructuren bij het programmeren. In de meeste gevallen is het begrijpen van grafieken en het oplossen van op grafieken gebaseerde problemen niet eenvoudig.
Wat is een grafiek en wat moet je erover weten?
Wat is een grafiek?
Een grafiek is een niet-lineaire gegevensstructuur met knopen (of hoekpunten) met randen die ze verbinden. Alle bomen zijn subtypes van grafieken, maar niet alle grafieken zijn bomen, en de grafiek is de gegevensstructuur waaruit bomen zijn voortgekomen.
Hoewel je kunt bouw datastructuren in JavaScript en andere talen, kunt u een grafiek op verschillende manieren implementeren. De meest populaire benaderingen zijn: randlijsten, aangrenzende lijsten, en aangrenzende matrices.
De Khan Academy-gids voor het weergeven van grafieken is een geweldige bron om te leren hoe een grafiek moet worden weergegeven.
Er zijn veel verschillende soorten grafieken. Een veelvoorkomend onderscheid is tussen: geregisseerd en ongericht grafieken; deze komen veel voor bij coderingsuitdagingen en real-life toepassingen.
Soorten grafieken
- Gerichte grafiek: Een grafiek waarin alle randen een richting hebben, ook wel aangeduid als digraaf.
- Ongerichte grafiek: Een ongerichte graaf wordt ook wel een tweerichtingsgrafiek genoemd. In ongerichte grafieken doet de richting van de randen er niet toe, en de verplaatsing kan in elke richting gaan.
- Gewogen grafiek: Een gewogen grafiek is een grafiek waarvan de knopen en randen een bijbehorende waarde hebben. In de meeste gevallen vertegenwoordigt deze waarde de kosten van het verkennen van dat knooppunt of die rand.
- Eindige grafiek: Een graaf met een eindig aantal knopen en randen.
- Oneindige grafiek: Een graaf met een oneindig aantal knopen en randen.
- Triviale grafiek: Een grafiek met slechts één knoop en geen rand.
- Eenvoudige grafiek: Wanneer slechts één rand elk paar knooppunten van een graaf verbindt, wordt dit een eenvoudige graaf genoemd.
- Null-grafiek: Een nulgrafiek is een graaf die geen randen heeft die de knooppunten met elkaar verbinden.
- Multigrafiek: In een multigraaf hebben ten minste een paar knooppunten meer dan één rand die ze verbindt. In multigraphs zijn er geen zelf-loops.
- Volledige grafiek: Een volledige graaf is een graaf waarin elk knooppunt aansluit op elk ander knooppunt in de graaf. Het is ook bekend als a volledige grafiek.
- Pseudo-grafiek: Een graaf die een zelflus heeft naast andere graafranden, wordt een pseudo-graaf genoemd.
- Regelmatige grafiek: Een gewone grafiek is een grafiek waarin alle knopen gelijke graden hebben; d.w.z. elk knooppunt heeft hetzelfde aantal buren.
- Verbonden grafiek: Een verbonden graaf is gewoon een graaf waarin twee willekeurige knooppunten met elkaar verbonden zijn; d.w.z. een grafiek met ten minste één pad tussen elke twee knooppunten van de grafiek.
- Losgekoppelde grafiek: Een niet-verbonden grafiek is het tegenovergestelde van een verbonden grafiek. In een niet-verbonden graaf zijn er geen randen die de knooppunten van de graaf met elkaar verbinden, zoals in a nul grafiek.
- Cyclische grafiek: Een cyclische grafiek is een grafiek die ten minste één grafiekcyclus bevat (een pad dat eindigt waar het begon).
- Acyclische grafiek: Een acyclische grafiek is een grafiek zonder cycli. Het kan zowel gericht als ongericht zijn.
- Subgraaf: Een subgraaf is een afgeleide grafiek. Het is een grafiek gevormd uit knopen en randen die deelverzamelingen zijn van een andere grafiek.
EEN lus in een graaf is een rand die begint bij een knoop en eindigt bij dezelfde knoop. Daarom, een zelf-loop is een lus over slechts één graafknooppunt, zoals te zien is in een pseudo-graaf.
Grafiektraversale algoritmen
Omdat het een soort niet-lineaire datastructuur is, is het doorlopen van een grafiek best lastig. Het doorkruisen van een grafiek betekent het doorlopen en verkennen van elk knooppunt, aangezien er een geldig pad door de randen is. Grafiektraversal-algoritmen zijn hoofdzakelijk van twee typen.
- Breedte-eerst zoeken (BFS): Breedte-eerst zoeken is een graaf-traversal-algoritme dat een grafiekknooppunt bezoekt en zijn buren verkent voordat het naar een van zijn onderliggende knooppunten gaat. Hoewel u kunt beginnen met het doorlopen van een grafiek vanaf elk geselecteerd knooppunt, hoofdknooppunt is meestal het gewenste startpunt.
- Diepte-eerst zoeken (DFS): Dit is het tweede grote algoritme voor het doorlopen van grafieken. Het bezoekt een graafknooppunt en verkent de onderliggende knooppunten of vertakkingen voordat het naar het volgende knooppunt gaat, dat wil zeggen eerst diep voordat het breed wordt.
Breedte-eerst zoeken is het aanbevolen algoritme om paden tussen twee knooppunten zo snel mogelijk te vinden, vooral het kortste pad.
Diepte-eerst zoeken wordt meestal aanbevolen als u elk knooppunt in de grafiek wilt bezoeken. Beide traversal-algoritmen werken in elk geval prima, maar de ene kan eenvoudiger en meer geoptimaliseerd zijn dan de andere in geselecteerde scenario's.
Een eenvoudige illustratie kan helpen om beide algoritmen beter te begrijpen. Beschouw de staten van een land als een grafiek en probeer te controleren of twee staten, X en Y, zijn verbonden. Een zoektocht op diepte kan bijna het hele land doorkruisen zonder dat je dat vroeg genoeg beseft Y is slechts 2 staten verwijderd van X.
Het voordeel van zoeken in de breedte is dat het zo dicht mogelijk bij het huidige knooppunt blijft voordat het naar het volgende gaat. Het zal de verbinding vinden tussen X en Y in korte tijd zonder het hele land te hoeven verkennen.
Een ander groot verschil tussen deze twee algoritmen is de manier waarop ze in code zijn geïmplementeerd. Breedte-eerst zoeken is een iteratief algoritme en maakt gebruik van een rij, terwijl een diepte-eerst zoeken meestal wordt uitgevoerd als een recursief algoritme dat maakt gebruik van de stapelen.
Hieronder vindt u enkele pseudocode die de implementatie van beide algoritmen demonstreert.
Breedte-eerst zoeken
bfs (Grafiek G, GraphNode root) {
laten q be nieuwe Rij// markeer root als bezocht
root.bezocht = WAAR// voeg root toe aan de wachtrij
q.in de wachtrij zetten(wortel)
terwijl (q is niet leeg) {
laten huidige be q.dequeue() // verwijder frontelement in de wachtrij
voor (buren n van stroom in G) {
als (n isniet nog bezocht) {
// voeg toe aan de wachtrij - zodat je ook de buren kunt verkennen
q.in de wachtrij zetten(n)
n.bezocht = WAAR
}
}
}
}
Diepte-eerst zoeken
dfs (Graph G, GraphNode root) {
// hoofdzaak
als (root is nul) opbrengst// markeer root als bezocht
root.bezocht = WAAR
voor (buren n van wortel in G)
als (n isniet nog bezocht)
dfs (G, n) // recursieve oproep
}
Een paar andere graph-traversal-algoritmen zijn afgeleid van breedte-eerst en diepte-eerst zoekopdrachten. De meest populaire zijn:
- Bidirectioneel zoeken: Dit algoritme is een geoptimaliseerde manier om het kortste pad tussen twee knooppunten te vinden. Het gebruikt twee breedte-eerste zoekopdrachten die botsen als er een pad is.
- Topologische sortering: Dit wordt gebruikt in gerichte grafieken om de knooppunten in de gewenste volgorde te sorteren. U kunt geen topologische sortering toepassen op ongerichte grafieken of grafieken met cycli.
- Dijkstra’s algoritme: Dit is ook een type BFS. Het wordt ook gebruikt om het kortste pad tussen twee knooppunten in a. te vinden gewogen gerichte grafiek, die cycli kunnen hebben of niet.
Veelvoorkomende sollicitatievragen op basis van grafieken
Grafieken behoren tot de belangrijkste datastructuren die elke programmeur zou moeten kennen. In technische interviews komen vaak vragen over dit onderwerp naar voren en u kunt enkele klassieke problemen tegenkomen die verband houden met het onderwerp. Deze omvatten zaken als de "stadsrechter", "aantal eilanden" en "reizende verkoper" -problemen.
Dit zijn slechts enkele van de vele populaire op grafieken gebaseerde interviewproblemen. Je kunt ze uitproberen op LeetCode, HackerRank, of GeeksforGeeks.
Grafiekgegevensstructuren en algoritmen begrijpen
Grafieken zijn niet alleen handig voor technische interviews. Ze hebben ook real-world use-cases, zoals in netwerken, kaarten, en luchtvaartsystemen voor het vinden van routes. Ze worden ook gebruikt in de onderliggende logica van computersystemen.
Grafieken zijn uitstekend geschikt voor het ordenen van gegevens en om ons te helpen bij het visualiseren van complexe problemen. Grafieken mogen echter alleen worden gebruikt wanneer dit absoluut noodzakelijk is, om ruimtecomplexiteit of geheugenproblemen te voorkomen.
