Algoritmo per ricavare albero data radice e foglie
Ciao a tutti, sono un programmatore quindi non sono molto esperto della teoria dei grafi,conoscendo solo alcuni degli algoritmo.
Il mio problema è questo: ho un grafo non orientato connesso e, specificando una radice e delle foglie, vorrei un algoritmo che mi ricavi un albero qualsiasi.
Conosco kruskal, prim, ecc. ma questi creano un albero minimo e basta...a me invece servirebbe creare un albero che abbia la radice che dico io e le foglie che specifico...
Il mio problema è questo: ho un grafo non orientato connesso e, specificando una radice e delle foglie, vorrei un algoritmo che mi ricavi un albero qualsiasi.
Conosco kruskal, prim, ecc. ma questi creano un albero minimo e basta...a me invece servirebbe creare un albero che abbia la radice che dico io e le foglie che specifico...
Risposte
[xdom="vict85"]Sposto in informatica.[/xdom]
[ot]
Probabilmente i programmatori sono tra quelli che conoscono meglio la teoria dei grafi..[/ot]
Ma in questo caso credo comunque che, a patto che quell'albero esista*, si possa semplicemente creare con una visita al grafo qualsiasi partendo dalla radice e fermandosi alle foglie.
* Non c'è infatti alcuna garanzia che questo albero esista.. Se tutti i percorsi tra una radice e qualche altra foglia passano per una delle foglie non puoi avere tale albero.
Ciao a tutti, sono un programmatore quindi non sono molto esperto della teoria dei grafi,conoscendo solo alcuni degli algoritmo.
Probabilmente i programmatori sono tra quelli che conoscono meglio la teoria dei grafi..[/ot]
Ma in questo caso credo comunque che, a patto che quell'albero esista*, si possa semplicemente creare con una visita al grafo qualsiasi partendo dalla radice e fermandosi alle foglie.
* Non c'è infatti alcuna garanzia che questo albero esista.. Se tutti i percorsi tra una radice e qualche altra foglia passano per una delle foglie non puoi avere tale albero.
Risolto...basta assegnare dei pesi agli archi e poi applicare kruskal.
Ho assegnato i seguenti valori ai vertici:
radice:0
relay: 1
foglia: 2
il peso dell'arco è dato dalla somma dei pesi dei nodi, quindi un arco che congiunge la radice con un relay ha peso 0+1=1, relay foglia 1+2=3 foglia foglia 2+2=4.
Applicando kruskal su un grafo con questi pesi farà in modo, per come è fatto l'algoritmo, di creare un albero con effettivamente la radice e le foglie che dico io.
Ovviamente implemento già dei controlli per assicurarmi ci sia una sola radice e che il grafo sia connesso
Ho assegnato i seguenti valori ai vertici:
radice:0
relay: 1
foglia: 2
il peso dell'arco è dato dalla somma dei pesi dei nodi, quindi un arco che congiunge la radice con un relay ha peso 0+1=1, relay foglia 1+2=3 foglia foglia 2+2=4.
Applicando kruskal su un grafo con questi pesi farà in modo, per come è fatto l'algoritmo, di creare un albero con effettivamente la radice e le foglie che dico io.
Ovviamente implemento già dei controlli per assicurarmi ci sia una sola radice e che il grafo sia connesso
Puoi scrivere il codice o lo psuedocodice?
Un confronto mi sarebbe utile visto che sembra funzionare ma non sono ancora sicuro.
L'algoritmo di kruskal è qua:
1.Sort the edges of G into decreasing order by weight. Let T be the set of edges comprising the maximum weight spanning tree. Set T = ∅.
2.Add the first edge to T.
3.Add the next edge to T if and only if it does not form a cycle in T. If there are no remaining edges exit and report G to be disconnected.
4.If T has n−1 edges (where n is the number of vertices in G) stop and output T . Otherwise go to step 3.
Ora, io mi trovo che se assegno i pesi agli edges del mio grafo in questo modo:
radice->relay: 1
relay->relay: 2
relay->foglia: 3
ottengo effettivamente un albero come lo voglio io, quindi con la radice specificata e le foglie specificate.
L'algoritmo di kruskal è qua:
1.Sort the edges of G into decreasing order by weight. Let T be the set of edges comprising the maximum weight spanning tree. Set T = ∅.
2.Add the first edge to T.
3.Add the next edge to T if and only if it does not form a cycle in T. If there are no remaining edges exit and report G to be disconnected.
4.If T has n−1 edges (where n is the number of vertices in G) stop and output T . Otherwise go to step 3.
Ora, io mi trovo che se assegno i pesi agli edges del mio grafo in questo modo:
radice->relay: 1
relay->relay: 2
relay->foglia: 3
ottengo effettivamente un albero come lo voglio io, quindi con la radice specificata e le foglie specificate.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo