graph implementation c using adjacency list
Deze tutorial legt de implementatie van grafieken in C ++ uit. U leert ook over verschillende typen, weergaven en toepassingen van grafieken:
Een grafiek is een niet-lineaire gegevensstructuur. Een graaf kan worden gedefinieerd als een verzameling knooppunten die ook wel 'hoekpunten' en 'randen' worden genoemd die twee of meer hoekpunten verbinden.
Een graaf kan ook worden gezien als een cyclische boom waarin hoekpunten geen ouder-kindrelatie hebben, maar een complexe relatie tussen hen onderhouden.
software development engineer in test interviewvragen
Klik hier voor de Absolute C ++ trainingsserie.
Wat je leert:
Wat is een grafiek in C ++?
Zoals hierboven vermeld, is een grafiek in C ++ een niet-lineaire gegevensstructuur die wordt gedefinieerd als een verzameling hoekpunten en randen.
Hieronder volgt een voorbeeld van een datastructuur van een grafiek.
Hierboven is een voorbeeldgrafiek G gegeven. Grafiek G is een set hoekpunten {A, B, C, D, E} en een set randen {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Soorten grafieken - Gerichte en niet-gerichte grafiek
Een grafiek waarin de randen geen richtingen hebben, wordt de niet-gerichte grafiek genoemd. De bovenstaande grafiek is een ongerichte grafiek.
Een grafiek waarin de randen een bijbehorende richting hebben, wordt een gerichte grafiek genoemd.
Hieronder wordt een voorbeeld gegeven van een gerichte grafiek.
In de hierboven getoonde gerichte grafiek vormen randen een geordend paar waarbij elke rand een specifiek pad van het ene hoekpunt naar het andere hoekpunt vertegenwoordigt. Het hoekpunt van waaruit het pad begint, wordt ' Eerste knooppunt 'Terwijl het hoekpunt waarin het pad eindigt de' Eindknooppunt
Dus in bovenstaande grafiek is de set hoekpunten {A, B, C, D, E} en de set randen is {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.
We zullen de grafiekterminologie of de veelgebruikte termen in relatie tot de onderstaande grafiek bespreken.
Grafiekterminologie
- Hoekpunt: Elk knooppunt van de grafiek wordt een hoekpunt genoemd. In de bovenstaande grafiek zijn A, B, C en D de hoekpunten van de grafiek.
- Rand: De verbinding of het pad tussen twee hoekpunten wordt een rand genoemd. Het verbindt twee of meer hoekpunten. De verschillende randen in de bovenstaande grafiek zijn AB, BC, AD en DC.
- Aangrenzende knoop: Als in een grafiek twee knooppunten zijn verbonden door een rand, worden ze aangrenzende knooppunten of buren genoemd. In de bovenstaande grafiek zijn hoekpunten A en B verbonden door rand AB. A en B zijn dus aangrenzende knooppunten.
- Mate van het knooppunt: Het aantal randen dat met een bepaald knooppunt is verbonden, wordt de graad van het knooppunt genoemd. In de bovenstaande grafiek heeft knooppunt A een graad 2.
- Pad: De volgorde van knooppunten die we moeten volgen als we in een grafiek van het ene hoekpunt naar het andere moeten reizen, wordt het pad genoemd. Als we in onze voorbeeldgrafiek van knooppunt A naar C moeten gaan, zou het pad A-> B-> C zijn.
- Gesloten pad: Als het eerste knooppunt hetzelfde is als een eindknooppunt, wordt dat pad het gesloten pad genoemd.
- Eenvoudig pad: Een gesloten pad waarin alle andere knooppunten verschillend zijn, wordt een eenvoudig pad genoemd.
- Fiets: Een pad waarin er geen herhaalde randen of hoekpunten zijn en de eerste en laatste hoekpunten hetzelfde zijn, wordt een cyclus genoemd. In de bovenstaande grafiek is A-> B-> C-> D-> A een cyclus.
- Verbonden grafiek: Een verbonden graaf is degene waarin er een pad is tussen elk van de hoekpunten. Dit betekent dat er geen enkel hoekpunt is dat geïsoleerd is of zonder een verbindingsrand. De bovenstaande grafiek is een verbonden grafiek.
- Volledige grafiek: Een grafiek waarin elk knooppunt met een ander is verbonden, wordt de volledige grafiek genoemd. Als N het totale aantal knooppunten in een grafiek is, dan bevat de volledige grafiek N (N-1) / 2 aantal randen.
- Gewogen grafiek: Een positieve waarde toegewezen aan elke rand die de lengte aangeeft (afstand tussen de hoekpunten verbonden door een rand) wordt gewicht genoemd. De grafiek met gewogen randen wordt een gewogen grafiek genoemd. Het gewicht van een rand e wordt aangegeven met w (e) en geeft de kosten aan van het doorkruisen van een rand.
- Diagraph: Een digraph is een grafiek waarin elke rand is geassocieerd met een specifieke richting en de verplaatsing alleen in een bepaalde richting kan worden gedaan.
Grafische weergave
De manier waarop de datastructuur van de grafiek in het geheugen wordt opgeslagen, wordt 'representatie' genoemd. De grafiek kan worden opgeslagen als een sequentiële weergave of als een gekoppelde weergave.
Beide typen worden hieronder beschreven.
Sequentiële vertegenwoordiging
Bij de opeenvolgende weergave van grafieken gebruiken we de aangrenzende matrix. Een aangrenzende matrix is een matrix van afmeting n x n waarbij n het aantal hoekpunten in de grafiek is.
De rijen en kolommen van de aangrenzende matrix vertegenwoordigen de hoekpunten in een grafiek. Het matrixelement wordt op 1 gezet als er een rand aanwezig is tussen de hoekpunten. Als de rand niet aanwezig is, wordt het element op 0 gezet.
Hieronder ziet u een voorbeeldgrafiek die de aangrenzende matrix laat zien.
We hebben de aangrenzende matrix voor de bovenstaande grafiek gezien. Merk op dat aangezien dit een ongerichte grafiek is, en we kunnen zeggen dat de rand in beide richtingen aanwezig is. Bijvoorbeeld, aangezien rand AB aanwezig is, kunnen we concluderen dat rand BA ook aanwezig is.
In de aangrenzende matrix kunnen we de interacties zien van de hoekpunten die matrixelementen zijn die worden ingesteld op 1 wanneer de rand aanwezig is en op 0 wanneer de rand afwezig is.
Laten we nu de aangrenzende matrix van een gerichte grafiek bekijken.
Zoals hierboven getoond, zal het snijpuntelement in de aangrenzende matrix 1 zijn als en slechts als er een rand is gericht van het ene hoekpunt naar het andere.
In de bovenstaande grafiek hebben we twee randen vanaf hoekpunt A.Een rand eindigt in hoekpunt B, terwijl de tweede eindigt in hoekpunt C.Dus in de aangrenzende matrix wordt het snijpunt van A en B ingesteld op 1 als het snijpunt van A en C.
Vervolgens zien we de sequentiële weergave voor de gewogen grafiek.
Hieronder is de gewogen grafiek en de bijbehorende aangrenzende matrix weergegeven.
We kunnen zien dat de sequentiële weergave van een gewogen grafiek verschilt van de andere soorten grafieken. Hier worden de niet-nulwaarden in de aangrenzende matrix vervangen door het werkelijke gewicht van de rand.
De rand AB heeft gewicht = 4, dus in de aangrenzende matrix stellen we het snijpunt van A en B in op 4. Op dezelfde manier worden alle andere niet-nulwaarden gewijzigd in hun respectievelijke gewichten.
De aangrenzende lijst is gemakkelijker te implementeren en te volgen. Traversal, d.w.z. om te controleren of er een rand is van het ene hoekpunt naar het andere, kost O (1) tijd en het verwijderen van een rand kost ook O (1).
Of de grafiek nu schaars (minder randen) of compact is, hij neemt altijd meer ruimte in beslag.
Gekoppelde vertegenwoordiging
Voor de gekoppelde weergave van de grafiek gebruiken we de aangrenzende lijst. De weergave van de aangrenzende lijst behoudt elk knooppunt van de grafiek en een link naar de knooppunten die aan dit knooppunt grenzen. Wanneer we alle aangrenzende knooppunten doorkruisen, zetten we de volgende aanwijzer op nul aan het einde van de lijst.
Laten we eerst eens kijken naar een niet-gerichte grafiek en zijn aangrenzende lijst.
Zoals hierboven weergegeven, hebben we een gekoppelde lijst (aangrenzende lijst) voor elk knooppunt. Van hoekpunt A hebben we randen naar hoekpunten B, C en D. Deze knooppunten zijn dus verbonden met knooppunt A in de corresponderende aangrenzende lijst.
Vervolgens stellen we een aangrenzende lijst op voor de gerichte graaf.
In de hierboven gerichte grafiek zien we dat er geen randen zijn die afkomstig zijn van hoekpunt E. Daarom is de aangrenzende lijst voor hoekpunt E leeg.
gratis online test voor handmatig testen
Laten we nu de aangrenzende lijst voor de gewogen grafiek samenstellen.
Voor een gewogen grafiek voegen we een extra veld toe aan het knooppunt van de aangrenzende lijst om het gewicht van de rand aan te geven, zoals hierboven weergegeven.
Het toevoegen van een hoekpunt in de aangrenzende lijst is eenvoudiger. Het bespaart ook ruimte door de implementatie van de gekoppelde lijst. Als we moeten weten of er een rand is tussen het ene hoekpunt en het andere, is de bewerking niet efficiënt.
Basisbewerkingen voor grafieken
Hieronder volgen de basisbewerkingen die we kunnen uitvoeren op de datastructuur van de grafiek:
- Voeg een hoekpunt toe: Voegt een hoekpunt toe aan de grafiek.
- Voeg een rand toe: Voegt een rand toe tussen de twee hoekpunten van een grafiek.
- Geef de hoekpunten van de grafiek weer: Geef de hoekpunten van een grafiek weer.
C ++ Graph-implementatie met behulp van de aangrenzende lijst
Nu presenteren we een C ++ -implementatie om een eenvoudige grafiek te demonstreren met behulp van de aangrenzende lijst.
Hier gaan we de aangrenzende lijst weergeven voor een gewogen gerichte grafiek. We hebben twee structuren gebruikt om de aangrenzende lijst en randen van de grafiek vast te houden. De aangrenzende lijst wordt weergegeven als (start_vertex, end_vertex, weight).
Het C ++ -programma is als volgt:
Uitgang:
Uitgang:
Grafiek aangrenzende lijst
(start_vertex, end_vertex, gewicht):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Toepassingen van grafieken
Laten we enkele toepassingen van grafieken bespreken.
- Grafieken worden op grote schaal gebruikt in de informatica om netwerkgrafieken of semantische grafieken weer te geven of zelfs om de stroom van berekeningen weer te geven.
- Grafieken worden veel gebruikt in Compilers om de toewijzing van bronnen aan processen weer te geven of om gegevensstroomanalyse aan te geven, enz.
- Grafieken worden ook gebruikt voor het optimaliseren van zoekopdrachten in databasetalen in sommige gespecialiseerde compilers.
- Op sociale netwerksites zijn grafieken de belangrijkste structuren om het netwerk van mensen weer te geven.
- Grafieken worden op grote schaal gebruikt om het transportsysteem op te bouwen, met name het wegennet. Een populair voorbeeld is Google maps die uitgebreid gebruik maakt van grafieken om overal ter wereld richtingen aan te geven.
Gevolgtrekking
Een grafiek is een populaire en veel gebruikte datastructuur die, afgezien van andere velden, vele toepassingen heeft op het gebied van informatica. Grafieken bestaan uit hoekpunten en randen die twee of meer hoekpunten met elkaar verbinden.
Een grafiek kan worden gericht of ongericht. We kunnen grafieken weergeven met behulp van een aangrenzende matrix, die een lineaire weergave is, en met behulp van een aangrenzende gekoppelde lijst. In deze tutorial hebben we ook de implementatie van de grafiek besproken.
Zie hier om de volledige lijst met C ++ - zelfstudies te verkennen.
Aanbevolen literatuur
- Python Advanced List-zelfstudie (lijst sorteren, omkeren, indexeren, kopiëren, samenvoegen, optellen)
- Python-lijst - Elementen maken, openen, segmenteren, toevoegen of verwijderen
- Lijst met standaard IP-adressen van router voor veelgebruikte merken draadloze router
- 12 beste tools voor het maken van lijngrafieken voor het maken van verbluffende lijngrafieken [2021 RANKINGS]
- Standaard aanmeldingswachtwoord voor router voor de beste routermodellen (2021-lijst)
- Gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Circulaire gekoppelde lijstgegevensstructuur in C ++ met illustratie
- Dubbel gekoppelde lijstgegevensstructuur in C ++ met illustratie