Clasa a XI-a · 10 algoritmiRead in English

Grafuri neorientateUndirected graphs

Toți algoritmii din capitolul „Grafuri neorientate”, din programa de liceu: ideea explicată, complexitatea, exemple și cod C++ pe care îl poți modifica și rula chiar aici.

Fă-ți cont gratuit Vezi toți algoritmii

10algoritmi
7capitole
1clasă

Grafuri neorientate

Undirected graphs · 10 algoritmi

Componentele conexeConnected componentsUn graf este conex dacă între oricare două noduri există un lanț. O componentă conexă…O(n²)
Detectarea unui cicluDetecting a cycleUn ciclu este un lanț simplu în care primul nod coincide cu ultimul. Facem o parcurgere…O(n²)
Lanțul de lungime minimă între două noduri (BFS)Shortest path between two nodes (BFS)Lungimea unui lanț este numărul de muchii. Parcurgerea în lățime pornită din x descoperă…O(n²)
Verificarea unui graf bipartitChecking a bipartite graphUn graf este bipartit dacă nodurile lui se pot împărți în două mulțimi A și B astfel…O(n²)
Listele de adiacențăAdjacency listsPentru fiecare nod reținem doar lista vecinilor lui. Muchia [x, y] se adaugă de două…O(log n)
Matricea de adiacență și gradele nodurilorAdjacency matrix and node degreesUn graf neorientat cu n noduri și m muchii se poate memora într-o matrice a cu n linii…O(n²)
Noduri izolate și graful completIsolated nodes and the complete graphUn nod izolat are gradul 0. Un graf este complet dacă oricare două noduri distincte sunt…O(n)
Parcurgerea în adâncime (DFS)Depth-first search (DFS)Parcurgerea în adâncime merge cât de departe se poate: din nodul curent trece în primul…O(n²)
Parcurgerea în lățime (BFS)Breadth-first search (BFS)Parcurgerea în lățime vizitează nodurile „pe straturi”: întâi nodul de start, apoi toți…O(n²)
Verificarea unui lanțChecking a path (chain)O succesiune de noduri x1, x2, ..., xk este lanț dacă oricare două noduri consecutive…O(n²)