Vue d’ensemble

L'algorithme d'Arbre Recouvrant Minimal (MST) calcule l'arbre recouvrant avec la somme minimale des poids des edges pour chaque composant connecté dans un graph.

Le MST a diverses applications, telles que la conception de réseaux, le clustering et les problèmes d'optimisation où la minimisation du coût ou du poids total est importante.

Concepts

Arbre Recouvrant

Un arbre recouvrant est un sous-graph connecté qui inclut tous les nodes d'un graph connecté G= = (V, E) (ou un composant connecté) et qui forme un arbre (c'est-à-dire, sans cercles). Il peut exister plusieurs arbres recouvrants pour un graph, et chaque arbre recouvrant doit avoir (|V| - 1) edges.

Les 11 nodes dans le graph ci-dessous, avec les 10 edges mis en évidence en rouge, forment un arbre recouvrant de ce graph :

Arbre Recouvrant Minimal (MST)

Le MST est l'arbre recouvrant qui a la somme minimale des poids des edges. La construction du MST commence à partir d'un node de départ donné. Le choix du node de départ n'affecte pas la validité de l'algorithme MST, mais il peut affecter la structure du MST et l'ordre dans lequel les edges sont ajoutés. Différents nodes de départ peuvent aboutir à différents MST, mais tous seront des MST valides pour le graph donné.

Après avoir attribué des poids aux edges dans l'exemple ci-dessus, les trois MST possibles avec différents nodes de départ sont mis en évidence en rouge ci-dessous :

Concernant la sélection des nodes de départ :

• Chaque composant connecté nécessite seulement un node de départ. Si plusieurs nodes de départ sont spécifiés, le premier sera considéré comme valide.
• Aucun MST ne sera calculé pour les composants connectés qui n'ont pas de node de départ spécifié.
• Les nodes isolés ne sont pas considérés comme des nodes de départ valides pour le calcul du MST.

Considérations

• L'algorithme MST ignore la direction des edges mais les calcule comme des edges non dirigés.

Syntaxe

• Commande : algo(mst)
• Paramètres :

Exemples

Le graph d'exemple est comme ci-dessous, le node A est un centre électrique, les nodes B~H sont les villages environnants. Chaque edge est étiqueté avec son UUID et la distance entre les emplacements connectés, ce qui représente la longueur de câble requise :

File Writeback

algo(mst).params({
  uuids: [1],
  edge_schema_property: 'distance'
}).write({
  file:{
    filename: 'solution'
    }
})

Résultats : Fichier solution

A--[107]--H
A--[108]--E
E--[111]--G
F--[113]--G
A--[101]--B
A--[104]--D
C--[103]--D

Direct Return

algo(mst).params({
  ids: 'A',
  edge_schema_property: '@connect.distance'
}) as mst 
return mst

Résultats : mst

Stream Return

algo(mst).params({
  uuids: [1],
  edge_schema_property: 'distance'
}).stream() as mst
with pedges(mst) as mstUUID
find().edges(mstUUID) as edges
return sum(edges.distance)

Résultats : 5.65