En effektiv programmerare behöver en gedigen förståelse för datastrukturer och algoritmer. Tekniska intervjuer kommer ofta att testa dina färdigheter i problemlösning och kritiskt tänkande.
Grafer är en av många viktiga datastrukturer inom programmering. I de flesta fall är det inte lätt att förstå grafer och lösa grafbaserade problem.
Vad är en graf och vad behöver du veta om den?
Vad är en graf?
En graf är en icke-linjär datastruktur som har noder (eller hörn) med kanter som förbinder dem. Alla träd är undertyper av grafer, men inte alla grafer är träd, och grafen är den datastruktur som träden kommer från.
Fast man kan bygga datastrukturer i JavaScript och andra språk kan du implementera en graf på olika sätt. De mest populära metoderna är kantlistor, angränsande listor, och närliggande matriser.
De Khan Academy guide till att representera grafer är en utmärkt resurs för att lära dig hur man representerar en graf.
Det finns många olika typer av grafer. En vanlig skillnad är mellan riktad och oriktad grafer; dessa kommer upp mycket i kodningsutmaningar och verkliga användningar.
Typer av grafer
- Riktad graf: En graf där alla kanter har en riktning, även kallad digrafera.
- Oriktat diagram: En oriktad graf är också känd som en tvåvägsgraf. I oriktade grafer spelar kanternas riktning ingen roll, och korsningen kan gå i vilken riktning som helst.
- Viktad graf: En viktad graf är en graf vars noder och kanter har ett associerat värde. I de flesta fall representerar detta värde kostnaden för att utforska den noden eller kanten.
- Finit graf: En graf som har ett ändligt antal noder och kanter.
- Oändlig graf: En graf som har ett oändligt antal noder och kanter.
- Trivial graf: En graf som bara har en nod och ingen kant.
- Enkel graf: När endast en kant förbinder varje par av noderna i en graf, kallas det en enkel graf.
- Nulldiagram: En nollgraf är en graf som inte har några kanter som förbinder sina noder.
- Multigraf: I en multigraf har åtminstone ett par noder mer än en kant som förbinder dem. I multigrafer finns det inga självslingor.
- Komplett graf: En komplett graf är en graf där varje nod ansluter till varannan nod i grafen. Det är också känt som en hela grafen.
- Pseudograf: En graf som har en självslinga bortsett från andra grafkanter kallas en pseudograf.
- Vanlig graf: En vanlig graf är en graf där alla noder har samma grader; dvs varje nod har samma antal grannar.
- Ansluten graf: En sammankopplad graf är helt enkelt vilken graf som helst där två valfria noder ansluter; dvs en graf med minst en väg mellan varannan nod i grafen.
- Frånkopplad graf: En frånkopplad graf är raka motsatsen till en sammankopplad graf. I en frånkopplad graf finns det inga kanter som länkar samman grafens noder, till exempel i en null Graf.
- Cyklisk graf: En cyklisk graf är en graf som innehåller minst en grafcykel (en väg som slutar där den började).
- Acyklisk graf: En acyklisk graf är en graf utan cykler alls. Det kan antingen vara riktat eller oriktat.
- Subgraf: En subgraf är en härledd graf. Det är en graf som bildas av noder och kanter som är delmängder av en annan graf.
A slinga i en graf finns en kant som börjar från en nod och slutar vid samma nod. Därför, a självslinga är en slinga över endast en grafnod, som ses i en pseudograf.
Algoritmer för diagramgenomgång
Eftersom det är en typ av icke-linjär datastruktur är det ganska svårt att korsa en graf. Att korsa en graf innebär att gå igenom och utforska varje nod förutsatt att det finns en giltig väg genom kanterna. Graftraversalalgoritmer är huvudsakligen av två typer.
- Breadth-First Search (BFS): Bredd-först-sökning är en grafgenomgångsalgoritm som besöker en grafnod och utforskar dess grannar innan den går vidare till någon av dess undernoder. Även om du kan börja korsa en graf från valfri vald nod, rotnod är vanligtvis den föredragna utgångspunkten.
- Depth-First Search (DFS): Detta är den andra stora grafgenomgångsalgoritmen. Den besöker en grafnod och utforskar dess underordnade noder eller grenar innan den fortsätter till nästa nod – det vill säga går djupt först innan den går bred.
Bredd-först-sökning är den rekommenderade algoritmen för att hitta vägar mellan två noder så snabbt som möjligt, särskilt den kortaste vägen.
Djup-först-sökning rekommenderas oftast när du vill besöka varje nod i grafen. Båda traversalalgoritmerna fungerar bra i alla fall, men den ena kan vara enklare och mer optimerad än den andra i utvalda scenarier.
En enkel illustration kan hjälpa dig att förstå båda algoritmerna bättre. Se tillstånden i ett land som en graf och försök kontrollera om två stater, X och Y, är anslutna. Ett djup-först-sök kan gå på en stig nästan runt landet utan att inse det tillräckligt tidigt Y är bara 2 stater bort från X.
Fördelen med en bredd-först-sökning är att den bibehåller närhet till den aktuella noden så mycket som möjligt innan du går till nästa. Det kommer att hitta kopplingen mellan X och Y på kort tid utan att behöva utforska hela landet.
En annan stor skillnad mellan dessa två algoritmer är hur de implementeras i kod. Bredd-först sökning är en iterativ algoritm och använder sig av en kö, medan en djup-först-sökning vanligtvis implementeras som en rekursiv algoritm som utnyttjar stack.
Nedan finns en pseudokod som visar implementeringen av båda algoritmerna.
Utöka första sökningen
bfs (Graph G, GraphNode root) {
låta q vara ny Kö// markera root som besökt
root.visited = Sann// lägg till root i kön
q.enqueue(rot)
medan (q är inte tömma) {
låta aktuell vara q.dequeue() // ta bort frontelement i kön
för (grannar n av ström i G) {
om (n ärinte ännu besökt) {
// lägg till i kön - så att du kan utforska dess grannar också
q.enqueue(n)
n.besökt = Sann
}
}
}
}
Djup-första sökning
dfs (Graph G, GraphNode root) {
// basfallet
om (roten är null) lämna tillbaka// markera root som besökt
root.visited = Sann
för (grannar n av roten i G)
om (n ärinte ännu besökt)
dfs (G, n) // rekursivt anrop
}
Några andra graf-traversalalgoritmer härrör från sökningar med bredd-först och djup-först. De mest populära är:
- Dubbelriktad sökning: Denna algoritm är ett optimerat sätt att hitta den kortaste vägen mellan två noder. Den använder två sökningar på bredden först som kolliderar om det finns en väg.
- Topologisk sort: Detta används i riktade grafer för att sortera noderna i önskad ordning. Du kan inte tillämpa en topologisk sortering på oriktade grafer eller grafer med cykler.
- Dijkstras algoritm: Detta är också en typ av BFS. Den används också för att hitta den kortaste vägen mellan två noder i en vägd riktad graf, som kan ha cykler eller inte.
Vanliga intervjufrågor baserade på grafer
Grafer är bland de viktiga datastrukturer som varje programmerare bör känna till. Frågor kommer ofta upp om detta ämne i tekniska intervjuer, och du kan stöta på några klassiska problem relaterade till ämnet. Dessa inkluderar saker som "stadsdomaren", "antal öar" och problem med "resande försäljare".
Dessa är bara några av de många populära grafbaserade intervjuproblemen. Du kan prova dem LeetCode, HackerRank, eller GeeksforGeeks.
Förstå grafdatastrukturer och algoritmer
Grafer är inte bara användbara för tekniska intervjuer. De har också verkliga användningsfall, som i nätverk, kartor, och flygbolagssystem för att hitta vägar. De används också i datorsystemens underliggande logik.
Grafer är utmärkta för att organisera data och för att hjälpa oss att visualisera komplexa problem. Grafer bör dock endast användas när det är absolut nödvändigt för att förhindra utrymmeskomplexitet eller minnesproblem.