Newsgroup: it.comp.lang.c++
Titolo: Algoritmo trova cicli

Scusate il subject, mi rendo conto che fa schifo.
Sto cercando un algoritmo che mi permetta di trovare un ciclo
all'interno di un grafo. Per intenderci, un algoritmo che mi determini
(se esiste) un cammino che tocchi tutti i nodi. 
Attenzione: non e' il TSP, perche' non mi interessa che sia di costo
minimo o il piu' breve. Mi interessa che sia un ciclo.
TIA
-- 
"A pensar male si pecca, ma spesso ci s'azzecca..."
Saluti 	 		      << Linux Powered >>			 
LIBRA               e-mail: metti "libero" al posto di "NOSPAM"  

 (se esiste) un cammino che tocchi tutti i nodi.
Mi pare che con una DFS (depth-first-search) puoi catalogare gli archi in
diversi modi :
-archi all'indietro
-archi in avanti
-archi dell'albero
-archi di attraversamento
e mi pare che un grafo orientato è ciclico solo se ha archi all'indietro.
Ciao.

(se esiste) un cammino che tocchi tutti i nodi. 
Calma un secondo: un "ciclo" č ben diverso da un "cammino che tocchi
tutti i nodi di un grafo"!!
Se ti serve un ciclo basta una DFS, appena hai un back edge hai
trovato un ciclo. Se ti serve un cammino che passi per tutti i nodi č
un po' piů dura. Ti posso dire che sicuramente esiste se il grafo č
fortemente connesso (condizione sufficiente ma molto non necessaria).
Se proprio ti serve posso cercarti un algoritmo perň abbi pazienza ;)

 diversi modi :
Qualche link?
Grazie


 trovato un ciclo. 
Ok, mi puoi indirizzare verso un po' di teoria della DFS?
Grazie.


Ok, mi puoi indirizzare verso un po' di teoria della DFS?
Un buon libro di algoritmi e strutture dati è quello che fa per te :)
Quello su cui ho studiato io, è l'ottimo "Introduction to Algorithms"
di Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest  (si,
proprio lui, la R di RSA!)
http://www.amazon.co.uk/exec/obidos/ASIN/0262530910/202-3143942-3557458
Se vuoi qualcosa in internet una semplice ricerca di "graph theory"
dovrebbe portarti a centinaia di pagine di corsi universitari in cui
puoi trovare molte cose interessanti, anche se magari non con il
sistematico metodo del Cormen.

 "A pensar male si pecca, ma spesso ci s'azzecca..."
Siete OT, scambiarvi delle e-mail private costa troppo?
Questo newsgroup si occupa del linguaggio C++ in quanto tale, e non di
aspetti specifici di particolari implementazioni. Per questo non e' il
posto piu' adatto per porre domande specifiche come la tua.
Potresti avere piu' fortuna su uno dei seguenti gruppi:
Per Win32 (95, 98, NT): it.comp.programmare.win32
Per Dos/Win 3.x: it.comp.os.dos
Per Linux:      it.comp.os.linux.development
Per C++Builder: i gruppi borland.public.cppbuilder.*, disponibili sul
                server 
newsgroups.borland.com
 (prevalentemente in
                inglese, ma si puo' postare anche in italiano)
Grazie.
-- 
Posted from 
flopiano.mm.eutelsat.org
 [194.214.173.28] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 CUT
Prima di scrivere, PENSATE! Implementare un algoritmo platform-indipendent 
(come questo) in C++ da quando è OT qui????
-- 
Luc.

 (come questo) in C++ da quando è OT qui????
Non mi sembra che sia stato tirato in discussione il C++, se a Libra
qualcuno gli dava un
bello zip con l'algoritmo da lui cercato scritto in ADA era felice con un
sorriso
da orecchio ad orecchio.
Lo hai letto il manifesto, grande Pensatore?
Poi invece che inveire cosi' non potresti essere un po + ? (notare che basta
che tu
sia solo un po "+" ). La tua ragazza ieri sera ti ha dato buca?


 scritto in ADA era felice con un sorriso da orecchio ad orecchio.
Avendo postato su un ng di C++ pensavo fosse sottinteso che volessi 
riferirmi al C++.
Non l'ho specificato, anche perche' in un messaggio di poco precedente a 
quello che ha originato questo thread lo avevo detto (ma ovviamente non 
pretendo che tu abbia letto tutti i miei messaggi).
Comunque, lo ribadisco, mi interessa il C/C++.
-- 
"A pensar male si pecca, ma spesso ci s'azzecca..."
Saluti 	 		      << Linux Powered >>			 


 riferirmi al C++.
Lascia stare, Tanuzzo non sa quel che dice... 8-PPP
-- 
Luc.

 sia solo un po "+" ). La tua ragazza ieri sera ti ha dato buca?
Io sarei sposato, e tu quanti anni hai? 14?
-- 
Luc.


Be allora che vuol dire che non ti puo andare buca ?
Comunque quasi 30 (il 6 Nov.).


Siete OT, scambiarvi delle e-mail private costa troppo?
No, secondo il manifesto č IT parlare di algoritmi in C++, il fatto
che nel messaggio non sia specificato il linguaggio lascia intendere
che l'OP lo voglia in C++.
-- 
Marco Barisione (ICQ 84277092)

 Comunque quasi 30 (il 6 Nov.).
Urka, 2 più di me... chi l'avrebbe mai detto... 8/
-- 
Luc.

 
http://www.amazon.co.uk/exec/obidos/ASIN/0262530910/202-3143942-3557458
personalmente consiglio "Algoritmi in C" di Sedgewick (esiste anche 
"Algortimi in C++", ma non l'ho letto). Parla abbastanza approfonditamente 
anche dei grafi; trovi una mia recensione su 
cpp.programmazione.it
ciao Anto
-- 
Antonio Cuni, 19 anni, studente
Brainbench C++ Master: 4.6, higher than 98% of all previous test takers.
C Language: 3.32, higher than 79% of all previous test takers.
Guida C/C++ di Programmazione.it: 
http://cpp.programmazione.it

anche dei grafi; trovi una mia recensione su 
cpp.programmazione.it
Qualcuno che l'ha letto mi sa dire com'è "algoritmi in C++"?



Prova con  :
www.dsi.unive.it/~ASD

AHHHHHHHHHHHH!!!
Ma allora è un vizio!!!
Ragazzi, ma questo qui passa le giornate cosi??
Se notate in altri post ha proprio la firma standard per quando uno è OT! Ma
tu programmi? Sei umano? O una entita virtuale?
Dome
--
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
PC Brain Official Web Site
http://digilander.iol.it/pcbrain
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

 Dome
Avrai sbagliato mira ?
-- 
Posted from 
dell-01.mm.eutelsat.org
 [194.214.173.17] 


 Qualcuno che l'ha letto mi sa dire com'h "algoritmi in C++"?
Ho la traduzione italiana della prima edizione (oggi RS ha pubblicato nuovi
testi).
Dal punto di vista degli algoritmi non e' male. Dal punto di vista del C++ e'
terribilmente obsoleto.
Inoltre, quando si parla di algoritmi, molti dimenticano che la trilogia di
Knuth e' ancora una bibbia attuale su tutti gli algoritmi fondamentali.
--
Andrea Ferro
---------
Brainbench C++ Master. Scored higher than 97% of previous takers
Scores: Overall 4.46, Conceptual 5.0, Problem-Solving 5.0
More info 
http://www.brainbench.com/transcript.jsp?pid=2522556

terribilmente obsoleto.
Allora tu cosa consiglieresti la versione per C o C++?


 wrote in message
news:3bb1ee7c...@News.CIS.DFN.DE...

Considerando che l'ultima edizione delle due serie e' composta da piu' parti e
che nella serie C++ sono state pubblicate solo le prime 4 (mancano i grafi)
mentre per la serie C e' gia' disponibile la 5 (da venti giorni).
Considerando che quello che conta sono gli algoritmi e non l'implementazione e
che sospetto la versione C++ sia comunque poco OO.
Io dico di comperare:
Algorithms in C, Parts 1-5 (Bundle)
Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms
Paperback - 1200 pages 3rd edition (September 6, 2001)
Addison-Wesley Pub Co; ISBN: 0201756080
Che trovi su amazon a $74.99
(
http://www.amazon.com/exec/obidos/ASIN/0201756080/qid=1001518110/sr=2-3/ref=sr_
8_19_3/103-8695966-8626254) ed e' al momento il meglio (credo: in realtà non
l'ho letto, ma certamente comprende tutto quello che c'era nella prima
edizione!!).


 Addison-Wesley Pub Co; ISBN: 0201756080
Non so se lo hai letto, ma rispetto ad "Algoritmi + strutture dati =
programmi" (che non sto più trovando!!!:(((
è più completo?
Cioè, è il triplo di dimensione, però chi tratta meglio gli argomenti
presentati da entrambi?
Grazie
--
Luigi
byte...@hotmail.com
http://web.tiscali.it/luigi_web
ICQ #46240443

 i grafi) mentre per la serie C e' gia' disponibile la 5 (da venti giorni).
non ho capito: stai dicendo che il libro che conprende gli algoritmi sui 
grafi e' disponibile solo da venti giorni? Io l'ho comprato questa 
primavera (ed era una ristampa) e i capitoli sui grafi c'erano, eccome!


 presentati da entrambi?
Non so risponderti con certezza perche' non l'ho letto. Pero' e' certamente il
trattato di algoritmi uscito piu' di recente, scritto da un autore che gli
algoritmi li puccia nel caffe' a colazione e il linguaggio usato per la
presentazione e' il C. Non so se RS sia diventato o meno un conoscitore del C++
(in algoritmi in C++ prima edizione non lo era di certo) ma il C lo conosce di
sicuro piuttosto bene!
Quindi dubito che in questo bundle manchino cose che erano presenti in testi
precedenti e dubito che l'uso fatto del linguaggio C sia scorretto.
Se non hai un testo sugli algoritmi o se cerchi un testo aggiornato rispetto a
quelli che hai, credo proprio che ti convenga prendere questo.


 primavera (ed era una ristampa) e i capitoli sui grafi c'erano, eccome!
Credo che tu stia parlando della vecchia edizione che era in un unico volume.
L'edizione nuova e' in 5 volumi. Ripeto: non l'ho ancora vista, ma se ti
riprendi il mio post precedente e vai a vedere il link ad Amazon (occhio che e'
rimasto spezzato in due linee, per cui devi ricomporlo) ti farai un'idea.


Ma sono 5 volumi da 240 pag. circa?


 
Io sono abbastanza propenso ad acquistarlo, ma non conosco il C, sto 
studiando  C++. Credi sia sufficiente un libro come "Linguaggio C - 2 ed".  
di K&R  per capire tutta la sintassi usata nel libro?
-- 
Luigi
--
bug windows [5] = {"95", "98", "NT", "Me", "2000"};
Email: 
byte...@hotmail.com
Web Site: 
http://web.tiscali.it/luigi_web
ICQ #46240443

 di Knuth e' ancora una bibbia attuale su tutti gli algoritmi fondamentali.
Ma allora meglio la trilogia di Knuth o la Pentalogia di Sedgevick?
-- 
Luigi


 di K&R  per capire tutta la sintassi usata nel libro?
Ripeto, non l'ho letto. Ma e' un testo che spiega gli algoritmi. Mi aspetto che
il C sia uasto come linguaggio di presentazione. Dubito che usi cose specifiche
e strane dil linguaggio. Quasi certamente potrai compilare gli esempi anche in
C++ cone nessuna o pochissime modifiche. Se conosci un minimo del C o del C++
dovrebbe essere sufficiente per capire il codice che presenta i vari algoritmi.
Cosi' ad occhio e conoscendo altri testi sugli algoritmi, una conoscenza di base
del C o del Pascal o Del C++ o persino di Java sono sufficienti a seguire il
discorso. Quello che comperi e' un testo sugli algoritmi, non una libreria. Se
vieni dal pascal e non sai nulla di C o C++ puoi avere un minimo di
tentennamenti a capire istruzioni come:
for ( int i=0; i<10; ++i )
o come
*p += 3;
o dichiarazioni come:
void *pv;
const int *pi;
e assegnamenti tipo
pi=(const int*)pv;
Ma se arrivi a capire queste, dubito che tu non riesca a seguire gli algoritmi
presentati (o almeno a seguirne la stragrande maggioranzza). E quelli che ancora
non capisci ... li capirai appena approfondisci leggermente il C++ o il C.
L'unico problema portesti trovarlo se vengono presentati algoritmi numerici
particolari facendo uso di alcune delle novità del C99. Ma ne dubito. E comunque
se capisci il concetto che sta dietro alla matematica del problema dovresti
persino riuscire a capire il sorgente anche senza conoscere il linguaggio.


 Ma allora meglio la trilogia di Knuth o la Pentalogia di Sedgevick?
Non ho letto la pentalogia di R.Sedgewick. In linea di massima credo che possa
essere piu' completa per certi aspetti e anche piu' moderna. Ma non credo che
tocci tutti gli argomenti toccati da D.Knuth (in cambio ne tocca certamente
altri). E se lo fa, in genere RS e' piu' orientato all'algoritmo in se che non
all'insegnamento delle basi. I testi di DK sono vecchiotti ma contengono tutte
le basi e sono scritti molto ma molto bene (e per quanto vecchi, praticamente
nessuno degli algoritmi presentati e' cambiato da allora!). E sono zeppi di
esercizi molto ben studiati. La formazione didattica di DK e' IMO migliore di
quella di RS. Per una corso di formazione che parta dalle basi e arrivi a
concetti anche abbastanza avanzati io consiglio ancora DK. Per un
approfondimento, certamente meglio RS. Naturalmente dico questo avendo letto DK
e conoscendo i vecchi testi di RS ma senza aver visto la nuova pentalogia. Per
esserne sicuro dovrei leggerla.


 di K&R  per capire tutta la sintassi usata nel libro?
Io ti consiglio di prendere l'edizione in inglese, perche' quella
italiana aveva fama pessima. A parte questo secondo me K&R resta il
punto di riferimento per tutti quelli che scrivono libri su linguaggi (e
parte della sua popolarita' il C lo deve alla disponibilita' di un libro
come questo).
Ciao,
Nicola
P.S. In dieci anni di programmazione in C ho comprato solo un altro
libro sul linguaggio: K&R, 1 ed. ...

Knuth e' ancora una bibbia attuale su tutti gli algoritmi fondamentali.
Sì' ma costa anche 150 dollari! Non mi sembra che sia molto a portata
di tasca per uno studente.
-- 
Marco Barisione (ICQ 84277092)
Su it.news.gruppi si sta discutendo della creazione di it.comp.lang
dove si parlerà dei linguaggi senza un proprio newsgroup e dei
confronti fra i diversi linguaggi.
Se sei interessato unisciti alla discussione.

 di tasca per uno studente.
Per mia esperienza i soldi spesi in libri sono raramente buttati. Alcuni libri
(come la trilogia in questione) sono praticamente eterni. DK ha ovviemente
aggiornato la sua opera con edizioni successive. Ma anche se hai la primissima
edizione, il contenuto e' ancora attualissimo.
Capisco che possa essere uno sforzo. Ma e' anche vero che nel giro di pochi anni
un buon programmatore arriverà ad avere un "bookshelf" del valore (all'acquisto)
di alcuni milioni. In generale c'e' molto piu' valore nel tenere aggiornata la
tua biblioteca personale che nel tener aggiornato il tuo HW. E in questa ottica
quelle 300 mila lire sono certamente ben spese.
Esiste poi la possibilità di comperare i volumi uno ad uno dilazionando la spesa
nel tempo. Magari alla fine hai speso di piu'. Pero' diluendo lo sforzo.
Eventualmente puoi rimandare il volume sui numeri casuali e sugli algoritmi
matematici (credo sia il secondo) se sei poco interessato a questa parte. O
sostituirlo temporaneamente con un altro testo piu' specifico se invece sei
interessato (per esempio il numerical recipes). Inoltre la trilogia, almeno in
teoria, e' solo l'inizio di un'opera in 7 volumi. Che pero' oramai molti
ritengono che DK non completerà mai.
In ogni caso non e' affatto obbligatorio avere il Knuth. Anche se e' credo
universalmente considerato la bibbia della programmazione (pre OO).


 di tasca per uno studente.
Uno studente in genere ha una bibioteca a portata di mano; almeno
quelli che sono in una citta' sede universitaria.
A proposito, ho letto di corsa i vari threads (sono stato assente per
un poco); il Sedgewick "5 parti" di cui parlate qualche messaggio
avanti non e' "del tutto" nuovo.  Le prime 4 parti sono in un volume
unico, con su scritto in rosso "third edition" e stampato nel 1998
(quindi e' una ristampa dell'ultima edizione precedente, magari
riveduta e corretta - l'ho avuto per le mani ma non l'ho letto).  La
quinta parte (quella sui grafi) e' in un secondo volume separato,
edito nel settembre 2001 (quindi nuova di stecca).  Tenete presente il
quanto se volete ordinarlo...  o, se volete, passate in una
biblioteca...
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it

quelle 300 mila lire sono certamente ben spese.
Già ma ho già in programma di comprarmi un bel libro su python (e poi
quando finalmente uscirà dovrò assolutamente comprare quello di Alex
Martelli!) e i soldi purtroppo non li guadagno. Comunque ci penserò ma
forse comprerò quello di Sedgevick visto che costa la metà e dite che
è comunque un buon libro.


quelli che sono in una citta' sede universitaria.
Ho iniziato ingegneria al politecnico di torino ma nella sede di
vercelli quindi mi sa che la biblioteca non sia poi molto fornita
comunque darò un'occhiata.


 h comunque un buon libro.
Non ne sono certo ma credo che sul python trovi tutto e poi ancora qualche cosa
aggratis su internet.
Prima di comperarti il libercolo magari verifica che sia veramente piu' completo
di quelli che trovi su internet.
E comunque IMO un libro su un linguaggio ha meno valore (negli anni) di un libro
piu' generale. Io di libri specifici su un linguaggio ne ho letti alcuni ma ne
ho comperato uno solo (l'ARM ai tempi dei primi lavori ANSI C++). A cui e'
seguito, se vuoi considerarlo un libro, lo standard stesso (in formato pdf per
19$). Naturalmente parlo di libri che parlano del linguaggio in se. Un libro
come quello di Alexandrescu pur essendo molto C++ specific non lo considero un
testo sul linguaggio.


 di K&R  per capire tutta la sintassi usata nel libro?
 
se conosci il C++ non hai alcuna difficolta' a seguire il discorso. Non ho 
controllato attentamente ma mi sembra che tutti gli esempi dovrebbero 
essere compilabili anche con un compilatore C++; solo dovresti cercare di 
capire cosa fa qualche funzionione della lib std del C che solitamente non 
e' usata in C++, come ad esempio malloc(); in ogni caso vai tranquillo che 
non ci saranno troppi problemi.


 leggerla.
non ho letto quelli di Knuth, ma a questo va aggiunto che spesso DK tratta 
i problemi in maniera piu' approfondita, anche dal punto di visto 
dell'analisi matematica: in piu' di un capitolo Sedgewick consigliaproprio 
i testi di Knuth per ulteriori approfondimenti.


 libro sul linguaggio: K&R, 1 ed. ...
E l'altro qual'è stato?
La 1ª ha buona fama (in italiano)?
Sai cosa ha la 2ª rispetto alla 1ª?  Non credo molto, sono entrambi piccoli
libri.
Ciao


Ma c'è la versione italiana della trilogia?
Da chi è edita?
Grazie


 biblioteca...
Ma allora č solo l'ultima parte nuova.


 libro sul linguaggio: K&R, 1 ed. ...
A proposito, anche se OT, sai se č prevista una terza edizione del libro?
Oppure i due autori si sono disinteressati al nuovo standard?
Ciao  Manlio Perillo

 universalmente considerato la bibbia della programmazione (pre OO).
e qual'e' invece la bibbia "in OO" (notate il latinismo di "in"; ecco a 
cosa serve il liceo ;-)? Mi viene in mette "Design Patterns", ma immagino 
che ci sia anche altro...


 che ci sia anche altro...
Ai tempi in cui usci' la prima edizione del Knuth, praticamente quasi tutto lo
scibile dell'informatica di base (ovvero non troppo specializzata) era compreso
in quell'opera. Oggi non credo proprio possa esistere una cosa corrispondete.
Inoltre l'OO non e' una cosa ben definita. Comprende tanti aspetti. Vi sono
molti testi che parlano di OOA (Analisi). Altri che parlano di OOD (Design). Poi
esistono vari linguaggi che supportano il paradigma OO in maniera piu' o meno
efficiente, e testi su ciascuno di questi. Poi esiste un ramo derivato che
potremmo considerare uno studio sull'utilizzo pratico di tecniche OO per lo
sviluppo di SW di dimensioni medie in tempi brevissimi e a budget ristretto da
parte di gruppi di lavoro di medie dimensioni (Extreme Programming, che ha
applicazioni anche al di fuori del contesto suddetto). Poi ci sono tutta una
serie di metodologie e filosofie che sono nate in anni recenti (o sono state
applicate in anni recenti allo sviluppo SW) e che pertanto si sposano bene con
l'OO dato che oramai l'OO e' onnipresente e pertanto qualunque cosa nuova non
puo' prescindere dall'OO. Per esempio i Design Patterns che a livello filosofico
si sarebbero potuti anche applicare ai tempi dell'analisi strutturata o dello
sviluppo di sistemi mainframe in COBOL, ma che essendosi diffusi solo in tempi
recenti di fatto si sono evoluti in un ambiente permeato dal paradigma OO.
Comunque se cerchi la bibbia (o la bibbietta, in un certo senso) della filosofia
dei Design Patterns, certamente il testo della GoF e' il testo giusto in ambito
informatico (e l'opera di Cristopher Alexander la vera bibbia in senso
generale).


 Da chi è edita?
Mi pare di si. Ma non so se sia stata tradotta anche l'ultima edizione. Non
ricordo chi fosse l'editore. Prova a fare un giro negli stand editoriali allo
SMAU prossimo venturo (se ci vai ancora a quella ciofega di mostra).


 bibbia in senso generale).
qual'e' l'opera di Alexander?


 qual'e' l'opera di Alexander?
Una serie di testi di architettura (Christopher Alexander, che si scrive con la
h che era rimasta nel dito quando ho postato l'altra volta, e' un architetto) di
cui quello piu' importante per il discorso dei pattern e' "The Timeless Way Of
Building".
