Veuillez suggérer un algorithme de trouver le noeud dans un arbre dont la distance à son nœud le plus éloigné est minimum de tous les nœuds.
c'est pas un graphique et il n'est pas pesé.
5 Réponses :
Vous pouvez utiliser l'algorithme de dijkstra ( http://fr.wikipedia.org/wiki/dijkstra % 27S_ALGORITHM ) sur chaque nœud à son tour, pour trouver toutes les distances de ce nœud à tous les autres nœuds; Scannez la liste résultante pour obtenir la distance au nœud le plus éloigné. Une fois que vous avez Dijkstra'd chaque nœud, une autre numérisation vous donnera le minimum de ces distances maximales.
dijkstra est généralement considéré comme ayant une exécution o (v ^ 2) , où v est le nombre de nœuds; Vous l'exécuteriez une fois par nœud, qui augmentera le temps nécessaire à O (v ^ 3) dans une implémentation naïve. Vous pourrez peut-être gagner des gains en stockant les résultats des exécutions Dijkstra antérieur des nœuds et les utilisant comme des valeurs connues dans les prochaines exécutions.
Floyd-Warshalllors est beaucoup plus simple à coder que celui de Dijkstra, mais oui, il a la même complexité.
Vous pouvez utiliser Algorithme de Johnson pour des graphiques rats, mais utilisez sinon le Algorithme Floyd-Warshall simplement parce qu'il est trivial à mettre en œuvre.
Essentiellement, vous souhaitez trouver la distance de chaque noeud sur tous les autres nœuds, puis il vous suffit de rechercher de manière triviale la propriété que vous souhaitez.
Ces algorithmes sont nouveaux pour moi et apparaissent effectivement similaires au code que Dijkstra.
Notez que FW est O (n ^ 3) qui peut ne pas être idéal.
Identique à la répétition de Dijkstra, pour cette application.
Retirer les feuilles. Si plus de 2 nœuds sont laissées, répétez. Le nœud (ou 2 nœuds) laissé sera le nœud que vous recherchez.
pourquoi cela fonctionne:
Le ou les nœuds sont au milieu du chemin le plus long p dans l'arborescence. Leur distance maximale à tout nœud est au plus de la moitié de la longueur du chemin (sinon, ce ne serait pas le plus long). Tout autre nœud sur p aura évidemment une plus grande distance à la fin de la fin de p que le (s) noeud trouvé (s). Tout nœud n non sur p aura son nœud le plus éloigné (distance entre n sur le nœud le plus proche sur p , disons c ) + (distance entre C à l'autre extrémité de p ), de nouveau plus que le (s) noeud (s) trouvé (s) l'algorithme.
Je ne sais pas quel est le nœud racine, donc aucune idée de ce qui est le nœud de la feuille.
Un nœud de feuille aura exactement un bord.
Cela trouvera toujours le nœud racine (asumant qu'il a plus de 1 bord, sinon il trouvera la branche la plus basse au-dessus de la racine)
@JK: Si je comprends bien, les bords sont indemnisés, il n'y a donc pas de "racine". Cela trouve toujours le milieu du chemin le plus long du graphique. Un nœud qui n'a que 1 bord est une feuille, il sera donc éliminé dans la première itération.
Choisissez un nœud arbitraire v dans l'arborescence t .
Exécutez BFS Fabrication v comme la racine de t .
BFS sortira les distances de v à tous les autres nœuds de t .
Choisissez maintenant un nœud u qui est le plus éloigné de v .
Courir à nouveau BFS Fabrication u comme racine.
Sur la nouvelle sortie de distance, recherchez un nœud w qui est le plus éloigné de u .
Considérez le chemin entre u et w .
C'est le chemin le plus long dans l'arborescence t .
Le nœud dans le mityle du chemin est Notez qu'il peut exister deux centres dans un arbre. Si c'est le cas, ce sont des voisins.
performance: o (n) , où n est le nombre de nœuds de t . .
Si nous le prouvons, l'algorithme est correct, car il trouve d'abord u , et, puisqu'il s'agit d'une extrémité du chemin le plus long, utilise des DFS pour trouver ce chemin lui-même.
Preuve de la revendication a) u --- r et v - k avez un nœud commun o . Ensuite, v - o - u et v - o - r sont plus courts que u-o --- k . Ensuite, o --- r est plus court que o - k . Ensuite, u ------ r n'est pas le chemin le plus long sous forme de graphique, car u ---- k est plus long. Il contredit notre hypothèse.
b) u --- r et v - k ne pas avoir de nœuds communs. Mais puisque le graphique est connecté, il y a des nœuds o1 et o2 sur chacun de ces chemins, de sorte que le chemin entre eux o1 - O2 ne contient pas d'autres nœuds sur ces deux chemins. La contradiction avec l'hypothèse est la même que dans le point A), mais avec o1 - O2 au lieu de o (en fait, point un > est juste un cas particulier de b , où o1 = o2 ).
Cela prouve la réclamation et donc l'exactitude de l'algorithme.
(Ceci est la preuve écrite par Pavel Shved , et l'auteur original pourrait avoir une plus courte). < / p> Preuve
Pourriez-vous divulguer un raisonnement pour votre méthode de recherche du chemin le plus long?
Comme d'autres ont dit dans les commentaires: Un arbre est un graphique - un graphique acyclique connecté non dirigé à être exact - voir "Arbre" ( Théorie graphique) .
Un arbre ne peut pas être non dirigé, peut-il?
Un arbre a une direction implicite. Chaque nœud a une distance bien définie sur le nœud racine (arbre non forêt) et deux nœuds connectés ont des distances à la racine qui diffèrent d'une. Le nœud avec la plus petite distance du nœud racine est le parent; Le nœud avec la plus grande distance est l'enfant. Cette relation parent-enfant dans des graphiques en forme d'arbre est ainsi définie dans des termes pure graphique. En outre, les arbres sont des graphiques acycliques, il n'ya donc aucun autre bord entre les parents et leurs enfants. Par conséquent, la relation parent-enfant des nœuds connectés agit comme une direction du bord.
Vous devez reformuler votre question.
Il n'a pas de sens. Il cherche essentiellement le sommet le plus "central" dans un graphique (le nœud dont le nœud le plus distant est minum de tous les nœuds).
Concernant le "Ce n'est pas un graphique": un arbre est un cas particulier de graphique, de sorte que les algorithmes de graphique devraient fonctionner pour votre arbre, même si cela n'est pas maximalement efficace.
Juste un arbre générique ou un arbre binaire ou un autre arbre d'autre?
Vous devez revisiter votre compréhension du terme «graphique». Un arbre est un graphique.
Le problème avec les arbres (même non pondérés) est qu'il n'ya pas de distance bien définie définie entre frères et sœurs. Transformez-le en un graphe tout aussi connecté, cependant, et la distance est certainement 2.