Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Algoritmo su digrafo aciclico
67 views
Skip to first unread message
Antologiko
Oct 31, 2015, 7:51:27 PM10/31/15
to
Sia G un digrafo semplice (ovvero un grafo orientato, senza cappi ne archi paralleli), e si assuma che in G esiste un unico nodo N1 a non possedere alcun genitore.
Mi serve un algoritmo veloce per stabilire se G è connesso ed aciclico.
Mi serve un algoritmo veloce per stabilire se G è connesso ed aciclico.
fma...@gmail.com
Nov 2, 2015, 3:41:16 AM11/2/15
to
Ciao!
ADPUF
Nov 2, 2015, 2:54:56 PM11/2/15
to
Antologiko 00:51, domenica 1 novembre 2015:
> Sia G un digrafo semplice (ovvero un grafo orientato, senza
> cappi ne archi paralleli), e si assuma che in G esiste un
> unico nodo N1 a non possedere alcun genitore.
>
> Mi serve un algoritmo veloce per stabilire se G č connesso ed
> aciclico.
Moltiplicare la matrice N volte ?
Non sono vere moltiplicazioni, sono OR di AND di zeri e uni.
Boh, non so se č veloce.
--
AIOE łżł
> Sia G un digrafo semplice (ovvero un grafo orientato, senza
> cappi ne archi paralleli), e si assuma che in G esiste un
> unico nodo N1 a non possedere alcun genitore.
>
> aciclico.
Moltiplicare la matrice N volte ?
Non sono vere moltiplicazioni, sono OR di AND di zeri e uni.
Boh, non so se č veloce.
--
AIOE łżł
fma...@gmail.com
Nov 2, 2015, 3:07:09 PM11/2/15
to
No, tranquilli, il DFS è per controllare se un grafo è connesso e aciclico
è da manuale...
Ciao!
ADPUF
Nov 3, 2015, 3:42:02 PM11/3/15
to
fma...@gmail.com
Nov 3, 2015, 3:54:05 PM11/3/15
to
che già è stato visitato il grafo ha un ciclo. Se, quando ha finito, ci
sono nodi che non sono stati visitati il grafo non è connesso.
Ciao!
Antologiko
Nov 4, 2015, 1:44:44 PM11/4/15
to
Grazie a tutti delle risposte. Aggiungo (chiedo venia per la distrazione) che il grafo è stato implementato tramite liste di adiacenza.
Mi è però venuto un dubbio:
nei grafi orientati, il DFS si muove per definizione sempre in direzione dei "figli"?
Perché in questo caso, prendendo un nodo a caso, col DFS potrebbero non essere raggiunti i suoi "avi", pur essendo il grafo connesso.
Grazie a chiunque per eventuali chiarimenti.
Mi è però venuto un dubbio:
nei grafi orientati, il DFS si muove per definizione sempre in direzione dei "figli"?
Perché in questo caso, prendendo un nodo a caso, col DFS potrebbero non essere raggiunti i suoi "avi", pur essendo il grafo connesso.
Grazie a chiunque per eventuali chiarimenti.
ADPUF
Nov 4, 2015, 3:42:35 PM11/4/15
to
fma...@gmail.com 21:54, martedì 3 novembre 2015:
--
AIOE ³¿³
> On Tuesday, November 3, 2015 at 9:42:02 PM UTC+1, ADPUF
>> fma...@gmail.com 21:07, lunedì 2 novembre 2015:
>> > On Monday, November 2, 2015 at 8:54:56 PM UTC+1, ADPUF
>> > On Monday, November 2, 2015 at 8:54:56 PM UTC+1, ADPUF
>> >> Antologiko 00:51, domenica 1 novembre 2015:
>> >>
>> >> > Sia G un digrafo semplice (ovvero un grafo orientato,
>> >> > senza cappi ne archi paralleli), e si assuma che in G
>> >> > esiste un unico nodo N1 a non possedere alcun genitore.
>> >> >
>> >> > Mi serve un algoritmo veloce per stabilire se G č
>> >> > connesso ed aciclico.
>> >>
>> >>
>> >> Moltiplicare la matrice N volte ?
>> >>
>> >> Non sono vere moltiplicazioni, sono OR di AND di zeri e
>> >> uni.
>> >>
>> >> Boh, non so se č veloce.
>> >>
>> >
>> > Minchia! :D
>> >
>> > No, tranquilli, il DFS è per controllare se un grafo è
>> > connesso e aciclico è da manuale...
>>
>>
>> E spiega, òstrega!
>> :-)
>>
>
> Scegli un nodo a caso, fai un DFS. Se, durante il percorso,
> trovi un nodo che già è stato visitato il grafo ha un ciclo.
> Se, quando ha finito, ci sono nodi che non sono stati
> visitati il grafo non è connesso.
Scusa l'abissale ignoranza, ma che cosa è DFS?
>> >>
>> >> > Sia G un digrafo semplice (ovvero un grafo orientato,
>> >> > senza cappi ne archi paralleli), e si assuma che in G
>> >> > esiste un unico nodo N1 a non possedere alcun genitore.
>> >> >
>> >> > Mi serve un algoritmo veloce per stabilire se G č
>> >> > connesso ed aciclico.
>> >>
>> >>
>> >> Moltiplicare la matrice N volte ?
>> >>
>> >> Non sono vere moltiplicazioni, sono OR di AND di zeri e
>> >> uni.
>> >>
>> >> Boh, non so se č veloce.
>> >>
>> >
>> > Minchia! :D
>> >
>> > No, tranquilli, il DFS è per controllare se un grafo è
>> > connesso e aciclico è da manuale...
>>
>>
>> E spiega, òstrega!
>> :-)
>>
>
> Scegli un nodo a caso, fai un DFS. Se, durante il percorso,
> trovi un nodo che già è stato visitato il grafo ha un ciclo.
> Se, quando ha finito, ci sono nodi che non sono stati
> visitati il grafo non è connesso.
--
AIOE ³¿³
fma...@gmail.com
Nov 4, 2015, 4:22:38 PM11/4/15
to
On Wednesday, November 4, 2015 at 7:44:44 PM UTC+1, Antologiko wrote:
> Grazie a tutti delle risposte. Aggiungo (chiedo venia per la distrazione) che il grafo è stato implementato tramite liste di adiacenza.
>
> Mi è però venuto un dubbio:
> nei grafi orientati, il DFS si muove per definizione sempre in direzione
> dei "figli"?
> Perché in questo caso, prendendo un nodo a caso, col DFS potrebbero non
> essere raggiunti i suoi "avi", pur essendo il grafo connesso.
>
Giusto, ben detto :)
> Grazie a tutti delle risposte. Aggiungo (chiedo venia per la distrazione) che il grafo è stato implementato tramite liste di adiacenza.
>
> Mi è però venuto un dubbio:
> nei grafi orientati, il DFS si muove per definizione sempre in direzione
> dei "figli"?
> Perché in questo caso, prendendo un nodo a caso, col DFS potrebbero non
> essere raggiunti i suoi "avi", pur essendo il grafo connesso.
>
Allora, se del tuo grafo non sai proprio nulla, per sapere se il tuo grafo
è un DAG basta che provi a farne l'ordinamento topologico: se non puoi,
non è un DAG.
Se lo è, quando è ordinato conosci il primo vertice! ;)
Ciao!
fma...@gmail.com
Nov 4, 2015, 4:27:07 PM11/4/15
to
On Wednesday, November 4, 2015 at 9:42:35 PM UTC+1, ADPUF wrote:
> fma...@gmail.com 21:54, martedì 3 novembre 2015:
> fma...@gmail.com 21:54, martedì 3 novembre 2015:
> > Scegli un nodo a caso, fai un DFS. Se, durante il percorso,
> > trovi un nodo che già è stato visitato il grafo ha un ciclo.
> > Se, quando ha finito, ci sono nodi che non sono stati
> > visitati il grafo non è connesso.
>
> Scusa l'abissale ignoranza, ma che cosa è DFS?
>
Depth-First Search.
> > trovi un nodo che già è stato visitato il grafo ha un ciclo.
> > Se, quando ha finito, ci sono nodi che non sono stati
> > visitati il grafo non è connesso.
>
> Scusa l'abissale ignoranza, ma che cosa è DFS?
>
Non mi sembra abbia una traduzione in Italiano - si contrappone al BFS
(Breadth-First Search) nel senso che il primo visita andando prima in
"profondità", il secondo visita andando in.. "ampiezza".
Sono sia logicamente che a livello di pseudocodice molto simili, ma hanno
implementazioni e proprietà abbastanza diverse.
Ciao!
ADPUF
Nov 5, 2015, 4:01:58 PM11/5/15
to
fma...@gmail.com 22:27, mercoledì 4 novembre 2015:
Sei giovane?
Purtroppo adesso si fa tutto in inglisc...
> si contrappone al BFS (Breadth-First Search) nel senso che il
> primo visita andando prima in "profondità", il secondo visita
> andando in.. "ampiezza".
Appunto ricerca in ampiezza (prima tutti i fratelli, come nei
regni arabi) e ricerca in profondità (prima il primo figlio,
come nei regni europei).
Si studiava in informatica, no?
> Sono sia logicamente che a livello di pseudocodice molto
> simili, ma hanno implementazioni e proprietà abbastanza
> diverse.
Boh, adesso mi ricordo che c'era un librettino divulgativo
Zanichelli, di un certo Oystein Ore, sui grafi.
Ma non era un testo di informatica.
--
AIOE ³¿³
> On Wednesday, November 4, 2015 at 9:42:35 PM UTC+1, ADPUF
>> fma...@gmail.com 21:54, martedì 3 novembre 2015:
>> > Scegli un nodo a caso, fai un DFS. Se, durante il
>> > percorso, trovi un nodo che già è stato visitato il grafo
>> > ha un ciclo. Se, quando ha finito, ci sono nodi che non
>> > sono stati visitati il grafo non è connesso.
>>
>> Scusa l'abissale ignoranza, ma che cosa è DFS?
>>
>
> Depth-First Search.
> Non mi sembra abbia una traduzione in Italiano -
Certo che c'è.
>> > Scegli un nodo a caso, fai un DFS. Se, durante il
>> > percorso, trovi un nodo che già è stato visitato il grafo
>> > ha un ciclo. Se, quando ha finito, ci sono nodi che non
>> > sono stati visitati il grafo non è connesso.
>>
>> Scusa l'abissale ignoranza, ma che cosa è DFS?
>>
>
> Depth-First Search.
> Non mi sembra abbia una traduzione in Italiano -
Sei giovane?
Purtroppo adesso si fa tutto in inglisc...
> si contrappone al BFS (Breadth-First Search) nel senso che il
> primo visita andando prima in "profondità", il secondo visita
> andando in.. "ampiezza".
regni arabi) e ricerca in profondità (prima il primo figlio,
come nei regni europei).
Si studiava in informatica, no?
> Sono sia logicamente che a livello di pseudocodice molto
> simili, ma hanno implementazioni e proprietà abbastanza
> diverse.
Zanichelli, di un certo Oystein Ore, sui grafi.
Ma non era un testo di informatica.
--
AIOE ³¿³
fma...@gmail.com
Nov 5, 2015, 4:31:12 PM11/5/15
to
On Thursday, November 5, 2015 at 10:01:58 PM UTC+1, ADPUF wrote:
> fma...@gmail.com 22:27, mercoledì 4 novembre 2015:
> > On Wednesday, November 4, 2015 at 9:42:35 PM UTC+1, ADPUF
> >> fma...@gmail.com 21:54, martedì 3 novembre 2015:
> >> > Scegli un nodo a caso, fai un DFS. Se, durante il
> >> > percorso, trovi un nodo che già è stato visitato il grafo
> >> > ha un ciclo. Se, quando ha finito, ci sono nodi che non
> >> > sono stati visitati il grafo non è connesso.
> >>
> >> Scusa l'abissale ignoranza, ma che cosa è DFS?
> >>
> >
> > Depth-First Search.
> > Non mi sembra abbia una traduzione in Italiano -
>
>
> Certo che c'è.
> Sei giovane?
> Purtroppo adesso si fa tutto in inglisc...
>
Non sono di certo vecchio :) e forse all'università ho studiato queste cose
> fma...@gmail.com 22:27, mercoledì 4 novembre 2015:
> > On Wednesday, November 4, 2015 at 9:42:35 PM UTC+1, ADPUF
> >> fma...@gmail.com 21:54, martedì 3 novembre 2015:
> >> > Scegli un nodo a caso, fai un DFS. Se, durante il
> >> > percorso, trovi un nodo che già è stato visitato il grafo
> >> > ha un ciclo. Se, quando ha finito, ci sono nodi che non
> >> > sono stati visitati il grafo non è connesso.
> >>
> >> Scusa l'abissale ignoranza, ma che cosa è DFS?
> >>
> >
> > Depth-First Search.
> > Non mi sembra abbia una traduzione in Italiano -
>
>
> Certo che c'è.
> Sei giovane?
> Purtroppo adesso si fa tutto in inglisc...
>
in Italiano (anche se, in effetti, non credo) - ma da anni leggo solo quella
sigla, penso ormai sia uno standard anche in Italia.
Dovrei cercare qualche pubblicazione relativa all'argomento in Italiano (ne
fanno ancora? mi sa di no..) e vedere come la scrivono.
> > si contrappone al BFS (Breadth-First Search) nel senso che il
> > primo visita andando prima in "profondità", il secondo visita
> > andando in.. "ampiezza".
>
> Appunto ricerca in ampiezza (prima tutti i fratelli, come nei
> regni arabi) e ricerca in profondità (prima il primo figlio,
> come nei regni europei).
> Si studiava in informatica, no?
>
> > Sono sia logicamente che a livello di pseudocodice molto
> > simili, ma hanno implementazioni e proprietà abbastanza
> > diverse.
>
> Boh, adesso mi ricordo che c'era un librettino divulgativo
> Zanichelli, di un certo Oystein Ore, sui grafi.
> Ma non era un testo di informatica.
>
avrei proprio idea..
Ogni tanto, per ricordarmi che sono un programmatore (e non un bullone
del sistema produttivo) faccio qualche gara di programmazione - e questi
due algoritmi (così come un ordinamento topologico) sono "blocchi base"
come possono esserlo un selection sort o un binary search. Sinceramente,
il ricordo di come o dove li ho imparati è abbastanza confuso..
Ciao!
ADPUF
Nov 6, 2015, 4:39:43 PM11/6/15
to
fma...@gmail.com 22:31, giovedì 5 novembre 2015:
>> > Non mi sembra abbia una traduzione in Italiano -
>>
>>
>> Certo che c'è.
>> Sei giovane?
>> Purtroppo adesso si fa tutto in inglisc...
>>
>
> Non sono di certo vecchio :) e forse all'università ho
> studiato queste cose in Italiano (anche se, in effetti, non
> credo) - ma da anni leggo solo quella sigla, penso ormai sia
> uno standard anche in Italia. Dovrei cercare qualche
> pubblicazione relativa all'argomento in Italiano (ne fanno
> ancora? mi sa di no..) e vedere come la scrivono.
Vedi, quando si fece l'Italia nell'Ottocento, e anche prima, e
anche dopo, nessuno si sognava di usare il francese o il
tedesco o l'inglese nelle università italiane.
Eppure il mondo accademico non era chiuso e dialogava con
l'estero.
E' una questione più importante di quel che sembra.
Adesso sono più pigri e non hanno voglia di tradurre.
Bon tanto io tra cento anni sarò morto.
--
AIOE ³¿³
>> > Non mi sembra abbia una traduzione in Italiano -
>>
>>
>> Certo che c'è.
>> Sei giovane?
>> Purtroppo adesso si fa tutto in inglisc...
>>
>
> Non sono di certo vecchio :) e forse all'università ho
> studiato queste cose in Italiano (anche se, in effetti, non
> credo) - ma da anni leggo solo quella sigla, penso ormai sia
> uno standard anche in Italia. Dovrei cercare qualche
> pubblicazione relativa all'argomento in Italiano (ne fanno
> ancora? mi sa di no..) e vedere come la scrivono.
anche dopo, nessuno si sognava di usare il francese o il
tedesco o l'inglese nelle università italiane.
Eppure il mondo accademico non era chiuso e dialogava con
l'estero.
E' una questione più importante di quel che sembra.
Adesso sono più pigri e non hanno voglia di tradurre.
Bon tanto io tra cento anni sarò morto.
--
AIOE ³¿³
fma...@gmail.com
Nov 7, 2015, 5:24:04 AM11/7/15
to
On Friday, November 6, 2015 at 10:39:43 PM UTC+1, ADPUF wrote:
> fma...@gmail.com 22:31, giovedì 5 novembre 2015:
> fma...@gmail.com 22:31, giovedì 5 novembre 2015:
> > Non sono di certo vecchio :) e forse all'università ho
> > studiato queste cose in Italiano (anche se, in effetti, non
> > credo) - ma da anni leggo solo quella sigla, penso ormai sia
> > uno standard anche in Italia. Dovrei cercare qualche
> > pubblicazione relativa all'argomento in Italiano (ne fanno
> > ancora? mi sa di no..) e vedere come la scrivono.
>
> Vedi, quando si fece l'Italia nell'Ottocento, e anche prima, e
> anche dopo, nessuno si sognava di usare il francese o il
> tedesco o l'inglese nelle università italiane.
>
> Eppure il mondo accademico non era chiuso e dialogava con
> l'estero.
>
> E' una questione più importante di quel che sembra.
>
> Adesso sono più pigri e non hanno voglia di tradurre.
>
> Bon tanto io tra cento anni sarò morto.
>
L'unico parere che ho a riguardo, è che non esiste nulla di peggio di quando
> > studiato queste cose in Italiano (anche se, in effetti, non
> > credo) - ma da anni leggo solo quella sigla, penso ormai sia
> > uno standard anche in Italia. Dovrei cercare qualche
> > pubblicazione relativa all'argomento in Italiano (ne fanno
> > ancora? mi sa di no..) e vedere come la scrivono.
>
> Vedi, quando si fece l'Italia nell'Ottocento, e anche prima, e
> anche dopo, nessuno si sognava di usare il francese o il
> tedesco o l'inglese nelle università italiane.
>
> Eppure il mondo accademico non era chiuso e dialogava con
> l'estero.
>
> E' una questione più importante di quel che sembra.
>
> Adesso sono più pigri e non hanno voglia di tradurre.
>
> Bon tanto io tra cento anni sarò morto.
>
trovi l'unico paper/testo/articolo che esiste su un certo argomento,
ma è in cinese.
Ciao!
0 new messages