Grafiekgegevensstructuur en Algorithms (Voorbeeld)
Sara Chen
⚡ Slimme samenvatting
Een graafdatastructuur is een niet-lineaire verzameling van knooppunten en verbindingen, waarbij elke verbinding een paar knooppunten met elkaar verbindt. Grafen modelleren netwerken uit de echte wereld, zoals kaarten, sociale netwerken en webpagina's, en ondersteunen veel krachtige algoritmen.
Wat is een grafiek in de gegevensstructuur?
Een graaf is een niet-lineaire datastructuur die bestaat uit knooppunten en verbindingen, waarbij de knooppunten de informatie of gegevens bevatten en de verbindingen fungeren als een link tussen twee knooppunten.
Het wordt gebruikt om problemen uit de praktijk op te lossen, zoals het vinden van de beste route naar een bestemming en de routeplanning voor telecommunicatie en sociale netwerken. Gebruikers worden beschouwd als knooppunten in de grafiek en de draden zijn de randen die de gebruikers met elkaar verbinden.
Als randen worden weergegeven als E en hoekpunten worden weergegeven als V, dan kan de grafiek G worden geschreven als de verzameling hoekpunten en randen, zoals G (V, E).
Voorbeeld van grafiek in gegevensstructuur
Hier volgt een eenvoudig voorbeeld van een grafische datastructuur:
Het is een eenvoudige ongerichte graaf (een type graaf). De verzameling knooppunten is: {A, B, C, D, E, F}. Twee knooppunten vormen een verbinding. Bijvoorbeeld, A en B zijn met elkaar verbonden door een verbinding. A en F zijn echter niet met elkaar verbonden door een verbinding.
Grafiekterminologieën in de gegevensstructuur
Hieronder volgen enkele belangrijke termen die in de grafiekdatastructuur worden gebruikt:
| Termijn | Beschrijving |
|---|---|
| Toppunt | Elk gegevenselement wordt een knooppunt of vertex genoemd. In de bovenstaande afbeelding zijn A, B, C, D en E de knooppunten. |
| Rand (boog) | Verbindingen tussen twee knooppunten of hoekpunten worden een rand (boog) genoemd. Een boog heeft twee uiteinden en wordt weergegeven als (startpunt, eindpunt). |
| Ongerichte rand | Het is een bidirectionele rand. |
| Gerichte rand | Het is een unidirectionele rand. |
| Gewogen rand | Een rand met een waarde erop. |
| Mate | In een graaf wordt het aantal randen dat met een knooppunt verbonden is, de graad genoemd. |
| Ingraad | Het totale aantal inkomende flanken verbonden met een hoekpunt. |
| Hoger diploma | Het totale aantal uitgaande randen dat met een hoekpunt is verbonden. |
| Zelflus | Een rand wordt een zelflus genoemd als de twee eindpunten ervan samenvallen. |
| nabijheid | Hoekpunten worden als aangrenzend beschouwd als er een verbindingsrand tussen hen bestaat. |
Soorten grafieken in de gegevensstructuur
Hier is de lijst met de meest voorkomende soorten grafieken in de datastructuur:
- Gerichte grafiek
- Ongerichte grafiek
- Gewogen grafiek
- Bidirectionele grafiek
- Oneindige grafiek
- Nulgrafiek
- Triviale grafiek
- Multigrafiek
- Volledige grafiek
- Verbonden grafiek
- Cyclische grafiek
- Gerichte Acyclische Grafiek (DAG)
- Cyclusgrafiek
- Bipartiete grafiek
- Euler-grafiek
- Hamilton-grafiek
Hoe kun je een grafiek in een datastructuur weergeven?
Een grafiek wordt doorgaans in het geheugen opgeslagen met behulp van een van twee representaties. De keuze hiervan heeft invloed op hoeveel geheugen de grafiek gebruikt en hoe snel veelvoorkomende bewerkingen worden uitgevoerd.
- Aangrenzingsmatrix: Een tweedimensionale V × V matrix waarbij cel [i][j] 1 is (of het gewicht van de rand) als er een rand bestaat tussen knooppunt i en knooppunt j, en 0 anders. Het maakt O(1) randopzoeking mogelijk, maar gebruikt O(V²) ruimte, waardoor het het meest geschikt is voor dichte grafieken.
- Aangrenzende lijst: Een array van lijsten waarbij elk knooppunt een lijst van zijn buurknooppunten opslaat. Het gebruikt O(V + E) ruimte en is efficiënt voor dunne grafieken, daarom wordt het in de meeste grafieken uit de praktijk gebruikt.
Je kunt hier meer over lezen in de aangrenzingslijst en matrixrepresentatie van een graaf tutorial.
Toepassingen van grafiekgegevensstructuur
Een graaf kent vele toepassingen. Er zijn talloze algoritmen die gebruikmaken van grafen. Hier volgen enkele voorbeelden van toepassingen van grafen:
- Google Maps gebruikt grafieken om het snijpunt van twee wegen te vinden en de afstand tussen twee locaties te berekenen. Bijvoorbeeld: Dijkstra, om de kortste afstand tussen de bron- en bestemmingslocatie te vinden.
- Facebook gebruikt grafieken om de gemeenschappelijke vrienden van gebruikers te vinden. Het algoritme beschouwt elke gebruiker als een knooppunt in een grafiek.
- Voor de toewijzing van resources wordt een DAG (Directed Acyclic Graph) gebruikt. Deze controleert de onderlinge afhankelijkheid van de resources.
- De Google Zoekmachines gebruiken grafieken om de rangschikking van websites te bepalen.
- Een kaartping Het apparaat maakt gebruik van de grafische datastructuur.
- A router en het protocol ervan gebruikt de grafiek om het pad naar de bestemming te leren.
