Tipuri de grafice în structura datelor cu exemple
Sarah Chen
⚡ Rezumat inteligent
Grafurile în structura datelor sunt colecții neliniare de vârfuri și muchii clasificate în familii precum grafuri direcționate, nedirecționate, ponderate, ciclice, aciclice, complete, conexe, bipartite, Euler și Hamilton, bazate pe structură.
Un graf este o structură de date neliniară care constă din vârfuri și muchii. Vârfurile conțin informațiile sau datele, iar muchiile funcționează ca o legătură între o pereche de vârfuri.
Grafurile pot fi de mai multe tipuri, în funcție de poziția nodurilor și a muchiilor. Iată câteva tipuri importante de grafuri:
Graficul Dirijat
Muchiile grafului orientat conțin săgeți care indică direcția. Săgeata determină unde este indicată muchia sau unde se termină. Iată un exemplu de graf orientat.
Graficul Dirijat
- Putem merge de la Nodul A la D.
- Totuși, nu putem merge de la nodul D la nodul A, deoarece marginea indică de la A la D.
- Deoarece Graficul nu are ponderi, călătoria de la vârful A la D va costa la fel ca și călătoria de la D la F.
Grafic nedirecționat
Un graf neorientat conține muchii fără pointeri. Aceasta înseamnă că putem călători invers între două vârfuri. Iată un exemplu simplu de graf neorientat.
Grafic nedirecționat
În graficul de mai sus,
- Putem trece de la A la B.
- De asemenea, putem trece de la B la A.
- Marginile nu conțin direcții.
Este un exemplu de graf neorientat având un număr finit de vârfuri și muchii fără ponderi.
Graficul ponderat
Un graf care conține ponderi sau costuri pe muchii se numește graf ponderat. Valoarea numerică reprezintă, în general, costul deplasării de la un vârf la altul. Atât grafurile orientate, cât și cele neorientate pot avea ponderi pe muchiile lor. Iată un exemplu de graf ponderat (orientat).
Grafic direcționat cu greutate
- De la A la B, există o muchă, iar ponderea este 5, ceea ce înseamnă că trecerea de la A la B ne va costa 5.
- A indică B, dar în acest grafic, B nu are o muchă directă peste A. Deci, nu putem călători de la B la A.
- Totuși, dacă vrem să trecem de la A la F, există mai multe căi. Căile sunt ADF și ABF. ADF va costa (10+11) sau 21.
- Aici, calea ABF va costa (5+15) sau 20. Aici adăugăm ponderea fiecărei muchii din cale.
Iată un exemplu de graf neorientat cu ponderi:
Grafic nedirecționat cu greutate
Aici, marginea are greutate, dar nu are direcție. Deci, înseamnă că călătoria de la vârful A la D va costa 10 și invers.
Grafic bidirecțional
Grafurile bidirecționale și neorientate au o proprietate comună. Și anume:
- În general, un graf neorientat poate avea o muchă între două vârfuri.
De exemplu:
- Aici, mutarea de la A la D sau D la A va costa 10.
- Într-un grafic bidirecțional, putem avea două muchii între două vârfuri.
Iată un exemplu:
Grafic bidirecțional
Călătoria de la A la D ne va costa 17, dar călătoria de la D la A ne va costa 12. Deci, nu putem atribui două ponderi diferite dacă este un graf neorientat.
Grafic infinit
Graful va conține un număr infinit de muchii și noduri. Dacă un graf este infinit și este, de asemenea, un graf conex, atunci va conține și un număr infinit de muchii. Aici, muchiile extinse înseamnă că mai multe muchii ar putea fi conectate la aceste noduri prin muchii. Iată un exemplu de graf infinit:
Grafic infinit
Grafic nul
Un graf nul conține doar noduri sau vârfuri, dar fără muchii. Dacă i se dă un graf G = (V, E), unde V reprezintă vârfurile și E sunt muchiile, acesta va fi nul dacă numărul de muchii E este zero. Iată un exemplu de graf nul:
Grafic nul
Grafic trivial
O structură de date a unui graf este considerată trivială dacă este prezent un singur vârf sau nod fără muchii. Iată un exemplu de graf trivial:
Grafic multiplu
Un graf se numește multigraf atunci când există mai multe muchii între două vârfuri sau vârful are o buclă. Termenul „Buclă” în structura datelor grafurilor înseamnă o muchie care indică același nod sau vârf. Un multigraf poate fi direcționat sau nedirecționat. Iată un exemplu de multigraf:
Există două muchii de la B la A. Mai mult, vârful E are o auto-buclă. Graful de mai sus este un graf orientat fără ponderi pe muchii.
Graficul complet
Un graf este complet dacă fiecare vârf are muchii orientate sau neorientate cu toate celelalte vârfuri. Să presupunem că există un total de V vârfuri și fiecare vârf are exact V-1 muchii. Atunci, acest graf va fi numit graf complet. În acest tip de graf, fiecare vârf este conectat la toate celelalte vârfuri prin muchii. Iată un exemplu de graf complet cu cinci vârfuri:
Puteți vedea în imagine că numărul total de noduri este cinci și toate nodurile au exact patru muchii.
Graficul conectat
Un graf se numește graf conectat dacă pornim de la un nod sau vârf și putem ajunge la toate nodurile de la nodul de pornire. Pentru aceasta, ar trebui să existe cel puțin o muchie între fiecare pereche de noduri sau vârfuri. Iată un exemplu de graf conectat:
Iată câteva explicații pentru graficul conectat de mai sus:
- Presupunând că nu există o muchie între C și F, nu putem călători de la A la G. Cu toate acestea, muchia de la C la F ne permite să călătorim către orice nod dintr-un nod dat.
- Un graf complet este un graf conectat deoarece ne putem muta de la un nod la orice alt nod din graficul dat.
Graficul ciclic
Un graf se numește ciclic dacă există unul sau mai multe cicluri prezente în graf. Iată un exemplu de graf ciclic:
Aici, vârfurile A, B și C formează un ciclu. Un graf poate avea mai multe cicluri în interiorul său.
Grafic aciclic direcționat (DAG)
Un graf se numește graf aciclic direcționat sau DAG dacă nu există cicluri în interiorul grafului. DAG este important atunci când se face... Sortare topologică sau găsirea ordinii de execuție. DAG este important și pentru crearea sistemelor de planificare sau scanarea dependenței de resurse etc. Cu toate acestea, graficul de mai sus nu conține niciun ciclu în interior. Iată un exemplu simplu de grafic aciclic direcționat (DAG):
Graficul ciclului
Un graf ciclic nu este același lucru cu un graf ciclic. Într-un graf ciclic, fiecare nod va avea exact două muchii conectate, ceea ce înseamnă că fiecare nod va avea exact două grade. Iată un exemplu de graf ciclic:
Graficul bipartit
Aceste tipuri de graficele sunt tipuri speciale de grafuri în care vârfurile sunt atribuite la două mulțimi. Un graf bipartit trebuie să respecte regula:
- Cele două seturi de vârfuri ar trebui să fie distincte, ceea ce înseamnă că toate vârfurile trebuie împărțite în două grupuri sau seturi.
- Vârfurile de același set nu ar trebui să formeze nicio muchie.
Graficul Euler
O structură de date de tip graf este considerată un graf Euler dacă toate vârfurile au un grad par. Termenul „gradul vârfurilor” înseamnă numărul de muchii care indică spre sau dinspre un anumit vârf. Iată un exemplu de graf Euler:
Toate vârfurile au grade pare. Vârfurile A, D, E și H au două grade. Aici, nodul C are patru grade, ceea ce este par.
Graficul Hamilton
Un graf Hamilton este un graf conectat, în care poți vizita toate vârfurile dintr-un anumit vârf fără a revizita același nod sau a utiliza aceeași muchie. Acest tip de graf conectat este cunoscut sub numele de „graf Hamilton”. Calea pe care o vizitezi pentru a verifica dacă graful dat este sau nu un graf Hamilton este cunoscută sub numele de Cale Hamiltoniană. Iată un exemplu simplu de graf Hamiltonian:
În această imagine, putem vizita toate nodurile din orice nod din graficul de mai sus. Una dintre căi poate fi ADCHBEDe asemenea, este posibil să se găsească un ciclu Hamilton. Un ciclu Hamilton începe și se termină în același vârf. Deci, ciclul Hamilton va fi ADCHBEA.
