graphe - Comment obtenir le sous-ensemble avec poids minimum?

Question

Voici un accise:

considérer le problème de trouver un sous-ensemble connecté poids minimum T d'arêtes d'un graphe connexe pondéré G. Le poids de T est la somme de tous les poids des arêtes dans une T.Give algorithme efficace pour calculer le poids minimum connecté sous T.

Voici ce que j'ai:

1. je dois assumer les poids sont mélangés par les deux positives et négatives. Seul le mélange des deux types de poids peut avoir un sens pour cette accise. Je vais trier les bords en premier, de sorte que les bords négatifs viendront en premier.

2. Je considère utiliser l'algorithme de Kruskal, mais devrait être avec quelques modifications

3. Parce que je salue les bords négatifs, je vais essayer d'ajouter autant de bords négatifs possible.

4. En outre, certains bords positifs peuvent être ajoutés au cas où tous les bords négatifs ne sont pas connectés et ils peuvent avoir besoin de certains bords positifs comme ponts.

---

Ok, au-dessus est ma façon de penser. Mais quand j'essaie de me salir les mains, je suis coincé.

Comment puis-je toujours enregistrer les poids minimums possibles?

Par exemple,

{0, 1} est un poids -20

{2, 3} est un poids -10

si {1, 3} a un poids de 11, alors bien sûr, je ne veux pas {1, 3}

ou si {1, 3} a un poids de 9, alors je veux

Avec quel type de structure de données, je peux toujours garder le poids minimum et les sommets pour que nous ça va?

---

Il convient de noter que le sous-ensemble cette accise cherche pour but à edges.

Considérons le problème de trouver un poids minimum connecté sous-ensemble T de bords d'un graphe connexe pondéré G

Cela signifie que tous les sommets doivent encore être inclus.

Aussi, il est plus d'un MST. Considérons que si un sommet a deux bords, l'un est -1, l'autre est -2. Dans un algorithme MST normal, seul le front de -2 sera pris. Mais dans cette accise, -1 et -2 doivent être prises pour réduire davantage le poids global.

Answer 1

Je pense que votre algorithme est déjà la plupart du temps correct, mais avec de légères modifications, il devient trivial à implémenter.

Tout d'abord, chaque bord doit être inclus afin de minimiser le poids résultant. Ensuite, calculez le nombre de composants connectés c. Si c=1, vous avez terminé. Sinon, vous avez besoin de c-1 bords positifs supplémentaires.

Maintenant, alors que vous ajoutez des arêtes négatives, considérez cela comme un processus d'algorithme de Kruskal. Tous les bords négatifs peuvent unir deux arbres dans la forêt de Kruskal. Cependant, vous ajoutez le bord négatif même si ses extrémités appartiennent au même arbre dans la forêt de Kruskal - contrairement à l'algorithme habituel de Kruskal où vous n'ajoutez que les arêtes qui unissent deux arbres différents.

Après cette phase, vous disposez d'un graphique de c composants connectés (ils ne peuvent plus être des arbres). Maintenant, continuez l'algorithme de Kruskal comme d'habitude. Traitez les bords positifs dans l'ordre croissant, en gardant une trace du nombre d'unions que vous avez faites avec des bords positifs. Une fois ce nombre atteint c-1, vous avez terminé. À propos, tout le processus de l'algorithme de Kruskal peut être facilement implémenté si vous représentez la forêt comme disjoint-set data structure. Il suffit de quelques lignes de code pour écrire, et après cela, il est trivial de garder une trace du nombre de syndicats qui ont été faits.

---

Certains pseudocode suit:

sort(edges); 
c := n; 
for edge in edges: 
    if edge.weight < 0: 
     if find(edge.firstEnd) != find(edge.secondEnd): 
      --c; 
     unite(edge.firstEnd, edge.secondEnd); 
    else: 
     if c == 1: break; 
     if find(edge.firstEnd) != find(edge.secondEnd): 
      unite(edge.firstEnd, edge.secondEnd); 
      --c; 

Ici unite et find sont les fonctions de structure de jeu de données disjointes.