c# - creating - graphs bfs
Invertir amplitud primera travesÃa en C# (2)
¿Alguien tiene una implementación lista del algoritmo transversal de Reverse Breadth First en C #?
Por amplitud inversa, primer recorrido, me refiero a que, en lugar de buscar en un árbol a partir de un nodo común, quiero buscar el árbol desde la parte inferior y converger gradualmente a un nodo común.
Veamos la figura de abajo, esta es la salida de un recorrido de Breadth First:
En mi primer recorrido a la inversa, 9 , 10 , 11 y 12 serán los primeros nodos encontrados (el orden de los mismos no es importante, ya que todos son de primer orden). 5 , 6 , 7 y 8 son los segundos nodos encontrados, y así sucesivamente. 1 sería el último nodo encontrado.
¿Alguna idea o punteros?
Edición: Cambie "Búsqueda en la amplitud de la amplitud" a "Travesía de la primera amplitud de la amplitud" para aclarar la pregunta
Ejecute un BFS normal desde rootNode y deje depth[i] = linked list of nodes with depth i . Así que para tu ejemplo tendrás:
depth[1] = {1}, depth[2] = {2, 3, 4} etc. Puedes construir esto con una simple búsqueda en BFS. Luego imprima todos los nodos en depth[maxDepth] , luego aquellos en depth[maxDepth - 1] etc.
La profundidad de un nodo i es igual a la profundidad de su nodo padre + 1. La profundidad del nodo raíz se puede considerar 1 o 0.
Utilice una combinación de una pila y la cola.
Haga el BFS ''normal'' usando la cola (que supongo que ya sabe que debe hacer), y siga presionando los nodos en la pila a medida que los encuentre.
Una vez hecho esto con el BFS, la pila contendrá el orden BFS inverso.