In deze zelfstudie leert u wat een grafiekgegevensstructuur is. Ook vindt u weergaven van een grafiek.
Een datastructuur van een grafiek is een verzameling knooppunten die gegevens hebben en zijn verbonden met andere knooppunten.
Laten we proberen dit aan de hand van een voorbeeld te begrijpen. Op Facebook is alles een knooppunt. Dat omvat Gebruiker, Foto, Album, Evenement, Groep, Pagina, Commentaar, Verhaal, Video, Link, Notitie… alles wat gegevens heeft is een knooppunt.
Elke relatie is een rand van het ene knooppunt naar het andere. Of je nu een foto plaatst, lid wordt van een groep, een pagina leuk vindt, enz., Er ontstaat een nieuw voordeel voor die relatie.
Voorbeeld van grafiekgegevensstructuur
Heel Facebook is dan een verzameling van deze knooppunten en randen. Dit komt omdat Facebook een grafische datastructuur gebruikt om zijn gegevens op te slaan.
Preciezer gezegd, een grafiek is een datastructuur (V, E) die bestaat uit
- Een verzameling hoekpunten V
- Een verzameling randen E, weergegeven als geordende paren hoekpunten (u, v)
Hoekpunten en randen
In de grafiek
V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)
Grafiekterminologie
- Nabijheid : er wordt gezegd dat een hoekpunt grenst aan een ander hoekpunt als er een rand is die ze verbindt. Hoekpunten 2 en 3 zijn niet aangrenzend omdat er geen rand tussen zit.
- Pad : een reeks randen waarmee u van hoekpunt A naar hoekpunt B kunt gaan, wordt een pad genoemd. 0-1, 1-2 en 0-2 zijn paden van hoekpunt 0 naar hoekpunt 2.
- Directed Graph : een grafiek waarin een rand (u, v) niet noodzakelijkerwijs betekent dat er ook een rand (v, u) is. De randen in zo'n grafiek worden weergegeven door pijlen om de richting van de rand aan te geven.
Grafische weergave
Grafieken worden gewoonlijk op twee manieren weergegeven:
1. Nabijheidsmatrix
Een aangrenzende matrix is een 2D-array van V x V-hoekpunten. Elke rij en kolom vertegenwoordigen een hoekpunt.
Als de waarde van een element a(i)(j)1 is, geeft dit aan dat er een rand is die hoekpunt i en hoekpunt j verbindt.
De aangrenzende matrix voor de grafiek die we hierboven hebben gemaakt, is
Grafiek aangrenzende matrix
Omdat het een ongerichte graaf is, moeten we voor rand (0,2) ook rand (2,0) markeren; het maken van de aangrenzende matrix symmetrisch rond de diagonaal.
Randopzoeken (controleren of er een rand bestaat tussen hoekpunt A en hoekpunt B) is extreem snel in aangrenzende matrixweergave, maar we moeten ruimte reserveren voor elke mogelijke link tussen alle hoekpunten (V x V), dus het vereist meer ruimte.
2. Nabijheidslijst
Een aangrenzende lijst vertegenwoordigt een grafiek als een reeks gekoppelde lijsten.
De index van de array vertegenwoordigt een hoekpunt en elk element in de gekoppelde lijst vertegenwoordigt de andere hoekpunten die een rand vormen met het hoekpunt.
De aangrenzende lijst voor de grafiek die we in het eerste voorbeeld hebben gemaakt, is als volgt:
Weergave van aangrenzende lijst
Een aangrenzende lijst is efficiënt in termen van opslag omdat we alleen de waarden voor de randen hoeven op te slaan. Voor een grafiek met miljoenen hoekpunten kan dit veel besparing betekenen.
Grafiekbewerkingen
De meest voorkomende grafiekbewerkingen zijn:
- Controleer of het element aanwezig is in de grafiek
- Graph Traversal
- Voeg elementen (hoekpunt, randen) toe aan de grafiek
- Het pad van het ene hoekpunt naar het andere vinden
