Menu

Implementácia grafov v C ++ pomocou zoznamu susedov

  • Hlavná
  • Iné
  • Implementácia grafov v C ++ pomocou zoznamu susedov

graph implementation c using adjacency list

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento výukový program vysvetľuje implementáciu grafov v C ++. Dozviete sa tiež o rôznych typoch, znázorneniach a aplikáciách grafov:

Graf je nelineárna dátová štruktúra. Graf možno definovať ako súbor uzlov, ktoré sa tiež nazývajú „vrcholy“ a „hrany“, ktoré spájajú dva alebo viac vrcholov.

Graf možno považovať aj za cyklický strom, v ktorom vrcholy nemajú vzťah rodič - dieťa, ale udržiavajú medzi nimi komplexný vzťah.

ako vytvoriť všeobecné pole v jave

=> Kliknutím sem zobrazíte sériu školení Absolute C ++.

Graf dátovej štruktúry C ++

Čo sa dozviete:

Čo je graf v C ++?

Ako už bolo uvedené vyššie, graf v jazyku C ++ je nelineárna dátová štruktúra definovaná ako súbor vrcholov a hrán.

Nasleduje príklad dátovej štruktúry grafu.

Ukážka dátovej štruktúry grafu

Vyššie je uvedený príklad grafu G. Graf G je množina vrcholov {A, B, C, D, E} a množina hrán {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.

Typy grafov - smerovaný a neorientovaný graf

Graf, v ktorom hrany nemajú smery, sa nazýva Neurčený graf. Vyššie uvedený graf je neorientovaný graf.

Graf, v ktorom majú hrany spojené smery, sa nazýva Directed graph.

Ďalej je uvedený príklad smerovaného grafu.

2. príklad riadeného grafu

V riadenom grafe zobrazenom vyššie tvoria hrany usporiadanú dvojicu, pričom každá hrana predstavuje konkrétnu cestu z jedného vrcholu do druhého. Vrchol, z ktorého cesta iniciuje, sa nazýva „ Počiatočný uzol „Zatiaľ čo vrchol, do ktorého cesta končí, sa nazýva„ Uzol terminálu “.

Vo vyššie uvedenom grafe je teda sada vrcholov {A, B, C, D, E} a sada hrán {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.

Budeme diskutovať o terminológii grafov alebo o bežných termínoch používaných v súvislosti s grafom uvedeným nižšie.

Terminológia grafov

Terminológia grafov

  1. Vrchol: Každý uzol grafu sa nazýva vrchol. Vo vyššie uvedenom grafe sú A, B, C a D vrcholy grafu.
  2. Hrana: Spojnica alebo cesta medzi dvoma vrcholmi sa nazýva hrana. Spája dva alebo viac vrcholov. Rôzne hrany vo vyššie uvedenom grafe sú AB, BC, AD a DC.
  3. Susedný uzol: Ak sú v grafe dva uzly spojené hranou, potom sa nazývajú susedné uzly alebo susedia. Vo vyššie uvedenom grafe sú vrcholy A a B spojené hranou AB. A a B sú teda susedné uzly.
  4. Stupeň uzla: Počet hrán, ktoré sú spojené s konkrétnym uzlom, sa nazýva stupeň uzla. Na vyššie uvedenom grafe má uzol A stupeň 2.
  5. Cesta: Postupnosť uzlov, ktorú musíme sledovať, keď máme v grafe prechádzať z jedného vrcholu do druhého, sa nazýva cesta. V našom príklade grafu, ak potrebujeme prejsť z uzla A do C, potom bude cesta A-> B-> C.
  6. Uzavretá cesta: Ak je počiatočný uzol rovnaký ako koncový uzol, potom sa táto cesta nazýva uzavretá cesta.
  7. Jednoduchá cesta: Uzavretá cesta, v ktorej sú všetky ostatné uzly odlišné, sa nazýva jednoduchá cesta.
  8. Cyklus: Cesta, v ktorej neexistujú opakované hrany alebo vrcholy a prvý a posledný vrchol sú rovnaké, sa nazýva cyklus. Vo vyššie uvedenom grafe je A-> B-> C-> D-> A cyklus.
  9. Prepojený graf: Prepojený graf je ten, v ktorom je cesta medzi každým z vrcholov. To znamená, že neexistuje jediný vrchol, ktorý je izolovaný alebo bez spojovacej hrany. Graf zobrazený vyššie je prepojeným grafom.
  10. Kompletný graf: Graf, v ktorom je každý uzol spojený s iným, sa nazýva Kompletný graf. Ak N je celkový počet uzlov v grafe, potom celý graf obsahuje N (N-1) / 2 počet hrán.
  11. Vážený graf: Kladná hodnota priradená každej hrane označujúca jej dĺžku (vzdialenosť medzi vrcholmi spojenými hranou) sa nazýva váha. Graf obsahujúci vážené hrany sa nazýva vážený graf. Hmotnosť hrany e je označená symbolom w (e) a označuje cenu prechodu hranou.
  12. Diagraf: Digraf je graf, v ktorom je každá hrana spojená s konkrétnym smerom a prechod je možné vykonať iba v určenom smere.

Grafové znázornenie

Spôsob, akým sa dátová štruktúra grafu ukladá do pamäte, sa nazýva „reprezentácia“. Graf je možné uložiť ako postupné znázornenie alebo ako prepojené znázornenie.

Oba tieto typy sú opísané nižšie.

Postupné zastúpenie

Pri postupnom znázornení grafov použijeme maticu susednosti. Matica susednosti je matica veľkosti n x n, kde n je počet vrcholov v grafe.

Riadky a stĺpce matice susedstva predstavujú vrcholy v grafe. Maticový prvok je nastavený na 1, ak je medzi vrcholmi hrana. Ak hrana nie je, potom je prvok nastavený na 0.

Ďalej je uvedený príklad grafu, ktorý zobrazuje maticu susednosti.

Matica susednosti v sekvenčnom znázornení

Videli sme maticu susednosti pre vyššie uvedený graf. Upozorňujeme, že toto je neorientovaný graf a môžeme povedať, že hrana je prítomná v oboch smeroch. Napríklad, keď je prítomná hrana AB, môžeme usúdiť, že je prítomná aj hrana BA.

V matici susedstva môžeme vidieť interakcie vrcholov, ktoré sú prvkami matice, ktoré sú nastavené na 1, kedykoľvek je hrana prítomná, a na 0, keď hrana chýba.

Teraz si pozrime maticu susednosti smerovaného grafu.

Usmernený graf v sekvenčnom znázornení

Ako je uvedené vyššie, prienikový prvok v matici susedstva bude 1 práve vtedy, ak existuje hrana smerovaná z jedného vrcholu do druhého.

Vo vyššie uvedenom grafe máme dve hrany od vrcholu A. Jedna hrana končí na vrchole B, zatiaľ čo druhá končí na vrchole C. Teda v matici susednosti je priesečník A & B nastavený na 1 ako priesečník A & C.

Ďalej uvidíme postupné znázornenie váženého grafu.

Ďalej je uvedený vážený graf a zodpovedajúca matica susednosti.

Vážený graf a jeho matica susednosti

Vidíme, že postupné znázornenie váženého grafu sa líši od ostatných typov grafov. Tu sa nenulové hodnoty v matici susedstva nahradia skutočnou hmotnosťou okraja.

Hrana AB má hmotnosť = 4, takže v matici susednosti nastavíme priesečník A a B na 4. Podobne sa všetky ostatné nenulové hodnoty zmenia na svoje príslušné váhy.

Zoznam susedstiev sa ľahšie implementuje a dodržiava. Traversal, tj. Skontrolovať, či existuje hrana z jedného vrcholu do druhého, trvá O (1) a odstránenie hrany tiež trvá O (1).

Či už je graf rozptýlený (menej hrán) alebo hustý, vždy trvá viac miesta.

Prepojené zastúpenie

Zoznam prepojenosti používame pre prepojené znázornenie grafu. Reprezentácia zoznamu susedov zachováva každý uzol grafu a odkaz na uzly, ktoré susedia s týmto uzlom. Keď prechádzame všetkými susednými uzlami, nastavíme ďalší ukazovateľ na nulu na konci zoznamu.

Najprv zvážime neusmernený graf a jeho zoznam susedných práv.

neorientovaný graf a zoznam jeho susedov

Ako je uvedené vyššie, pre každý uzol máme prepojený zoznam (zoznam susedov). Od vrcholu A máme hrany až vrcholy B, C a D. Tieto uzly sú teda spojené s uzlom A v príslušnom zozname susednosti.

Ďalej zostavíme zoznam susedných vzťahov pre smerovaný graf.

Zoznam susedstiev pre smerovaný graf

Vo vyššie nasmerovanom grafe vidíme, že neexistujú žiadne hrany pochádzajúce z vrcholu E. Zoznam susedov pre vrchol E je teda prázdny.

Teraz vytvorme zoznam susedných vzťahov pre vážený graf.

Zoznam susedov pre vážený graf

Pre vážený graf pridáme ďalšie pole do uzla zoznamu susedov, aby sme označili váhu okraja, ako je uvedené vyššie.

Pridanie vrcholu do zoznamu susedov je jednoduchšie. Šetrí to tiež miesto kvôli implementácii prepojeného zoznamu. Keď potrebujeme zistiť, či existuje hrana medzi jednotlivými vrcholmi, nie je operácia efektívna.

Základné operácie s grafmi

Nasledujú základné operácie, ktoré môžeme vykonať s dátovou štruktúrou grafu:

  • Pridajte vrchol: Pridá vrchol do grafu.
  • Pridajte okraj: Pridá hranu medzi dva vrcholy grafu.
  • Zobraziť vrcholy grafu: Zobraziť vrcholy grafu.

Implementácia grafov v C ++ pomocou zoznamu susedných vzťahov

Teraz uvádzame implementáciu C ++ na demonštráciu jednoduchého grafu pomocou zoznamu susedných práv.

Tu zobrazíme zoznam susedstiev pre vážený smerovaný graf. Použili sme dve štruktúry, ktoré držia zoznam susedov a okraje grafu. Zoznam susedstiev je zobrazený ako (start_vertex, end_vertex, váha).

Program C ++ je nasledovný:

jednoduchý java program na triedenie čísel vzostupne
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i

Výkon:

Výkon:

Zoznam susedných grafov

(start_vertex, end_vertex, váha):

(0, 2, 4) (0, 1, 2)

(1, 4, 3)

(2, 3, 2)

(3, 1, 4)

(4, 3, 3)

Grafický výstup

Aplikácie grafov

Poďme diskutovať o niektorých aplikáciách grafov.

  • Grafy sa vo výpočtovej technike vo veľkej miere používajú na zobrazovanie sieťových grafov alebo sémantických grafov alebo dokonca na znázornenie toku výpočtov.
  • Grafy sa v kompilátoroch často používajú na zobrazenie alokácie zdrojov procesom alebo na indikáciu analýzy toku údajov atď.
  • Grafy sa tiež používajú na optimalizáciu dotazov v databázových jazykoch v niektorých špecializovaných prekladačoch.
  • Na stránkach sociálnych sietí sú hlavnými štruktúrami, ktoré znázorňujú sieť ľudí, grafy.
  • Grafy sa vo veľkej miere používajú na stavbu dopravného systému, najmä cestnej siete. Populárnym príkladom sú mapy Google, ktoré vo veľkej miere používajú grafy na označenie smerov po celom svete.

Záver

Graf je populárna a hojne využívaná dátová štruktúra, ktorá má okrem iných oblastí aj veľa aplikácií v samotnej oblasti informatiky. Grafy pozostávajú z vrcholov a hrán spájajúcich dva alebo viac vrcholov.

Graf môže byť nasmerovaný alebo neusmernený. Grafy môžeme reprezentovať pomocou matice susednosti, ktorá je lineárnou reprezentáciou, ako aj pomocou zoznamu prepojených susedstiev. V tomto výučbe sme tiež diskutovali o implementácii grafu.

=> Ak chcete preskúmať celý zoznam výukových programov C ++, prečítajte si tu.

Odporúčané čítanie

^