Jump to content

Ajuda MostSpanningTree


HIT_Braga

Recommended Posts

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

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
Link to comment
Share on other sites

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

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

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 by HappyHippyHippo
  • Vote 1
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

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 account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.