Ho un problema di hw che richiede un algoritmo che rileva se c'è un ciclo in qualsiasi grafico non orientato che contiene un dato bordo 'E'. L'algoritmo dovrebbe essere eseguito nel tempo lineare O (N).Come verificare se un fronte è in qualche ciclo?
Il problema che ho è che non so da dove cominciare. Ho alcuni semplici grafici di esempio, ma non so da dove andare.
Eventuali suggerimenti?
Si inizia con il bordo 'e'. Da questo dovresti ottenere i due vertici che collega. Da loro si ottengono altri bordi e altri vertici, e altri bordi e altri vertici, e ... Avrai bisogno di un modo per capire se un vertice è già stato 'visitato' dal tuo algoritmo. Se ha allora c'è un ciclo di cui 'e' è parte.
Esegui prima una ricerca approfondita aggiungendo nodi a un elenco mentre vai e rimuovendoli dall'elenco al tuo ritorno.
L'elenco rappresenta il percorso corrente di attraversamento.
Se si incontra un nodo che è già presente nell'elenco, esiste un ciclo/ciclo.
Per il bordo (u, v):
1- eseguire una ricerca in profondità a partire da u, determinare se viene rilevato v ed un bordo posteriore presenti lungo il percorso v
2-. eseguire una ricerca in profondità da v, se u è trovato e bordo posteriore esistono per u, allora c'è un ciclo che include sia uev.
In altre parole,
1- eseguire un DFS partendo da u , controlla se il bordo posteriore esiste e v non è ancora finito.
2- eseguire un DFS a partire da v, controllare se il bordo posteriore esiste e non è ancora finito se entrambe le condizioni sono vere, quindi il bordo (u, v) appartiene a un ciclo.
Estrarre quel bordo (u, v) da G. 1. Avviare BFS per vedere se v è ancora raggiungibile da u. 2. se sì, il grafico originale ha un ciclo contenente e. altrimenti non lo è.
Un suggerimento? Sicuro. Alcuni set (come gli hashset) hanno una ricerca O (1). – corsiKa