graph implementation c using adjacency list
Ovaj vodič objašnjava implementaciju grafikona u C ++. Također ćete naučiti o različitim vrstama, prikazima i primjeni grafikona:
Graf je nelinearna struktura podataka. Graf se može definirati kao zbirka Čvorova koji se nazivaju i 'vrhovi' i 'rubovi' koji povezuju dva ili više vrhova.
Graf se može vidjeti i kao ciklično stablo gdje vrhovi nemaju odnos roditelja i djeteta, ali održavaju složeni odnos među njima.
dvostruko povezana lista c ++ implementacija
=> Kliknite ovdje za apsolutnu seriju C ++ treninga.
Što ćete naučiti:
Što je graf na C ++-u?
Kao što je gore rečeno, graf u C ++-u je nelinearna struktura podataka definirana kao zbirka vrhova i bridova.
Slijedi primjer strukture podataka grafa.
Dati gore nalazi se primjer grafa G. Grafikon G je skup vrhova {A, B, C, D, E} i skup bridova {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Vrste grafikona - usmjereni i neusmjereni grafikon
Grafikon u kojem rubovi nemaju smjerove naziva se neusmjereni graf. Grafikon prikazan gore je neusmjereni graf.
Graf u kojem su bridovi povezani s pravcima naziva se usmjereni graf.
Dolje je dat primjer usmjerenog grafa.
U gore prikazanom usmjerenom grafu rubovi tvore uređeni par u kojem svaki rub predstavlja određeni put od jednog vrha do drugog vrha. Vrh iz kojeg put započinje naziva se „ Početni čvor 'Dok se vrh u koji put završava naziva' Terminalni čvor '.
Dakle, u gornjem grafikonu skup vrhova je {A, B, C, D, E}, a skup bridova je {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.
Razmotrit ćemo terminologiju grafa ili uobičajene pojmove koji se koriste u odnosu na grafikon u nastavku.
Terminologija grafikona
- Vrh: Svaki čvor grafa naziva se temenom. U gornjem grafikonu A, B, C i D su vrhovi grafa.
- Rub: Veza ili put između dva vrha naziva se rub. Povezuje dva ili više vrhova. Različiti bridovi na gornjem grafu su AB, BC, AD i DC.
- Susjedni čvor: U grafikonu, ako su dva čvora povezana rubom, tada se nazivaju susjedni čvorovi ili susjedi. U gornjem grafikonu vrhovi A i B povezani su rubom AB. Tako su A i B susjedni čvorovi.
- Stupanj čvora: Broj bridova koji su povezani s određenim čvorom naziva se stupanj čvora. Na gornjem grafikonu čvor A ima stupanj 2.
- Staza: Slijed čvorova koje moramo slijediti kada moramo putovati iz jednog vrha u drugi u grafu naziva se put. U našem primjeru grafikona, ako trebamo ići od čvora A do C, tada bi put bio A-> B-> C.
- Zatvoreni put: Ako je početni čvor isti kao terminalni čvor, tada se taj put naziva zatvorenim putem.
- Jednostavan put: Zatvoreni put u kojem su svi ostali čvorovi različiti naziva se jednostavnim putem.
- Ciklus: Put u kojem nema ponovljenih bridova ili vrhova, a prvi i posljednji vrh su isti naziva se ciklus. Na gornjem grafikonu A-> B-> C-> D-> A je ciklus.
- Povezani graf: Povezani graf je onaj u kojem postoji put između svakog vrha. To znači da ne postoji niti jedan vrh koji je izoliran ili bez veznog ruba. Gore prikazani graf je povezani graf.
- Potpuni grafikon: Grafikon u kojem je svaki čvor povezan s drugim naziva se cjeloviti graf. Ako je N ukupan broj čvorova u grafu, tada cjeloviti graf sadrži N (N-1) / 2 broj bridova.
- Ponderirani graf: Pozitivna vrijednost dodijeljena svakom rubu koja označava njegovu duljinu (udaljenost između vrhova povezanih rubom) naziva se težina. Graf koji sadrži ponderirane bridove naziva se ponderirani graf. Težina ruba e označava se s w (e) i označava cijenu prelaska ruba.
- Dijagram: Digraf je graf u kojem je svaki rub povezan s određenim smjerom, a prelazak se može izvesti samo u zadanom smjeru.
Prikaz grafikona
Način na koji se struktura podataka grafa pohranjuje u memoriju naziva se 'predstavljanje'. Grafikon se može pohraniti kao sekvencijalni prikaz ili kao povezani prikaz.
Obje ove vrste opisane su u nastavku.
Sekvencijalno predstavljanje
U sekvencijalnom prikazu grafova koristimo matricu susjedstva. Matrica susjedstva je matrica veličine n x n gdje je n broj vrhova na grafikonu.
Redovi i stupci matrice susjedstva predstavljaju vrhove u grafikonu. Element matrice postavlja se na 1 kad je između vrhova prisutan rub. Ako rub nije prisutan, element je postavljen na 0.
Dolje je dat primjer grafa koji prikazuje njegovu matricu susjedstva.
Vidjeli smo matricu susjedstva za gornji graf. Imajte na umu da, budući da je ovo neusmjereni graf, možemo reći da je rub prisutan u oba smjera. Na primjer, kako je prisutan rub AB, možemo zaključiti da je prisutan i rub BA.
U matrici susjedstva možemo vidjeti interakcije vrhova koji su elementi matrice koji se postavljaju na 1 kad god je rub prisutan i na 0 kad ruba nema.
Pogledajmo sada matricu susjedstva usmjerenog grafa.
Kao što je gore prikazano, presječni element u matrici susjedstva bit će 1 ako i samo ako postoji rub usmjeren iz jednog vrha u drugi.
U gornjem grafikonu imamo dva brida iz vrha A. Jedan rub završava u vrh B, dok drugi završava u vrh C. Tako je u matrici susjedstva presjek A & B postavljen na 1 kao presjek A & C.
Dalje, vidjet ćemo sekvencijalni prikaz ponderiranog grafa.
Dolje je dan ponderirani graf i njegova odgovarajuća matrica susjedstva.
Možemo vidjeti da se sekvencijalni prikaz ponderiranog grafa razlikuje od ostalih vrsta grafova. Ovdje su vrijednosti nula u matrici susjedstva zamijenjene stvarnom težinom ruba.
Rub AB ima težinu = 4, pa smo u matrici susjedstva postavili presjek A i B na 4. Slično tome, sve ostale vrijednosti koje nisu nula mijenjaju se u odgovarajuće težine.
Popis susjednosti lakše je primijeniti i slijediti. Prijelaz tj. Da bi se provjerilo postoji li rub od jednog vrha do drugog, potrebno je O (1) vrijeme, a uklanjanju ruba također treba O (1).
Bez obzira je li graf rijedak (manje rubova) ili gust, uvijek treba više prostora.
Povezana reprezentacija
Popis susjednosti koristimo za povezani prikaz grafa. Prikaz popisa susjednosti održava svaki čvor grafikona i vezu do čvorova koji su susjedni ovom čvoru. Kad pređemo sve susjedne čvorove, postavimo sljedeći pokazivač na nulu na kraju popisa.
Prvo razmotrimo neusmjereni graf i njegov popis susjednosti.
Kao što je gore prikazano, imamo povezani popis (popis susjedstva) za svaki čvor. Iz vrha A imamo rubove do vrhova B, C i D. Stoga su ti čvorovi povezani s čvorom A na odgovarajućem popisu susjedstva.
Zatim konstruiramo popis susjedstva za usmjereni graf.
U gore usmjerenom grafu vidimo da nema bridova koji potječu iz vrha E. Stoga je popis susjedstva za vrh E prazan.
Izgradimo sada popis susjednosti za ponderirani graf.
Za ponderirani graf dodajemo dodatno polje u čvor popisa susjednosti da označimo težinu ruba kako je gore prikazano.
dodaj niz u niz nizova java
Lakše je dodavanje vrha na popis susjedstva. Također štedi prostor zbog implementacije povezanog popisa. Kada moramo otkriti postoji li rub između jednog vrha i drugog, operacija nije učinkovita.
Osnovne operacije za grafikone
Slijede osnovne operacije koje možemo izvoditi na strukturi podataka grafa:
- Dodaj vrh: Grafikonu dodaje vrh.
- Dodaj rub: Dodaje rub između dva vrha grafa.
- Prikaži vrhove grafa: Prikazati vrhove grafa.
Implementacija C ++ grafa pomoću popisa susjedstva
Sada predstavljamo implementaciju C ++ za demonstraciju jednostavnog grafa pomoću popisa susjednosti.
Ovdje ćemo prikazati popis susjedstva za ponderirani usmjereni graf. Koristili smo dvije strukture za zadržavanje popisa susjednosti i rubova grafikona. Popis susjednosti prikazuje se kao (početni_vrh, krajnji_vrh, težina).
Program C ++ je sljedeći:
#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 Izlaz:
Izlaz:
Grafikon popis susjedstva
(start_vertex, end_vertex, težina):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Primjene grafova
Razmotrimo neke od primjena grafova.
- Grafovi se široko koriste u računalnoj znanosti za prikaz mrežnih grafova ili semantičkih grafova ili čak za prikaz toka izračunavanja.
- Grafikoni se široko koriste u sastavljačima kako bi prikazali raspodjelu resursa procesima ili naznačili analizu protoka podataka itd.
- Grafovi se također koriste za optimizaciju upita u jezicima baza podataka u nekim specijaliziranim prevoditeljima.
- Na web mjestima društvenih mreža grafovi su glavne strukture za prikaz mreže ljudi.
- Grafovi se opsežno koriste za izgradnju transportnog sustava, posebno cestovne mreže. Popularan primjer su Google karte koje opsežno koriste grafikone za označavanje smjerova u cijelom svijetu.
Zaključak
Graf je popularna i široko korištena struktura podataka koja ima mnoštvo primjena u samom području informatike, osim ostalih područja. Grafovi se sastoje od vrhova i bridova koji povezuju dva ili više vrhova.
Grafikon može biti usmjeren ili usmjeren. Grafove možemo predstaviti pomoću matrice susjedstva koja je linearni prikaz, kao i pomoću popisa povezanih susjedstava. Također smo razgovarali o provedbi grafa u ovom vodiču.
=> Pogledajte ovdje kako biste istražili cjeloviti popis vodiča za C ++.
Preporučena literatura
- Vodič za napredni popis za Python (sortiranje, preokretanje, indeksiranje, kopiranje, pridruživanje, zbroj)
- Popis Python - Stvaranje, pristup, rezanje, dodavanje ili brisanje elemenata
- Zadani popis IP adresa usmjerivača za uobičajene marke bežičnih usmjerivača
- 12 najboljih alata za izradu linijskih grafova za stvaranje zapanjujućih linijskih grafova (2021 RANGING)
- Zadana lozinka za prijavu na usmjerivač za najbolje modele usmjerivača (popis 2021)
- Povezana struktura podataka popisa na C ++ s ilustracijom
- Kružno povezana struktura podataka popisa na C ++ s ilustracijom
- Dvostruko povezana struktura podataka popisa na C ++ s ilustracijom
