9
votes

Pourquoi les algorithmes Kruskal et Prim Mst ont-ils des travaux différents pour des graphiques rares et denses?

J'essaie de comprendre pourquoi Prim et Kruskal ont des complexités de temps différentes lorsqu'il s'agit de graphiques rares et denses. Après avoir utilisé quelques applets qui démontrent comment chaque fonctionne, je suis toujours laissé un peu confus sur la manière dont la densité du graphique affecte les algorithmes. J'espère que quelqu'un pourrait me donner un coup de pouce dans la bonne direction.


4 commentaires

Avez-vous des exemples de complexités de temps différents? Tout ce que je peux trouver, ce sont des limites supérieures qui travaillent dans les deux cas ...


dense: prim = o (n2), kruskal = o (n2 * log (n)) clairsemé: prim = o (n2), kruskal = o (n log (n))


Sauf si je me souviens de ce faux, avec les bonnes structures de données, vous ne devriez avoir aucun mandat de N ^ 2. Peu importe, la réponse à l'OP est d'aller trouver une copie de Cormen, qui a une analyse d'exécution et une comparaison des deux.


Cela dépend de ce que n est, il semble probablement être ~ = nombre de sommets dans ce cas


3 Réponses :


1
votes

sont ces différentes complexités par rapport au nombre de sommets par hasard?

Il y a souvent, un argument légèrement handicapé, qui dit pour un graphe clairsemé, le nombre d'arêtes E = O (v) où V est le nombre de verticyes, pour un graphique dense E = O (v ^ 2). Comme les deux algotrithmes ont potentiellement une complexité qui dépend de E, lorsque vous convertissez cela en combinexité qui dépend de V, vous obtenez différentes complexités en fonction des graphiques denses ou clairsemés

EDIT:

Différentes structures de données affectera également la complexité du cours Wikipedia a une pause sur Ceci


4 commentaires

Je ne pense pas que cet argument soit handicapé. Il semble simple de le formaliser. Choisissez n'importe quel k et appelez des graphiques d'appel où e ≤ k v "cessé". Maintenant, vous avez grandement limité le domaine problématique, asymptotiquement quand même: peu importe ce que K vous choisissez, car v devient grand, une infime fraction de graphiques sera clairsemée. Un algorithme qui est O (E Log V) sera O (V log V) sur des graphiques clairsemés.


Son onduleuse à la main, car je ne crois pas qu'il existe une définition stricte de ce qui est clairsemé, et je l'ai vu décrit comme e = v ^ k pour K quelque part entre 1 et 2.


Mais oui, je pense que c'est généralement accepté qu'avec E = v ^ k Sparse signifie que k ~ = 1 et dense va signifier k ~ = 2


Oh je vois. Mais c'est juste une chose de terminologie, à savoir le mot «clairsemé» n'a aucun sens standard précis. L'argument est irréprochable.



4
votes

Wikipedia donne la complexité de ces algorithmes en termes de e , le nombre d'arêtes et v , le nombre de sommets, qui est une bonne pratique car il laisse Vous faites exactement ce genre d'analyse.

L'algorithme de Kruskal est O ( e log v ). La complexité de PRIM dépend de la structure de données que vous utilisez pour cela. Utilisation d'une matrice d'adjacence, c'est O ( v 2 ).

Maintenant si vous branchez v 2 pour e , voici que vous obtenez les complexités que vous avez citées dans votre commentaire pour des graphiques denses et Si vous branchez v pour e , lo vous obtenez les rares.

Pourquoi branchez-nous v 2 pour un graphique dense? Eh bien, même dans le graphique éventuel dense possible, vous ne pouvez pas avoir autant que v 2 bords, donc clairement e = o ( v 2 ).

Pourquoi branchez-nous v pour un graphique précis? Eh bien, vous devez définir ce que vous entendez par cépage, mais supposons que nous appelons un graphique clairsemé si chaque sommet n'a pas plus de cinq bords. Je dirais que de tels graphiques sont assez clairsemés: une fois que vous vous levez dans les milliers de sommets, la matrice d'adjacence serait surtout d'espace vide. Cela signifierait que pour des graphiques rats, e ≤ 5 v , donc e = o ( v ). < / p>


0 commentaires

0
votes

Les algorithmes de Cormen et al font effectivement une analyse, dans les deux cas en utilisant une représentation clairsemée du graphique. Avec l'algorithme de Kruskal (des sommets de liaison dans les composants disjoints jusqu'à ce que tout rejoint) La première étape consiste à trier les bords du graphique, qui prend du temps O (E LG E) et il établit simplement que rien d'autre ne prend plus de temps que cela. Avec l'algorithme de prim (étendre l'arborescence actuelle en ajoutant le sommet le plus proche, pas déjà dessus), ils utilisent un tas de fibonacci pour stocker la file d'attente des sommets en attente et obtenir O (E + V LGV), car avec un arbre Fibonacci diminue la distance à des sommets. dans la file d'attente n'est que O (1) et vous le faites au plus une fois par bord.


0 commentaires