Comment indiquer le précommande d'un Spanning Tree à l'aide de l'algorithme BFS

Question

Je fais une implémentation de l'algorithme BFS en c ++ pour trouver un spanning tree, la sortie d'un spanning tree devrait être affichée en précommande, mais j'ai un doute sur l'implémentation, comment je peux construire un arbre sinonsavoir exactement combien d'enfants ont chaque nœud ?.Considérer une structure arborescente récursive La structure des données de l'arbre peut s'écrire:

typedef struct node 
{
        int val;
        struct node *left, *right;
}*tree; //tree has been typedefed as a node pointer.

Mais ne pensez pas que cette implémentation fonctionne comme mentionné précédemment.

Voici ma fonction pour retourner l'arbre en précommande:

void preorder(tree t) 
{
        if(t == NULL)
                return;
        printf("%d ", t->val);
        preorder(t->left);
        preorder(t->right);
}

Je me demande également s'il existe un moyen de faire le précommande des nœuds sans utiliser une structure arborescente.

Answer 1

J'ai vu deux questions concrètes dans la publication:

1. Est-il possible d'avoir une structure de données utilisant plus de deux enfants dans un arbre? Bien sûr, cela est possible. Fait intéressant, c'est même possible avec la structure de nœuds que vous avez publiée! Considérez simplement le pointeur left comme un pointeur vers le premier enfant et le pointeur right pour pointer vers le frère suivant. Étant donné que la première recherche en largeur d'un graphe crée implicitement un arbre couvrant, vous pouvez alors parcourir cet arbre en précommande si vous le représentez réellement d'une manière ou d'une autre.
2. Pouvez-vous faire une promenade en précommande sans utiliser une arborescence? Oui, c'est possible aussi. Essentiellement, DFS et BFS ne sont pas différents du point de vue conceptuel pour cela: vous avez juste une structure de données qui maintient les nœuds à visiter ensuite. Pour DFS, il s'agit d'une pile, pour BFS, il s'agit d'une file d'attente. Vous obtenez un parcours de précommande de l'arborescence (c'est-à-dire que vous visitez tous les enfants d'un nœud après le parent) si vous émettez le numéro de nœud lorsque vous l'insérez dans la structure de données en conservant les nœuds à visiter.

Pour développer un peu le deuxième point: une promenade de précommande d'un arbre signifie simplement que chaque nœud est traité avant ses nœuds enfants. Lorsque vous effectuez une recherche de graphique que vous souhaitez parcourir à travers un composant connecté d'un graphique, en visitant chaque nœud une seule fois, vous créez effectivement un arbre implicite. Autrement dit, votre nœud de départ devient le nœud racine de l'arborescence. Chaque fois que vous visitez un nœud, vous recherchez des nœuds adjacents qui n'ont pas été visités, c'est-à-dire qui ne sont pas marqués. S'il existe un tel nœud, l'arête incidente devient un nœud d'arbre et vous marquez le nœud. Puisqu'il n'y a toujours qu'un seul nœud actif, vous devez vous souvenir des nœuds qui ne sont pas encore traités dans une structure de données, par exemple une pile ou une file d'attente (au lieu d'utiliser une pile explicitement, vous pouvez faire une récursivité qui crée la pile implicitement). Maintenant, si vous émettez le numéro de nœud la première fois que vous voyez un nœud, vous le traitez clairement avant ses enfants, c'est-à-dire que vous finissez par écrire le numéro de nœud dans l'ordre d'une marche de précommande.

Si vous ne comprenez pas cela, veuillez sortir une feuille de papier et dessiner un graphique et une file d'attente:

• les nœuds avec des cercles creux et leur numéro de nœud à côté d'eux
• les bords avec des lignes fines
• la file d'attente n'est que des rectangles qui ne contiennent rien au début

Choisissez maintenant un nœud pour devenir le nœud de départ de votre recherche qui est le même que le nœud racine de votre arbre. Écrivez son numéro dans la première position vide de la file d'attente et cochez, c'est-à-dire remplissez le nœud. Maintenant, poursuivez la recherche:

• regardez le nœud indiqué par l'avant de la file d'attente et trouvez un nœud adjacent qui n'est pas rempli:
  • ajoutez le nœud à l'arrière de la file d'attente (c'est-à-dire juste derrière le dernier nœud du rectangle)
  • marquer (c'est-à-dire remplir) le nœud
  • épaississez la ligne reliant les deux nœuds: c'est une arête d'arbre maintenant
• s'il n'y a plus de nœuds adjacents non marqués, cochez le nœud avant dans la file d'attente (c'est-à-dire supprimez-le de la file d'attente) et passez au nœud suivant jusqu'à ce qu'il n'y ait plus de nœuds

Le rectangle de la file d'attente contient maintenant un parcours de précommande de l'arbre couvrant impliqué par une première recherche en largeur du graphe. L'arbre couvrant est visible à l'aide des lignes plus épaisses. L'algorithme fonctionnerait également si vous traitiez le rectangle de la file d'attente comme une pile, mais ce serait un peu plus compliqué car vous vous retrouverez avec des nœuds cochés entre les nœuds encore à traiter: au lieu de regarder le premier nœud décoché, vous regarderiez le dernier nœud décoché.

En travaillant avec des algorithmes graphiques, j'ai trouvé très utile de visualiser l'algorithme. Bien qu'il serait bien que l'ordinateur maintienne le dessin, l'alternative low-tech consistant à dessiner des objets sur papier et éventuellement à indiquer les nœuds actifs par un certain nombre de crayons étiquetés fonctionne aussi bien sinon mieux.

Juste

un commentaire sur le code: chaque fois que vous lisez une entrée, assurez-vous que vous avez bien lu les données.BTW, votre code est clairement uniquement C et non C ++: les tableaux de longueur variable ne sont pas disponibles en C ++.En C ++, vous utiliseriez std::vector<int> followOrder(vertexNumber) au lieu de int followOrder[vertexNumber].Fait intéressant, le code n'est pas non plus C car il utilise par exemplestd::queue<int>.