Trouver un arbre couvrant minimum à partir d'une liste d'adjacence où la liste d'adjacence se trouve dans un tableau de chaînes en utilisant l'algorithme Prims

StackOverflow https://stackoverflow.com/questions/9449967

Question

J'ai donc besoin d'aide pour trouver un moyen de trouver un arbre couvrant minimum. Supposons que j'ai mon graphique sous la forme d'une liste d'adjacence:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

La première lettre indique quel nœud vous regardez, et le nombre indique combien de connexions avec un autre nœud. Par exemple, A a deux connexions - une à B et moi. Après cela, le nombre qui suit les lettres indique simplement le poids d'un bord. B a du poids 12 et j'ai du poids 25. Donc j'avais initialement prévu de représenter ce truc comme un tableau de cordes appelé Graph[8]. Chaque ligne serait un emplacement différent dans le tableau. J'ai des difficultés à comprendre comment accomplir cela avec des primes ou des algorithmes de Kruskalls.

Était-ce utile?

La solution

Supposons que j'ai mon arbre sous la forme d'une liste d'adjacence

Il est important (pour votre compréhension) de noter que vous avez un graphique Dans ce genre de liste d'adjacence, mais je pense que c'était juste une faute de frappe. Je vais le proposer en tant que modification, mais je veux juste que vous en soyez conscient. Le fait qu'il s'agit d'un graphique et non d'un arbre peut être vu à partir de ces lignes:

A 2 B 12 I 25
B 3 C 10 H 40 I 8

Ici, vous avez déjà un cercle à Abi:

     A
  12/_\25
   B 8 I

Avoir un cercle par définition signifie qu'il ne peut pas être un arbre! Il y a encore une chose que l'on peut voir de la façon dont j'ai présenté ce sous-graphique: les bords ont des poids, pas les nœuds.

Jetons maintenant un coup d'œil à votre exemple fourni: 

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

Tout d'abord, nous pouvons voir que cette liste d'adjacence est incorrecte ou déjà optimisée pour vos besoins. Cela peut (par exemple) être vu à partir des lignes

E 2 F 60 G 38
F 0

La première ligne ici montre un avantage de E à F, mais la deuxième ligne dit que F avait un degré de 0, mais le degré est défini par les bords incidents!

C'est à quoi ressemblerait la liste d'adjacence s'il était «complet»:

A 2 B 12 I 25
B 4 A 12 C 10 H 40 I 8
C 3 B 10 D 18 G 55
D 2 C 18 E 44
E 3 D 44 F 60 G 38
F 1 E 60
G 3 C 55 E 38 H 35
H 3 B 40 G 35 I 35

Nous pouvons voir beaucoup de redondance parce que chaque bord se produit deux fois, c'est pourquoi votre liste d'adjacence «optimisée» convient mieux à vos besoins - serait-ce cet exemple «complet» que l'on ferait de nombreux chèques inutiles. Cependant, tu devrais seulement comptez sur cela si vous pouvez être sûr que toutes les données données à votre code sont déjà «optimisées» (ou plutôt dans ce format)! Je vais prendre cela comme une donnée à partir de maintenant.

Parlons de votre structure de données. Vous pouvez bien sûr utiliser votre éventail de chaînes proposé, mais pour être honnête, je préfère recommander quelque chose comme la structure de données proposée de @ Amirafghani. L'utilisation de son approche faciliterait votre travail (car il l'a déjà souligné - serait plus proche de votre la représentation mentale) et encore plus efficace (je suppose, ne comptez pas sur cette supposition;)) comme vous le feriez de nombreux Opérations sur les chaînes autrement. Dans le titre que vous avez demandé après l'algorithme de Prim, mais dans votre question réelle, vous avez dit Soit Prim's ou Kruskal. J'irai avec Kruskal simplement parce que son algorithme est beaucoup plus facile et vous semblez accepter les deux.

L'algorithme de Kruskal

L'algorithme de Kruskal est assez simple, c'est essentiellement:

  • Commencez avec chaque nœud, mais pas de bords

Répétez les éléments suivants aussi souvent que possible:

  • De tous les bords inutilisés / non choisis, choisissez celui avec le moins de poids (s'il y en a plus d'un: choisissez-en un)
  • Vérifiez si ce bord provoquerait un cercle, si c'est le cas, marquez-le comme choisi et le jetez.
  • S'il ne provoque pas de cercle, utilisez-le et marquez-le comme utilisé / choisi.

C'est tout. C'est vraiment aussi simple. Cependant, je voudrais mentionner une chose à ce stade, je pense que cela s'adapte le mieux ici: il n'y a pas "l'arbre couvrant minimum" en général, mais "un arbre couvrant minimum" car il peut y en avoir beaucoup, donc vos résultats peuvent varier!

Retour à votre structure de données! Vous pouvez maintenant voir pourquoi ce serait une mauvaise idée d'utiliser un tableau de chaînes comme structure de données. Vous répéteriez de nombreuses opérations sur les chaînes (par exemple en vérifiant le poids de chaque bord) et Les cordes sont immuables, cela signifie que vous ne pouvez pas simplement «jeter» l'un des bords ou marquer l'un des bords de quelque manière que ce soit. En utilisant une approche différente, vous pouvez simplement régler le poids sur -1, ou même supprimer l'entrée pour le bord!

Recherche en profondeur d'abord

D'après ce que j'ai vu, je pense que votre principal problème est de décider si un bord provoquerait un cercle ou non, non? Pour en décider, vous devrez probablement appeler un algorithme de recherche en profondeur d'abord et utiliser sa valeur de retour. L'idée de base est la suivante: commencez à partir de l'un des nœuds (j'appellerai ce nœud la racine) et essayez de trouver un moyen vers le nœud à l'autre extrémité du bord choisi (j'appellerai ce nœud le nœud cible). (Bien sûr dans le graphique qui n'a pas encore cet avantage)

  • Choisissez un incident de bord non visité à votre racine
  • Marquez ce bord choisi comme visité (ou quelque chose comme ça, quoi que vous vouliez)
  • Répétez les deux dernières étapes pour le nœud de l'autre côté du bord visité
  • Chaque fois qu'il n'y a pas de bords non visitées, revenez en arrière
  • Si vous êtes de retour à votre racine et que vous n'avez aucun bord non visité, ce qui vous reste, vous avez terminé. retourne false.
  • Si vous, à tout moment, visitez votre nœud cible, vous avez terminé. Retour Vrai.

Maintenant, si cette méthode revient true Ce bord provoquerait un cercle.

Autres conseils

Ce n'est pas une réponse directe à votre question par Say (on dirait que vous faites des travaux scolaires), mais je pense que cela vous aidera à démarrer. Pourquoi ne pas créer une structure de données qui correspond plus étroitement à votre modèle mental et s'accumuler à partir de là?

class GraphNode { 

    final String name;
    final List<GraphEdge> adjacentNodes;

    public GraphNode(String name) { 
        this.name = name;
        adjacentNodes = new ArrayList<GraphEdge>();
    }

    public void addAdjacency(GraphNode node, int weight) { 
        adjacentNodes.add(new GraphEdge(node, weight));
    }

}

class GraphEdge {

    final GraphNode node;
    final int weight;

    public GraphEdge(GraphEdge node, int weight) {
        this.node = node;
        this.weight = weight;
    }

}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top