HIT_Braga Posted June 23, 2012 at 07:40 PM Report Share #465148 Posted June 23, 2012 at 07:40 PM Boas pessoal. Estou aqui com um problema, e ainda não descortinei como raio vou fazer isto. Tenho uma estrutura do seguinte tipo: typedef struct lan{ char tipo1[30]; char tipo2[30]; char id1[30]; char id2[30]; int peso; struct lan *prox; }Lan; Ou seja na estrutura vou guardar nada mais nada menos do que arcos(Vertice Origem(tipo1,id1) Vertice Destino(tipo2,id2) e peso). Agora preciso de implementar o algoritmo de Kruskal ou Prim para resolver a a árvore minima, mas não consigo fazer isso. As implementações que vejo são "todas" com matrizes de adjacencia e eu estou aqui à nora. Será que alguém pode dar umas dicas de como começar ? Sds, HIT " Elogios não me elevam, ofensas não me rebaixam, sou o que sou e não o que acham! " Link to comment Share on other sites More sharing options...
HappyHippyHippo Posted June 23, 2012 at 08:07 PM Report Share #465152 Posted June 23, 2012 at 08:07 PM 1º - escolher um nó aleatório (normalmente o primeiro da lista para simplificar) entras num ciclo: - escolhes o arco de menor peso que liga um nó já escolhido a um ainda não escolhido - adicionas o nó e o arco escolhido - continuar até não teres mais nós IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
HIT_Braga Posted June 23, 2012 at 11:28 PM Author Report Share #465171 Posted June 23, 2012 at 11:28 PM Boas. Obrigado pela resposta HappyHippyHippo, mas ainda assim continuo com duvidas, pois executando(em papel) tal como dizes fico numa situação em que não funciona. Tenho uma grafo assim: ORIGEM#DESTINO#PESO 1#4#10 4#3#3 3#2#1 2#9#9 3#6#9 6#8#3 8#11#4 4#5#9 5#7#10 7#10#7 5#6#1 7#8#7 10#11#3 O grafo é não orientado claro. Nesta situação o algoritmo não funciona, ou pelo menos eu não percebi ainda. Começa no Vertice 1. Sds, HIT " Elogios não me elevam, ofensas não me rebaixam, sou o que sou e não o que acham! " Link to comment Share on other sites More sharing options...
KTachyon Posted June 23, 2012 at 11:36 PM Report Share #465173 Posted June 23, 2012 at 11:36 PM Provavelmente não estarás a implementar bem. Quando adicionas um vértice tens que adicionar todas as arestas que ligam a outros vértices. No fundo seria uma estrutura "vértice", com um ponteiro para uma lista de estruturas "arestas", que têm um ponteiro para o vértice de destino e o peso. “There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.” -- Tony Hoare Link to comment Share on other sites More sharing options...
HappyHippyHippo Posted June 24, 2012 at 09:57 AM Report Share #465192 Posted June 24, 2012 at 09:57 AM (edited) Grafo original: +--+ +--+ +--+ +--+ +--+ | 1|--10--| 4|---9--| 5|--10--| 7|---7--|10| +--+ +--+ +--+ +--+ +--+ | | | | 3 1 7 3 | | | | +--+ +--+ +--+ +--+ +--+ | 2|---1--| 3|---9--| 6|---3--| 8|---4--|11| +--+ +--+ +--+ +--+ +--+ | 9 | +--+ | 9| +--+ Resultado do algoritmo, por passos : 1- escolha do um nó aleatório (1o) +--+ | 1| +--+ 2- escolha do arco de menor custo que "sai" do grafo ja criado (1<->4) +--+ +--+ | 1|--10--| 4| +--+ +--+ 3- escolha do arco de menor custo que "sai" do grafo ja criado (4<->3) +--+ +--+ | 1|--10--| 4| +--+ +--+ | 3 | +--+ | 3| +--+ 4- escolha do arco de menor custo que "sai" do grafo ja criado (3<->2) +--+ +--+ | 1|--10--| 4| +--+ +--+ | 3 | +--+ +--+ | 2|---1--| 3| +--+ +--+ 5- escolha do arco de menor custo que "sai" do grafo ja criado (4<->5 ou 3<->6 ou 2<->9) +--+ +--+ +--+ | 1|--10--| 4|---9--+ 5+ +--+ +--+ +--+ | 3 | +--+ +--+ | 2|---1--| 3| +--+ +--+ 6- escolha do arco de menor custo que "sai" do grafo ja criado (5<->6) +--+ +--+ +--+ | 1|--10--| 4|---9--+ 5+ +--+ +--+ +--+ | | 3 1 | | +--+ +--+ +--+ | 2|---1--| 3| | 6| +--+ +--+ +--+ 7- escolha do arco de menor custo que "sai" do grafo ja criado (6<->8) +--+ +--+ +--+ | 1|--10--| 4|---9--+ 5+ +--+ +--+ +--+ | | 3 1 | | +--+ +--+ +--+ +--+ | 2|---1--| 3| | 6|---3--+ 8+ +--+ +--+ +--+ +--+ 8- escolha do arco de menor custo que "sai" do grafo ja criado (8<->11) +--+ +--+ +--+ | 1|--10--| 4|---9--+ 5+ +--+ +--+ +--+ | | 3 1 | | +--+ +--+ +--+ +--+ +--+ | 2|---1--| 3| | 6|---3--+ 8+---4--+11+ +--+ +--+ +--+ +--+ +--+ 9- escolha do arco de menor custo que "sai" do grafo ja criado (11<->10) +--+ +--+ +--+ +--+ | 1|--10--| 4|---9--+ 5+ |11| +--+ +--+ +--+ +--+ | | | 3 1 3 | | | +--+ +--+ +--+ +--+ +--+ | 2|---1--| 3| | 6|---3--+ 8+---4--+11+ +--+ +--+ +--+ +--+ +--+ 10- escolha do arco de menor custo que "sai" do grafo ja criado (7<->8 ou 7<->10) +--+ +--+ +--+ +--+ +--+ | 1|--10--| 4|---9--+ 5+ | 7|---7--|11| +--+ +--+ +--+ +--+ +--+ | | | 3 1 3 | | | +--+ +--+ +--+ +--+ +--+ | 2|---1--| 3| | 6|---3--+ 8+---4--+11+ +--+ +--+ +--+ +--+ +--+ 11- escolha do arco de menor custo que "sai" do grafo ja criado (2<->9) +--+ +--+ +--+ +--+ +--+ | 1|--10--| 4|---9--+ 5+ | 7|---7--|11| +--+ +--+ +--+ +--+ +--+ | | | 3 1 3 | | | +--+ +--+ +--+ +--+ +--+ | 2|---1--| 3| | 6|---3--+ 8+---4--+11+ +--+ +--+ +--+ +--+ +--+ | 9 | +--+ | 9| +--+ não venhas dizer que o algoritmo está errado !!! Edited June 24, 2012 at 10:07 AM by HappyHippyHippo 1 Report IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now