En guide til grafdatastrukturen

En guide til grafdatastrukturen

En effektiv programmør har brug for en solid forståelse af datastrukturer og algoritmer. Tekniske interviews vil ofte teste dine problemløsnings- og kritiske tænkningsevner.





Grafer er en af ​​de mange vigtige datastrukturer i programmering. I de fleste tilfælde er det ikke let at forstå grafer og løse grafbaserede problemer.



MAKEUSE AF DAGENS VIDEO

Hvad er en graf, og hvad skal du vide om den?





Hvad er en graf?

En graf er en ikke-lineær datastruktur, der har noder (eller toppunkter) med kanter, der forbinder dem. Alle træer er undertyper af grafer, men ikke alle grafer er træer, og grafen er den datastruktur, som træer stammer fra.

Visuel gengivelse af en graf

Selvom du kan opbygge datastrukturer i JavaScript og andre sprog, kan du implementere en graf på forskellige måder. De mest populære tilgange er kantlister , tilgrænsende lister , og tilstødende matricer .



Det Khan Academy guide til at repræsentere grafer er en fantastisk ressource til at lære om, hvordan man repræsenterer en graf.

Der er mange forskellige typer grafer. En fælles forskel er mellem instrueret og urettet grafer; disse kommer meget op i kodningsudfordringer og brug i det virkelige liv.



Typer af grafer

  1. Instrueret graf: En graf, hvor alle kanter har en retning, også kaldet digraf. En rettet graf
  2. Urettet graf: En urettet graf er også kendt som en to-vejs graf. I urettede grafer betyder retningen af ​​kanterne ikke noget, og traversering kan gå i alle retninger.
  3. Vægtet graf: En vægtet graf er en graf, hvis noder og kanter har en tilknyttet værdi. I de fleste tilfælde repræsenterer denne værdi omkostningerne ved at udforske den pågældende node eller kant.
  4. Endelig graf: En graf, der har et begrænset antal noder og kanter.
  5. Uendelig graf: En graf, der har en uendelig mængde af noder og kanter.
  6. Triviel graf: En graf, der kun har én knude og ingen kant.
  7. Simpel graf: Når kun én kant forbinder hvert par af knudepunkter i en graf, kaldes det en simpel graf.
  8. Nul graf: En nul-graf er en graf, der ikke har nogen kanter, der forbinder dens noder.
  9. Multigraf: I en multigraf har mindst et par noder mere end én kant, der forbinder dem. I multigrafer er der ingen selvløkker.
  10. Komplet graf: En komplet graf er en graf, hvor hver knude forbindes med hver anden knude i grafen. Det er også kendt som en fuld graf .
  11. Pseudograf: En graf, der har en selvløkke bortset fra andre grafkanter, kaldes en pseudograf.
  12. Almindelig graf: En almindelig graf er en graf, hvor alle noder har lige store grader; dvs. hver node har det samme antal naboer.
  13. Forbundet graf: En forbundet graf er simpelthen en hvilken som helst graf, hvori to knudepunkter forbindes; dvs. en graf med mindst én vej mellem hver to knudepunkter i grafen.
  14. Afbrudt graf: En afbrudt graf er det direkte modsatte af en forbundet graf. I en afbrudt graf er der ingen kanter, der forbinder grafens noder, såsom i en nul kurve.
  15. Cyklisk graf: En cyklisk graf er en graf, der indeholder mindst én grafcyklus (en sti, der slutter, hvor den startede).
  16. Acyklisk graf: En acyklisk graf er en graf uden cyklusser overhovedet. Den kan enten være instrueret eller uinstrueret.
  17. Undergrafik: En undergraf er en afledt graf. Det er en graf, der er dannet af noder og kanter, der er delmængder af en anden graf.