Drum Hamiltonian în DAG

PLAYGROUND

Vizualizator & Editor de Grafuri

Matricea de Adiacență

Noduri:

Bifează celula (linie, coloană) pentru a adăuga un arc orientat de la nodul liniei la nodul coloanei. Diagonala este blocată (fără bucle).

Seturi Predefinite (Presetări)

Reprezentarea Vizuală a Grafului

💡 Poți glisa (drag) nodurile grafului pentru a rearanja aspectul vizual.

Consola de Execuție

Gata

[Sistem] Generatorul a fost inițializat. Alege o presetare sau editează matricea pentru a începe.

SANDBOX JS

Modifică & Testează Codul Algoritmului

Aici poți edita logica JavaScript direct în browser! Codul tău primește ca intrare numărul de noduri și matricea de adiacență, apoi rulează în timp real. Mesajele din console.log() vor apărea direct în Consola de mai sus.

algoritm_hamiltonian.js

ECMAScript 6 (Strict)

// =========================================================================
// ALGORITM: DRUM HAMILTONIAN ÎN GRAF ORIENTAT ACICLIC (DAG)
// =========================================================================
// S-a adăugat: Vizualizare VERBOSE și încetinitor (sleep) pentru prezentare
//
// Intrarea algoritmului:
// - n = numărul de noduri (întreg). Nodurile sunt indexate de la 0 la n-1.
// - matrix = matricea de adiacență a grafului (array 2D, elementele sunt 0 sau 1).
// - sleep = funcție pentru încetinire, apelabilă cu `await sleep(ms)`

async function solveHamiltonian(n, matrix) {
    console.log("Se inițiază algoritmul pentru un graf cu " + n + " noduri...");
    
    // =========================================================================
    // PASUL 1: DETECTAREA CIRCUITELOR (CICLURILOR)
    // =========================================================================
    const visited = new Array(n).fill(0); 
    let hasCycle = false;
    
    async function dfsCycle(node) {
        console.log(`[DFS-C] Vizităm nodul ${String.fromCharCode(65 + node)}. Îl marcăm Gri (în procesare).`);
        visited[node] = 1; 
        await sleep(400); // Încetinitor pentru a observa pașii în consolă
        
        for (let next = 0; next < n; next++) {
            if (matrix[node][next] === 1) { 
                console.log(`  [DFS-C] Verificăm muchia ${String.fromCharCode(65 + node)} -> ${String.fromCharCode(65 + next)}`);
                await sleep(300);

if (visited[next] === 1) {
                    console.log(`  🔥 [DFS-C] EROARE! Am găsit o muchie înapoi la nodul ${String.fromCharCode(65 + next)} care este deja Gri. Circuit detectat!`);
                    hasCycle = true;
                    return;
                } else if (visited[next] === 0) {
                    await dfsCycle(next);
                    if (hasCycle) return; 
                }
            }
        }
        console.log(`[DFS-C] Nodul ${String.fromCharCode(65 + node)} finalizat. Îl marcăm Negru.`);
        visited[node] = 2; 
    }
    
    for (let i = 0; i < n; i++) {
        if (visited[i] === 0) {
            await dfsCycle(i);
        }
    }
    
    if (hasCycle) {
        console.log("Eroare: Graful conține circuite. Condiția de DAG a eșuat!");
        return { hasPath: false, path: null, error: "Graful conține circuite (nu este un DAG)" };
    }
    
    // =========================================================================
    // PASUL 2: SORTAREA TOPOLOGICĂ
    // =========================================================================
    console.log("\n--- Începe Sortarea Topologică ---");
    const topoOrder = [];
    const topoVisited = new Array(n).fill(false);
    
    async function dfsTopo(node) {
        topoVisited[node] = true;
        for (let next = 0; next < n; next++) {
            if (matrix[node][next] === 1 && !topoVisited[next]) {
                await dfsTopo(next);
            }
        }
        console.log(`[TOPO] Am adăugat ${String.fromCharCode(65 + node)} la lista de sortare.`);
        topoOrder.push(node);
        await sleep(200);
    }
    
    for (let i = 0; i < n; i++) {
        if (!topoVisited[i]) {
            await dfsTopo(i);
        }
    }
    topoOrder.reverse();
    console.log(`Sortare topologică obținută (inversată): ${topoOrder.map(x => String.fromCharCode(65 + x)).join(" -> ")}\n`);
    await sleep(500);

// =========================================================================
    // PASUL 3: VALIDAREA DRUMULUI HAMILTONIAN
    // =========================================================================
    console.log("--- Verificăm unicitatea sortării ---");
    let pathExists = true;
    for (let i = 0; i < n - 1; i++) {
        const u = topoOrder[i];
        const v = topoOrder[i + 1];
        
        console.log(`Verificăm legătura directă între nodurile consecutive ${String.fromCharCode(65 + u)} și ${String.fromCharCode(65 + v)}...`);
        await sleep(400);

if (matrix[u][v] !== 1) {
            console.log(`❌ Nu există arc direct între ${String.fromCharCode(65 + u)} și ${String.fromCharCode(65 + v)}. Sortarea nu e unică.`);
            pathExists = false;
            break; 
        } else {
            console.log(`✅ Legătură validă: ${String.fromCharCode(65 + u)} -> ${String.fromCharCode(65 + v)}`);
        }
    }
    
    // =========================================================================
    // REZULTAT FINAL
    // =========================================================================
    if (pathExists) {
        console.log("\nSucces! A fost identificat un drum Hamiltonian valid.");
        return { hasPath: true, path: topoOrder, error: null };
    } else {
        console.log("\nEșec. Nu există drum Hamiltonian în acest DAG.");
        return { hasPath: false, path: null, error: null };
    }
}

return await solveHamiltonian(n, matrix);

MATH DOCS

Documentația Algoritmului & Suport Academic

1. Concepte Fundamentale

Drumul Hamiltonian: Într-un graf orientat G = (V, E), un drum Hamiltonian este un drum simplu care trece prin fiecare vârf v ∈ V exact o singură dată. Determinarea existenței unui drum Hamiltonian în grafuri generale este o problemă extrem de dificilă (NP-completă), echivalentă cu problema comis-voiajorului.

Graf Orientat Acyclic (DAG): Un DAG este un graf orientat care nu conține circuite (cicluri). În această structură particulară, relațiile de ordine între vârfuri permit simplificarea drastică a multor probleme computaționale grele.

Sortarea Topologică: Sortarea topologică a unui DAG este o aranjare liniară a vârfurilor sale astfel încât pentru fiecare arc orientat u → v, nodul u să preceadă nodul v în ordonare. Orice DAG are cel puțin o sortare topologică.

2. Teorema Existenței Drumului Hamiltonian în DAG-uri

Un graf orientat fără circuite (DAG) are un drum Hamiltonian dacă și numai dacă sortarea sa topologică este UNICĂ.

Demonstrație intuitivă:

Necesitate (⇒): Să presupunem că DAG-ul G conține un drum Hamiltonian v₁ → v₂ → ... → v_n. Acest drum vizitează toate vârfurile exact o dată. Arcele drumului determină o relație de ordine totală strictă în care v_i trebuie să apară înaintea lui v_i+1 în orice sortare topologică. Prin urmare, singura sortare topologică validă este chiar succesiunea vârfurilor din drumul Hamiltonian, făcând sortarea topologică unică.
Suficiență (⇐): Să presupunem că graful G are o singură sortare topologică v₁, v₂, ..., v_n. Presupunem, prin reducere la absurd, că pentru o anumită poziție i (1 ≤ i < n), nu există arcul direct v_i → v_i+1 în graf. Deoarece este o sortare topologică, nu pot exista alte căi orientate de la v_i+1 la v_i (altfel s-ar forma un circuit). De asemenea, din moment ce nu există arcul direct v_i → v_i+1 și niciun element intermediar nu se află între ele în sortare, nu există nicio cale de la v_i la v_i+1 care să nu implice alte vârfuri. Asta înseamnă că relația de precedență directă între ele este nedeterminată; prin urmare, am putea inversa ordinea nodurilor obținând sortarea topologică validă v₁, ..., v_i+1, v_i, ..., v_n, ceea ce contrazice ipoteza că sortarea este unică. Astfel, arcul v_i → v_i+1 trebuie să existe pentru orice i, generând drumul Hamiltonian.

3. Descrierea Pas cu Pas a Algoritmului

Pentru a determina drumul Hamiltonian, algoritmul implementat parcurge următorii pași:

Verificarea prezenței circuitelor: Se rulează o parcurgere în adâncime (DFS) unde nodurile sunt marcate ca: 0 (nevizitat), 1 (în curs de procesare / în stivă), sau 2 (complet explorat). Dacă se întâlnește un arc către un nod cu marcajul 1, s-a detectat un circuit înapoi, iar graful nu este un DAG.
Generarea Sortării Topologice: Dacă graful este DAG, se rulează DFS pe nodurile nevizitate. Când un nod își termină explorarea vecinilor săi, este adăugat în fruntea unei liste (sau adăugat într-o stivă și extras la final). Ordinea rezultată reprezintă sortarea topologică.
Validarea drumului: Având sortarea topologică v₁, v₂, ..., v_n, se folosește matricea de adiacență pentru a interoga dacă celula M[v_i][v_i+1] == 1 pentru orice i ∈ [1, n - 1].
Verdict: Dacă toate interogările returnează 1, atunci sortarea topologică reprezintă drumul Hamiltonian valid și unic. În caz contrar, graful nu admite un drum Hamiltonian.

4. Analiza Complexității

Complexitate Temporală: Parcurgerea DFS pentru sortare topologică și detecția ciclurilor vizitează fiecare nod și arc exact o singură dată, consumând timp O(V + E). Verificarea conexiunilor adiacente din sortare efectuează exact V - 1 interogări în matricea de adiacență, consumând O(V) pași. Prin urmare, complexitatea temporală totală este de **O(V + E)** (respectiv O(V²) dacă graful este dens și reprezentat prin matrice de adiacență, deoarece popularea și interogarea acoperă celulele matricei).
Complexitate Spațială: Spațiul auxiliar utilizat este destinat structurilor de vizitare (vectori de vizitare, stiva recursivă și lista sortării), însumând o complexitate spațială de **O(V)**.

← Înapoi la Arhiva de Proiecte