Dubbio su algoritmo su grafo
salve, dovrei risolvere questo esercizio:
Scrivere un algoritmo che , dati in ingresso un grafo non orientato G =(V,E) stabilisce se G è un'unica componente connessa con un numero pari di vertici. fornire la complessità dell'algoritmo.
il problema è che non so da dove partire, non mi viene proprio niente.
cosa posso fare?
grazie
Scrivere un algoritmo che , dati in ingresso un grafo non orientato G =(V,E) stabilisce se G è un'unica componente connessa con un numero pari di vertici. fornire la complessità dell'algoritmo.
il problema è che non so da dove partire, non mi viene proprio niente.
cosa posso fare?
grazie
Risposte
"lilengels":
il problema è che non so da dove partire, non mi viene proprio niente.
cosa posso fare?
grazie
parti dal vedere come funziona la visita DFS.
ma in realtà partire da Dfs o Bfs cambia poco... il fatto è che se un grafo è connesso una visita del grafo deve dar vita ad un albero con esattamente n nodi...
Ti do una bozza di codice in pseudolinguaggio che sfrutta il DFS
algoritmo connesso (Grafo G, vertice s ) --> boolean {
marca tutti i nodi come non esplorati;
num = 0;
P<-- struttura pila vuota;
P.push (s);
while (!P.isempty()) do
{
u<-- P.pop();
marca u come visitato;
num++;
for each((u,v)€G) do
if ( v non visitato) then P.push(v);
}
if ( num == |V|) then return true;
else return false;
}
Tempo richiesto nel caso peggiore ovvero quando il grafo è connesso O(m+n).
Spero sia questo ciò che stavi cercando...
Ti do una bozza di codice in pseudolinguaggio che sfrutta il DFS
algoritmo connesso (Grafo G, vertice s ) --> boolean {
marca tutti i nodi come non esplorati;
num = 0;
P<-- struttura pila vuota;
P.push (s);
while (!P.isempty()) do
{
u<-- P.pop();
marca u come visitato;
num++;
for each((u,v)€G) do
if ( v non visitato) then P.push(v);
}
if ( num == |V|) then return true;
else return false;
}
Tempo richiesto nel caso peggiore ovvero quando il grafo è connesso O(m+n).
Spero sia questo ciò che stavi cercando...
@Danielking: Usa il tag code per inserire il codice, anche se non è scritto in un vero linguaggio di programmazione in modo da renderlo più leggibile.
"Danielking":
ma in realtà partire da Dfs o Bfs cambia poco...
non penso.
BFS visita solo l'albero radicato a partire da un vertice. Se un grafo ha più componenti connesse non si può sapere.
DFS visita l'intero grafo e basta intorrempere la visita appena si scopre un vertice in più, oltre la prima componente connessa.
Quindi non serve scrive codice ex-novo, basta una piccola modifica alla DFS, cosa che hai fatto ma si contraddice se parti dalla BFS.
non capisco...
L'algortmico richiedeva di rispondere alla domanda se il grafo G è una componente connessa...
Se esistono dei nodi isolati che non sono legati tra loro ma non al resto del grafo (ovvero esistono più componenti connesse che tra l'altro è un caso non contemplato dall'esercizio richiesto) come fa una visita DFS a visitare l'intero grafo?
L'algortmico richiedeva di rispondere alla domanda se il grafo G è una componente connessa...
Se esistono dei nodi isolati che non sono legati tra loro ma non al resto del grafo (ovvero esistono più componenti connesse che tra l'altro è un caso non contemplato dall'esercizio richiesto) come fa una visita DFS a visitare l'intero grafo?
Credo che Danielking abbia ragione. Un qualsiasi algoritmo che ti permetta di visitare l'albero radicato in un nodo qualsiasi (scelto a caso) va bene per rispondere alla domanda.
Il fatto è che Danielking considera a priori il numero di vertici, ovviamente se fosse così è corretta la sua versione e in pratica è così perchè basta confrontare il numero di nodi visitati ed i vertici totali. Ma di solito è meglio non fare assunzioni, almeno in questi esercizi e rimanere generali.
ma se ci sono più componenti connesse comunque un algoritmo di visita o in profondità non può raggiungere tutti i nodi anche una visita in profondità terminerà al termine della singola componente connessa, a meno di aggiungere un arco iniziale che collega tutti i nodi...
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo