graph implementation c using adjacency list
Acest tutorial explică implementarea graficelor în C ++. De asemenea, veți afla despre diferite tipuri, reprezentări și aplicații ale graficelor:
Un grafic este o structură de date neliniară. Un grafic poate fi definit ca o colecție de noduri care sunt, de asemenea, numite „vârfuri” și „margini” care conectează două sau mai multe vârfuri.
Un grafic poate fi văzut și ca un arbore ciclic în care vârfurile nu au o relație părinte-copil, dar mențin o relație complexă între ei.
întrebări și răspunsuri la interviu cu seleniu pentru o experiență de 4 ani
=> Faceți clic aici pentru seria Absolute C ++ Training.
Ce veți învăța:
Ce este un grafic în C ++?
După cum sa menționat mai sus, un grafic în C ++ este o structură de date neliniară definită ca o colecție de vârfuri și margini.
Următorul este un exemplu de structură a datelor grafice.
Dat mai sus este un exemplu de grafic G. Graficul G este un set de vârfuri {A, B, C, D, E} și un set de margini {(A, B), (B, C), (A, D), (D, E), (E, C), (B, E), (B, D)}.
Tipuri de grafice - Grafic direcționat și nedirectat
Un grafic în care marginile nu au direcții se numește grafic nedirectat. Graficul prezentat mai sus este un grafic nedirecționat.
Un grafic în care marginile au direcții asociate lor se numește grafic direcționat.
Dat mai jos este un exemplu de grafic direcționat.
În graficul direcționat prezentat mai sus, muchiile formează o pereche ordonată în care fiecare margine reprezintă o cale specifică de la un vârf la altul. Vârful de la care începe calea se numește „ Nod inițial ”În timp ce vârful în care se termină calea se numește„ Nod terminal ”.
Astfel, în graficul de mai sus, setul de vârfuri este {A, B, C, D, E}, iar setul de margini este {(A, B), (A, D), (B, C), (B, E ), (D, E) (E, C)}.
Vom discuta terminologia graficului sau termenii obișnuiți utilizați în raport cu graficul de mai jos.
Terminologie grafică
- Vertex: Fiecare nod al graficului se numește vârf. În graficul de mai sus, A, B, C și D sunt vârfurile graficului.
- Margine: Legătura sau calea dintre două vârfuri se numește margine. Conectează două sau mai multe vârfuri. Diferitele muchii din graficul de mai sus sunt AB, BC, AD și DC.
- Nod adiacent: Într-un grafic, dacă două noduri sunt conectate printr-o margine, atunci acestea sunt numite noduri adiacente sau vecine. În graficul de mai sus, vârfurile A și B sunt conectate prin muchia AB. Astfel, A și B sunt noduri adiacente.
- Gradul nodului: Numărul de margini care sunt conectate la un anumit nod se numește gradul nodului. În graficul de mai sus, nodul A are un grad 2.
- Cale: Secvența de noduri pe care trebuie să o urmăm atunci când trebuie să călătorim de la un vârf la altul într-un grafic se numește cale. În graficul nostru de exemplu, dacă trebuie să mergem de la nodul A la C, atunci calea ar fi A-> B-> C.
- Calea închisă: Dacă nodul inițial este același cu un nod terminal, atunci calea respectivă este denumită calea închisă.
- Calea simplă: O cale închisă în care toate celelalte noduri sunt distincte se numește o cale simplă.
- Ciclu: O cale în care nu există margini sau vârfuri repetate și primul și ultimul vârf sunt aceleași se numește ciclu. În graficul de mai sus, A-> B-> C-> D-> A este un ciclu.
- Grafic conectat: Un grafic conectat este cel în care există o cale între fiecare vârf. Aceasta înseamnă că nu există un singur vârf izolat sau fără margine de legătură. Graficul de mai sus este un grafic conectat.
- Grafic complet: Un grafic în care fiecare nod este conectat la altul se numește grafic complet. Dacă N este numărul total de noduri dintr-un grafic, atunci graficul complet conține N (N-1) / 2 numărul de muchii.
- Grafic ponderat: O valoare pozitivă atribuită fiecărei muchii care indică lungimea acesteia (distanța dintre vârfurile legate de o margine) se numește greutate. Graficul care conține muchii ponderate se numește grafic ponderat. Greutatea unei muchii e este notată cu w (e) și indică costul traversării unei muchii.
- Diagraf: Un digraf este un grafic în care fiecare margine este asociată cu o direcție specifică și traversarea se poate face numai în direcția specificată.
Reprezentarea graficului
Modul în care structura datelor grafice este stocată în memorie se numește „reprezentare”. Graficul poate fi stocat ca o reprezentare secvențială sau ca o reprezentare legată.
Ambele tipuri sunt descrise mai jos.
Reprezentare secvențială
În reprezentarea secvențială a graficelor, folosim matricea de adiacență. O matrice de adiacență este o matrice de dimensiunea n x n unde n este numărul de vârfuri din grafic.
Rândurile și coloanele matricei de adiacență reprezintă vârfurile într-un grafic. Elementul matricial este setat la 1 atunci când există o margine prezentă între vârfuri. Dacă marginea nu este prezentă, atunci elementul este setat la 0.
Dat mai jos este un exemplu de grafic care prezintă matricea de adiacență.
Am văzut matricea de adiacență pentru graficul de mai sus. Rețineți că, deoarece acesta este un grafic nedirecționat și putem spune că muchia este prezentă în ambele direcții. De exemplu, întrucât muchia AB este prezentă, putem concluziona că muchia BA este de asemenea prezentă.
În matricea de adiacență, putem vedea interacțiunile vârfurilor care sunt elemente ale matricei care sunt setate la 1 ori de câte ori este prezentă muchia și la 0 când marginea este absentă.
Acum să vedem matricea de adiacență a unui grafic direcționat.
Așa cum se arată mai sus, elementul de intersecție din matricea de adiacență va fi 1 dacă și numai dacă există o margine direcționată de la un vârf la altul.
În graficul de mai sus, avem două muchii de la vârful A. O margine se termină în vârful B în timp ce a doua se termină în vârful C. Astfel, în matricea de adiacență, intersecția lui A & B este setată la 1 ca intersecție a lui A și C.
Apoi, vom vedea reprezentarea secvențială pentru graficul ponderat.
Dat mai jos este graficul ponderat și matricea de adiacență corespunzătoare.
Putem vedea că reprezentarea secvențială a unui grafic ponderat este diferită de celelalte tipuri de grafice. Aici, valorile diferite de zero din matricea de adiacență sunt înlocuite cu greutatea reală a muchiei.
Marginea AB are greutate = 4, astfel, în matricea de adiacență, stabilim intersecția lui A și B la 4. În mod similar, toate celelalte valori diferite de zero sunt schimbate la greutățile lor respective.
Lista de adiacențe este mai ușor de implementat și urmărit. Transversal, adică pentru a verifica dacă există o margine de la un vârf la altul durează O (1) timp și îndepărtarea unei muchii durează și O (1).
Indiferent dacă graficul este rar (mai puține muchii) sau dens, este nevoie întotdeauna de mai mult spațiu.
Reprezentare legată
Folosim lista de adiacențe pentru reprezentarea legată a graficului. Reprezentarea listei de adiacență menține fiecare nod al graficului și un link către nodurile care sunt adiacente acestui nod. Când traversăm toate nodurile adiacente, setăm următorul indicator la nul la sfârșitul listei.
Să luăm în considerare mai întâi un grafic nedirecționat și lista lui de adiacență.
Așa cum se arată mai sus, avem o listă legată (listă de adiacențe) pentru fiecare nod. De la vârful A, avem margini până la vârfurile B, C și D. Astfel, aceste noduri sunt legate de nodul A din lista de adiacență corespunzătoare.
Apoi, construim o listă de adiacență pentru graficul direcționat.
În graficul direcționat mai sus, vedem că nu există margini care să provină din vârful E. Prin urmare, lista de adiacențe pentru vârful E este goală.
Acum, să construim lista de adiacențe pentru graficul ponderat.
Pentru un grafic ponderat, adăugăm un câmp suplimentar în nodul listei de adiacență pentru a indica greutatea muchiei așa cum se arată mai sus.
Adăugarea vârfului în lista de adiacență este mai ușoară. De asemenea, economisește spațiu datorită implementării listei legate. Când trebuie să aflăm dacă există o margine între un vârf la altul, operația nu este eficientă.
Operații de bază pentru grafice
Următoarele sunt operațiile de bază pe care le putem efectua pe structura datelor grafice:
- Adăugați un vârf: Adaugă vârf la grafic.
- Adăugați o margine: Adaugă o margine între cele două vârfuri ale unui grafic.
- Afișați vârfurile grafice: Afișați vârfurile unui grafic.
Implementarea graficului C ++ utilizând lista Adjacency
Acum prezentăm o implementare C ++ pentru a demonstra un grafic simplu folosind lista de adiacență.
Aici vom afișa lista de adiacență pentru un grafic direcționat ponderat. Am folosit două structuri pentru a ține lista de adiacență și marginile graficului. Lista de adiacență este afișată ca (start_vertex, end_vertex, greutate).
Programul C ++ este după cum urmează:
#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 Ieșire:
Ieșire:
Lista de adiacență a graficului
(start_vertex, end_vertex, greutate):
(0, 2, 4) (0, 1, 2)
(1, 4, 3)
(2, 3, 2)
(3, 1, 4)
(4, 3, 3)
Aplicații ale graficelor
Să discutăm câteva dintre aplicațiile graficelor.
- Graficele sunt utilizate pe scară largă în informatică pentru a descrie grafice de rețea sau grafice semantice sau chiar pentru a descrie fluxul de calcul.
- Graficele sunt utilizate pe scară largă în Compilatoare pentru a descrie alocarea resurselor către procese sau pentru a indica analiza fluxului de date etc.
- Graficele sunt, de asemenea, utilizate pentru optimizarea interogărilor în limbile de baze de date în unele compilatoare specializate.
- În site-urile de rețele sociale, graficele sunt principalele structuri pentru a descrie rețeaua de oameni.
- Graficele sunt utilizate pe scară largă pentru a construi sistemul de transport, în special pentru rețeaua rutieră. Un exemplu popular este Google Maps, care folosește pe scară largă grafice pentru a indica direcțiile din întreaga lume.
Concluzie
Un grafic este o structură de date populară și larg utilizată, care are multe aplicații în domeniul informaticii, în afară de alte domenii. Graficele constau din vârfuri și muchii care leagă două sau mai multe vârfuri.
cum se creează cazuri de testare junit în java
Un grafic poate fi direcționat sau neorientat. Putem reprezenta grafice folosind matricea de adiacență, care este o reprezentare liniară, precum și folosind lista legată de adiacență. De asemenea, am discutat despre implementarea graficului în acest tutorial.
=> Consultați aici pentru a explora lista completă de tutoriale C ++.
Lectură recomandată
- Tutorial Python Advanced List (Sortare listă, inversare, indexare, copiere, alăturare, sumă)
- Lista Python - Creați, accesați, tăiați, adăugați sau ștergeți elemente
- Lista de adrese IP a routerului implicit pentru mărcile comune de router wireless
- Cele mai bune 12 instrumente de creare a graficelor de linii pentru crearea graficelor de linii uimitoare (CLASAMENTE 2021)
- Parola de autentificare implicită a routerului pentru cele mai bune modele de router (lista 2021)
- Structura de date a listei legate în C ++ cu ilustrație
- Structură de date cu listă circulară legată în C ++ cu ilustrație
- Structură de date de listă dublă legată în C ++ cu ilustrare
