Pourquoi les algorithmes de Prim ou de Kruskal ne peuvent-ils pas être utilisés sur un graphe orienté?

Prim et Kruskal les algorithmes sont utilisés pour trouver le minimum spanning tree d'un graphe qui est connecté et non orienté. Pourquoi ne peuvent-ils pas être utilisés sur un graphique qui est dirigé?

source d'informationauteur user1472747

  1. 25

    C'est un petit miracle que ces algorithmes de travail, en premier lieu, que la plupart des algorithmes cupides simplement écraser et de les graver sur certains cas. En supposant que vous souhaitez utiliser afin de trouver un minimum spanning arborescence (dirigé les chemins d'un sommet à tous les autres), puis une problématique graphique pour Kruskal ressemble à ceci.

     5
  --> a
 /  /^
s   1| |2
 \   v /
  --> b
 3

    Nous allons prendre l'a->b arc de coûts 1, puis coincé parce que nous voulions vraiment s->b, d'un coût de 3 et b->un coût de 2.

    Pour Prim, ce graphique est problématique.

     5
  --> a
 /  /
s   1|
 \   v
  --> b
 3

    Nous allons prendre le s->b, d'un coût de 3, mais nous avons vraiment voulu s->un coût de 5 et a->b prix 1.

  2. 4

    Prim et de Kruskal algorithme de sortie minimum spanning tree pour les connectés et "non-directifs" graphique. Si il n'est pas connecté, nous pouvons les adapter à la sortie de minimum couvrant les forêts.

    Dans l'algorithme de Prim, nous divisons le graphique en deux ensembles de sommets. Un jeu de la exploré les sommets qui ont déjà formé des MST (Set1) et un autre ensemble de sommets inexplorés qui finira par rejoindre le premier set complet "couvrant"(Set2). À chaque instant, nous sélectionnons un minimum pondéré bord de la coupe de joindre les deux ensembles disjoints. Si il n'est pas dirigé bord de nœuds explorés de MST au reste inexploré, l'algorithme se coince, même si il y a des arêtes de inexplorées nœuds à explorer les nœuds MST.

    Dans l'algorithme de Kruskal, l'idée est de trier les arêtes par ordre croissant de leur poids et de les ramasser dans l'ordre et les inclure dans MST exploré les nœuds/bords si ils ne forment déjà un cycle avec exploré les nœuds. Ceci est fait par l'Union-Find DS. Mais la détection de cycle pour les graphes orientés échoue avec cette méthode. Ex: Graphe contenant les arêtes [1->2] [2->3] [1->3] sera signalé pour contenir un cycle avec l'Union, la méthode Find.

    Donc Prim échoue parce qu'il suppose, chaque nœud est accessible à partir de chaque nœud, qui, bien que valable pour les non-orienté graphiques peuvent ne pas être vrai pour les bigrammes. Kruskal échoue en raison de l'incapacité à détecter les cycles et parfois, il est indispensable d'ajouter les bords des cycles de prise de satisfaire "minimum" pondéré propriété de MST.

    Aussi, en cas de bigrammes, MST n'a pas le sens complet. Son équivalent pour les bigrammes est "minimum spanning arborescence", qui permettra de produire un arbre où chaque sommet peut être atteint à partir d'un seul sommet.