Ajuda MostSpanningTree

[HIT_Braga]

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

[HappyHippyHippo]

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

[HIT_Braga]

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

[KTachyon]

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.

[HappyHippyHippo]

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