Grafiekgegevensstructuur en Algorithms (Voorbeeld)
Sara Chen
Wat is een grafiek in de gegevensstructuur?
Een grafiek is een niet-lineaire gegevensstructuur die bestaat uit hoekpunten en randen, waarbij hoekpunten de informatie of gegevens bevatten, en de randen werken als een link tussen paar hoekpunten.
Het wordt gebruikt om echte woordproblemen op te lossen, zoals het vinden van de beste route naar de bestemmingslocatie en de route voor telecommunicatie en sociale netwerken. Gebruikers worden beschouwd als een knooppunt in de grafiek en de draden zijn de randen die de gebruikers 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 is een eenvoudig voorbeeld van de structuur van grafiekgegevens:
Het is een eenvoudige, ongerichte grafiek (één soort grafiek). Hier is de set hoekpunten: {A, B, C,D,E,F}. Twee hoekpunten creëren een rand. A en B zijn bijvoorbeeld verbonden met een rand. A en F zijn echter niet met randen verbonden.
Grafiekterminologieën in de gegevensstructuur
Hieronder staan enkele belangrijke termen die in de grafische datastructuur worden gebruikt:
| Termijn | Beschrijving |
|---|---|
| Toppunt | Alle gegevenselementen worden een hoekpunt of een knooppunt genoemd. In de bovenstaande afbeelding zijn A, B, C, D en E de hoekpunten. |
| Rand (boog) | Verbindingsverbindingen tussen twee knooppunten of hoekpunten worden rand (Arc) genoemd. Het heeft twee uiteinden en wordt weergegeven als (startpuntVertex, eindigendVertex). |
| Ongerichte rand | Het is een bidirectionele rand. |
| Gerichte rand | Het is een unidirectionele rand. |
| Gewogen rand | Een rand met waarde erop. |
| Mate | In Graph wordt het aantal randen dat met een hoekpunt is verbonden een 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 | Er wordt gezegd dat hoekpunten aangrenzend zijn als een rand is verbonden. |
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
Toepassingen van grafiekgegevensstructuur
Een grafiek heeft veel use cases. Er zijn veel algoritmes die grafieken veel gebruiken. Hier zijn enkele toepassingen van de grafiek:
- Google Maps gebruikt grafieken om het snijpunt van twee wegen te vinden en de afstand tussen twee locaties te berekenen.
Bijvoorbeeld Dijkstra, voor het vinden van de kortste afstand tussen bron- en bestemmingslocatie. - Facebook gebruikt Grafieken om de gemeenschappelijke vriend van de gebruikers te vinden. Het algoritme beschouwt elke gebruiker als een knooppunt van een grafiek.
- Voor de toewijzing van hulpbronnen wordt DAG (Direct Acyclic Graph) gebruikt. Het controleert de afhankelijkheid van de bronnen.
- Google Search Engine gebruikt grafieken om de ranking voor websites te bepalen.
- Een kaartapparaat gebruikt de grafiekgegevensstructuur.
- router en het protocol van t gebruikt de grafiek om het pad van het bestemmingspad te leren.
