Traverser une structure arborescente générale à partir d'un nœud arbitraire en C#

Question

J'ai besoin d'algorithmes de traversée d'arbres pour des arbres arbitraires dans l'ordre de la traversée en profondeur d'abord et en largeur d'abord. La partie délicate est que je dois pouvoir commencer à partir d'un nœud arbitraire et continuer jusqu'à ce qu'un autre nœud spécifique soit parcouru.

Je peux utiliser n'importe quel algorithme ordinaire et ignorer les nœuds traversés jusqu'au nœud de départ et continuer jusqu'au nœud final (ce que je fais actuellement), mais c'est laid et inefficace.

Des suggestions, s'il vous plaît.

MISE À JOUR : Chacun de mes nœuds est associé à un identifiant. Dans certains cas, j'ai des références de nœuds de départ et d'arrivée pour commencer. Dans d'autres cas, on me donne deux identifiants, je vérifie si le noeud donné est le noeud de départ ou le noeud d'arrivée en inspectant leurs identifiants. J'utilise un parcours en profondeur pour trouver le nœud de départ. Les nœuds de départ et d'arrivée peuvent se trouver n'importe où dans la hiérarchie. J'espère que quelqu'un pourra trouver une idée pour le cas où l'on me donne déjà des références au nœud de départ et au nœud final. BTW, les nœuds de l'arbre sont en fait triés selon un ordre de tri qui commence à 0 pour chacun des sous-nœuds d'un nœud et il y a un nœud racine.

Answer 1

Je pense que ce que vous faites est la manière la plus efficace de procéder. Surtout si vous travaillez avec des arbres arbitraires.

On vous donne un arbre arbitraire et vous devez trouver le nœud à partir duquel commencer la traversée. Comme il n'y a pas de hiérarchie (c'est-à-dire qu'il ne s'agit pas d'un arbre binaire), vous devrez parcourir les nœuds (vous pourriez finir par parcourir plus de la moitié des nœuds si le nœud donné est un nœud feuille ou si le nœud n'est pas dans l'arbre, vous devrez parcourir tout l'arbre) jusqu'à ce que vous trouviez le nœud par lequel commencer. Une fois que vous avez trouvé le nœud, vous pouvez commencer votre DF Traversal ou BF Traversal.

Je ne vois aucune optimisation possible.

Answer 2

Plutôt que de

Traverse(RootNode, StartNode, EndNode)

Passer le nœud de départ comme racine

Traverse(StartNode, EndNode)

Cependant, si vous souhaitez renvoyer des nœuds qui ne sont pas des enfants de votre nœud de départ, vous devrez continuer à utiliser votre méthode actuelle.

Answer 3

Si vous devez répondre à un grand nombre de requêtes sans rapport entre elles et que vous devez fournir un chemin d'accès (au lieu de simplement dire qu'il existe ou non), vous ne pouvez pas faire mieux que ce que vous avez maintenant AFAIK.

En revanche, si vous vous attendez à un grand nombre de requêtes impliquant un petit nombre de nœuds spécifiques (par exemple, quels sont les chemins de A à B, C, D, E, F et G ?), vous pouvez d'abord calculer le arbre à portée minimale de ce(s) nœud(s) et rendre votre BFS plus efficace.