Structura datelor grafice este o colecție de noduri legat de margini . Este folosit pentru a reprezenta relațiile dintre diferite entități. Algoritmi grafici sunt metode folosite pentru a manipula și analiza grafice, rezolvând diverse probleme precum găsind calea cea mai scurtă sau de detectare a ciclurilor.

pothineni berbec

Cuprins

• Componentele unui grafic
• Operații de bază pe grafice
• Aplicații ale graficului
• Bazele graficului
• BFS și DFS în grafic
• Cicluri în grafic
• Cea mai scurtă cale din grafic
• Arborele de întindere minim
• Sortare topologică
• Conectivitate în Graph
• Debit maxim în grafic
• Unii trebuie să facă Probleme pe Graph
• Câteva chestionare

Componentele unui grafic:

• vârfuri: Vârfurile sunt unitățile fundamentale ale graficului. Uneori, vârfurile sunt cunoscute și sub denumirea de vârfuri sau noduri. Fiecare nod/vertex poate fi etichetat sau neetichetat.
• Margini: Muchiile sunt desenate sau utilizate pentru a conecta două noduri ale graficului. Poate fi ordonată pereche de noduri într-un grafic direcționat. Edges poate conecta oricare două noduri în orice mod posibil. Nu sunt reguli. Uneori, muchiile sunt cunoscute și ca arce. Fiecare margine poate fi etichetată/neetichetată.

Operații de bază pe grafice:

Mai jos sunt operațiunile de bază pe grafic:

• Inserarea nodurilor/marchiilor în grafic – Introduceți un nod în grafic.
• Ștergerea nodurilor/marchiilor din grafic – Ștergeți un nod din grafic.
• Căutare pe grafice – Căutați o entitate în grafic.
• Traversarea graficelor – Parcurgerea tuturor nodurilor din grafic.

Aplicații ale graficului:

Următoarele sunt aplicațiile din viața reală:

• Structurile de date grafice pot fi folosite pentru a reprezenta interacțiunile dintre jucătorii dintr-o echipă, cum ar fi pase, șuturi și tack-uri. Analizarea acestor interacțiuni poate oferi informații despre dinamica echipei și domeniile de îmbunătățire.
• Folosit în mod obișnuit pentru a reprezenta rețelele sociale, cum ar fi rețelele de prieteni pe rețelele sociale.
• Graficele pot fi folosite pentru a reprezenta topologia rețelelor de calculatoare, cum ar fi conexiunile dintre routere și comutatoare.
• Graficele sunt folosite pentru a reprezenta conexiunile dintre diferite locuri dintr-o rețea de transport, cum ar fi drumurile și aeroporturile.
• Graficele sunt folosite în rețelele neuronale, unde vârfurile reprezintă neuronii, iar marginile reprezintă sinapsele dintre ei. Rețelele neuronale sunt folosite pentru a înțelege cum funcționează creierul nostru și cum se schimbă conexiunile atunci când învățăm. Creierul uman are aproximativ 10^11 neuroni și aproape 10^15 sinapse.

Bazele graficului:

• Introducere în grafice
• Graficul și reprezentările sale
• Tipuri de grafice cu exemple
• Proprietățile de bază ale unui grafic
• Aplicații, avantaje și dezavantaje ale graficului
• Transpunerea graficului
• Diferența dintre grafic și arbore

BFS și DFS în grafic:

• Prima traversare a lățimii pentru un grafic
• Adâncimea prima traversare pentru un grafic
• Aplicații ale Depth First Search
• Aplicații ale Breadth First Traversal
• Prima căutare iterativă în profunzime
• BFS pentru graficul deconectat
• Închiderea tranzitivă a unui grafic folosind DFS
• Diferența dintre BFS și DFS

Cicluri în grafic:

• Detectează ciclul într-un grafic direcționat
• Detectează ciclul într-un grafic nedirecționat
• Detectați ciclul într-un grafic direct folosind culori
• Detectează un ciclu negativ într-un grafic | (Bellman Ford)
• Cicluri de lungime n într-un graf nedirecționat și conex
• Detectarea ciclului negativ folosind Floyd Warshall
• Clonează un grafic aciclic direcționat
• Unirea după rang și comprimarea căii în algoritmul Union-Find
• Cea mai scurtă cale din grafic:
  • Algoritmul cu calea cea mai scurtă a lui Dijkstra
  • Algoritmul Bellman-Ford
  • Algoritmul Floyd Warshall
  • Algoritmul lui Johnson pentru cele mai scurte căi ale tuturor perechilor
  • Cea mai scurtă cale în graficul aciclic direcționat
  • Algoritmul Dialului
  • Grafic în mai multe etape (Cea mai scurtă cale)
  • Cea mai scurtă cale dintr-un grafic neponderat
  • Algoritmul ciclului de greutate medie minimă (sau medie) al lui Karp
  • 0-1 BFS (Cea mai scurtă cale într-un grafic de greutate binar)
  • Găsiți ciclul minim de greutate într-un grafic nedirecționat

  Arborele de întindere minim:

  • Arborele de întindere minim al lui Prim (MST)
  • Algoritmul arborelui de întindere minimă al lui Kruskal
  • Diferența dintre algoritmul lui Prim și Kruskal pentru MST
  • Aplicații ale problemei arborelui de întindere minimă
  • Cost minim pentru conectarea tuturor orașelor
  • Numărul total de arbori care se întind într-un grafic
  • Arborele minim de acoperire a produsului
  • Algoritmul de ștergere inversă pentru arborele de întindere minimă
  • Algoritmul lui Boruvka pentru Minimum Spanning Tree

  Sortare topologică:

  • Sortare topologică
  • Toate tipurile topologice ale unui graf aciclic direcționat
  • Algoritmul lui Kahn pentru sortarea topologică
  • Limitele maxime care pot fi adăugate la DAG, astfel încât să rămână DAG
  • Cea mai lungă cale într-un grafic aciclic direcționat
  • Sortare topologică a unui grafic folosind timpul de plecare al vârfului

  Conectivitate în Graph:

  • Puncte de articulație (sau vârfuri tăiate) într-un grafic
  • Componente biconectate
  • Poduri într-un grafic
  • Calea și circuitul eulerian
  • Algoritmul lui Fleury pentru tipărirea căii sau circuitului eulerian
  • Componente puternic conectate
  • Numărați toate drumurile posibile de la o sursă la o destinație cu exact k margini
  • Circuitul Euler într-un grafic direcționat
  • Lungimea celui mai scurt lanț pentru a ajunge la cuvântul țintă
  • Aflați dacă o matrice de șiruri poate fi înlănțuită pentru a forma un cerc
  • Algoritmul lui Tarjan pentru a găsi componente puternic conectate
  • Căi pentru a parcurge fiecare nod folosind fiecare margine (Șapte poduri ale Königsberg)
  • Conectivitate dinamică | Setul 1 (incremental)

  Debit maxim în grafic:

  • Introducere problemei fluxului maxim
  • Algoritmul Ford-Fulkerson pentru problema debitului maxim
  • Găsiți numărul maxim de căi disjunse de muchii între două vârfuri
  • Găsiți tăietura s-t minimă într-o rețea de curgere
  • Potrivire bipartită maximă
  • Problemă de atribuire a canalelor
  • Introducere în algoritmul Push Rebel
  • Algoritmul lui Karger - Setul 1 - Introducere și implementare
  • Algoritmul lui Dinic pentru flux maxim

  Unii trebuie să facă probleme pe grafic:

  • Găsiți lungimea celei mai mari regiuni din matricea booleană
  • Numărați numărul de copaci dintr-o pădure
  • O problemă cu graficul Peterson
  • Clonează un grafic nedirecționat
  • Colorarea graficelor (introducere și aplicații)
  • Implementarea problemei vânzătorului călători (TSP).
  • Problema acoperirii vârfurilor | Setul 1 (Introducere și algoritm aproximativ)
  • Problema centrelor K | Setul 1 (algoritmul aproximativ lacom)
  • Modelul Erdos Renyl (pentru generarea de grafice aleatorii)
  • Poștaș chinez sau inspecție rută | Setul 1 (introducere)
  • Algoritmul lui Hierholzer pentru graficul direcționat
  • Verificați dacă un anumit grafic este bipartit sau nu
  • Problema cu șarpele și scara
  • Boggle (Găsiți toate cuvintele posibile într-un tablou de caractere)
  • Algoritmul Hopcroft Karp pentru o potrivire maximă-Introducere
  • Timp minim pentru putrezirea tuturor portocalelor
  • Construiți un grafic din grade date ale tuturor vârfurilor
  • Determinați dacă într-un grafic direcționat există o chiuvetă universală
  • Numărul de noduri colectoare dintr-un grafic
  • Problemă cu două clicuri (verificați dacă graficul poate fi împărțit în două clicuri)

  Câteva chestionare:

  • Chestionare despre traversarea graficului
  • Chestionare pe calea cea mai scurtă a graficului
  • Chestionare despre arborele de întindere minim al graficului
  • Chestionare despre grafice

  Link-uri rapide:

  • Top 10 întrebări de interviu despre Depth First Search (DFS)
  • Câteva întrebări interesante pe calea cea mai scurtă
  • Videoclipuri pe grafice

  Recomandat:

  • Aflați structura datelor și algoritmi | Tutorial DSA