Introducere în grafic în structura datelor
Graficele sunt structuri de date neliniare care cuprind un set finit de noduri și muchii. Nodurile sunt elementele, iar marginile sunt ordonate perechi de conexiuni între noduri.
Observați cuvântul neliniar. O structură de date neliniară este una în care elementele nu sunt aranjate în ordine secvențială. De exemplu, un tablou este o structură liniară de date, deoarece elementele sunt aranjate unul după altul. Puteți traversa toate elementele unui tablou într-o singură execuție. Nu este cazul în structurile de date neliniare. Elementele unei structuri de date neliniare sunt dispuse pe mai multe niveluri, urmând deseori un model ierarhic. Graficele sunt neliniare.
Următorul cuvânt la care trebuie să fiți atenți este finit. Definim graficul pentru a avea un număr finit și numărabil de noduri. Acesta este un termen destul de neacceptabil. În esență, un grafic poate avea un număr infinit de noduri și poate fi în continuare finit. De exemplu, un arbore genealogic care se întoarce la Adam și Eva. Acesta este un grafic relativ infinit, dar este totuși contabil și este astfel considerat finit.
Exemplu din lumea reală
Cel mai bun exemplu de grafice din lumea reală este Facebook. Fiecare persoană de pe Facebook este un nod și este conectată prin margini. A este prieten cu B. B este prieten cu C și așa mai departe.
terminologii
Aici sunt menționate mai jos Terminologiile graficului din structura de date
1. Reprezentarea graficului: În general, un grafic este reprezentat ca o pereche de seturi (V, E). V este mulțimea de noduri sau noduri. E este setul de margini. În exemplul de mai sus,
V = (A, B, C, D, E)
E = (AB, AC, AD, BE, CD, DE)
2. nod sau vertex: elementele unui grafic sunt conectate prin margini.
3. Margini: o cale sau o linie între două vertexuri dintr-un grafic.
4. Noduri alăturate: Două noduri sunt numite adiacente dacă sunt conectate printr-o margine. În exemplul de mai sus, nodul A este adiacent nodurilor B, C și D, dar nu nodului E.
5. Calea: Calea este o secvență de margini între două noduri. Este esențial un travers care începe de la un nod și se termină de la altul. În exemplul de mai sus, există mai multe căi de la nodul A la nodul E.
Calea (A, E) = (AB, BE)
SAU
Calea (A, E) = (AC, CD, DE)
SAU
Calea (A, E) = (AD, DE)
6. Grafic nedirectat : Un grafic nedirecționat este unul în care marginile nu specifică o anumită direcție. Marginile sunt bidirecționale.
Exemplu
Astfel, în acest exemplu, muchia AC poate fi traversată de la A la C și C la A. Similar tuturor marginilor. O cale de la nodul B la nodul C ar fi fie (BA, AC) fie (BD, DC).
7. Graf direcționat: Un grafic direcționat este unul în care marginile pot fi traversate doar într-o direcție specificată.
Exemplu
Astfel, în același exemplu, acum marginile sunt direcționale. Puteți traversa doar marginea de-a lungul direcției sale. Nu există nicio cale de la nodul B la nodul C acum.
8. Grafic ponderat: Un grafic ponderat este unul în care marginile sunt asociate cu o greutate. Acesta este, în general, costul de a traversa marginea.
Exemplu
Astfel, în același exemplu, acum marginile au o anumită greutate asociată cu ele. Există două căi posibile între nodul A până la nodul E.
Calea1 = (AB, BD, DE), Greutate1 = 3 + 2 + 5 = 10
Calea2 = (AC, CD, DE), Greutate2 = 1 + 3 + 5 = 9
În mod clar, unul ar prefera Path2 dacă obiectivul este să ajungă la nodul E de la nodul A cu cost minim.
Operațiuni de bază pe grafic
Iată operațiunile de bază ale graficului menționate mai jos
1. Adăugați / eliminați Vertex
Aceasta este cea mai simplă operație din grafic. Pur și simplu adăugați un vertex la un grafic. Nu trebuie să fie conectat la niciun alt vertex printr-o margine. Când eliminați un vertex, trebuie să eliminați toate marginile care provin din și care se termină la vertexul șters.
2. Adăugați / eliminați marginea
Această operație adaugă sau îndepărtează o margine între două vârfuri. Când toate marginile care provin de la și se termină la un vertex sunt șterse, vertexul devine un vertex izolat.
3. Latere-Prima Căutare (BFS)
Aceasta este o operație de traversare în grafic. BFS traversează orizontal graficul. Aceasta înseamnă că traversează toate nodurile la un singur nivel înainte de a trece la nivelul următor.
Algoritmul BFS începe din partea de sus a primului nod din grafic și apoi parcurge toate nodurile adiacente către acesta. Odată traversate toate nodurile adiacente, algoritmul repetă aceeași procedură pentru nodurile copil.
Exemplu
Traversarea graficului de mai sus în mod BFS ar rezulta din A -> B -> C -> D -> E -> F -> G. Algoritmul pornește de la nodul A și traversează toate nodurile adiacente B, C și D. Acesta marchează toate cele patru noduri vizitate. Odată traversate toate nodurile adiacente ale lui A, algoritmul se deplasează la primul nod adiacent al lui A și repetă aceeași procedură. În acest caz, nodul este B și nodurile adiacente lui B sunt E și F. În continuare, sunt traversate nodurile adiacente către C. Odată ce toate nodurile sunt vizitate, operațiunea se încheie.
4. Prima căutare a adâncimii (DFS)
Depth First Search sau DFS traversează graficul pe verticală. Începe cu nodul rădăcină sau primul nod al graficului și traversează toate nodurile copil înainte de a trece la nodurile adiacente.
Exemplu
Traversarea graficului de mai sus în mod BFS ar rezulta din A -> B -> E -> F -> C -> G -> D. Algoritmul pornește de la nodul A și traversează toate nodurile copilului său. De îndată ce se întâlnește cu B, se pare că mai are noduri copil. Deci, nodurile copil din B sunt traversate înainte de a trece la următorul nod copil din A.
Realizări grafice din lumea reală
- Proiectarea circuitelor electrice pentru transmisia de putere.
- Proiectarea rețelei de calculatoare interconectate.
- Studiul structurii moleculare, chimice și celulare a oricărei substanțe, de exemplu ADN-ul uman.
- Proiectarea rutelor de transport între orașe și locuri dintr-un oraș.
Concluzie - Grafic în structura datelor
Graficele sunt un concept foarte util în structurile de date. Are implementări practice în aproape toate domeniile. Este foarte important să înțelegem elementele de bază ale teoriei graficului, să dezvoltăm o înțelegere a algoritmilor structurii grafice.
Acest articol a fost doar o introducere în grafice. Este doar o piatră de pas. Se recomandă să vă scufundați mai mult în subiectul teoriei graficului.
Articole recomandate
Acesta este un ghid al graficului în structura datelor. Aici discutăm Terminologiile și operațiunile de bază ale graficului în structura datelor. De asemenea, puteți consulta articolul următor pentru a afla mai multe -
- Întrebări privind interviul privind structura datelor
- Model de date în Cassandra
- Ce este Data Mart?
- Ce este un cercetător de date?