Cómo indicar el pedido anticipado de un árbol de expansión utilizando el algoritmo BFS

Question

Estoy haciendo una implementación del algoritmo BFS en C ++ para encontrar un árbol de expansión, la salida para un árbol de expansión debe mostrarse en un pedido por pedido, pero tengo dudas en la implementación, cómo puedo construir un árbol si no saber exactamente cómo muchos niños tienen cada nodo? Teniendo en cuenta una estructura de árbol recursiva, la estructura de datos del árbol se puede escribir como:

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

Pero no piense que funciona esta implementación como se mencionó anteriormente.

Esta es mi función para devolver el árbol en preorden:

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

También me pregunto si hay alguna forma de hacer el pedido de los nodos sin usar una estructura de árbol.

Answer 1

He visto dos preguntas concretas en la publicación:

1. ¿Es posible tener una estructura de datos que use más de dos niños en un árbol? Por supuesto que esto es posible. Curiosamente, ¡incluso es posible con la estructura del nodo que publicó! Solo considere el left puntero para ser un puntero para el primer niño y el right Puntero para señalar al siguiente hermano. Dado que la amplitud primero la búsqueda de un gráfico desarrolla implícitamente un árbol de expansión, puede caminar este árbol en un pedido por pedido si realmente lo representa de alguna manera.
2. ¿Puedes hacer una caminata por reservas sin usar una estructura de árbol? Sí, esto también es posible. Esencialmente, DFS y BFS no son conceptualmente diferentes para esto: solo tiene una estructura de datos que mantiene los nodos que se visitarán a continuación. Para DFS, esta es una pila, para BFS es una cola. Obtiene una caminata de pedido por pedido del árbol (es decir, visite a todos los niños de un nodo después del padre) si emite el número de nodo cuando lo inserta en la estructura de datos que mantiene los nodos que se visitarán.

Para expandirse un poco en el segundo punto: un Permitole el paseo de un árbol Solo significa que cada nodo se procesa antes de los nodos infantiles. Cuando realiza una búsqueda de gráficos, desea atravesar un componente conectado de un gráfico, visitando cada nodo solo una vez, crea efectivamente un árbol implícito. Es decir, su nodo de inicio se convierte en el nodo raíz del árbol. Cada vez que visita un nodo, busca nodos adyacentes que no se hayan visitado, es decir, que no está marcado. Si hay tal nodo, el borde incidente se convierte en un nodo de árbol y marca el nodo. Dado que siempre solo hay un nodo que se sostiene activamente, debe recordar los nodos que no están procesados, sin embargo, en alguna estructura de datos, por ejemplo, una pila o una cola (en lugar de usar una pila explícitamente, podría hacer una recursión que crea el pila implícitamente). Ahora, si emite el número de nodo la primera vez que ve un nodo que lo procesa claramente antes de sus hijos, es decir, termina escribiendo el número de nodo el orden de una caminata por pedido.

Si no entiende esto, saque una hoja de papel y dibuje un gráfico y una cola:

• los nodos con círculos huecos y su número de nodo al lado de ellos
• los bordes con líneas delgadas
• La cola es solo rectángulos que no contienen nada al principio

Ahora elija un nodo para convertirse en el nodo de inicio de su búsqueda, que es el mismo que el nodo raíz de su árbol. Escriba su número en la primera posición vacía en la cola y marque, es decir, llene el nodo. Ahora continúe con la búsqueda:

• Mire el nodo indicado por el frente de la cola y encuentre un nodo adyacente que no esté lleno:
  • Agregue el nodo en la parte posterior de la cola (es decir, justo detrás del último nodo del rectángulo)
  • Mark (es decir, llene) el nodo
  • Haga que la línea conecta los dos nodos más gruesos: es un borde de árbol ahora
• Si no hay más nodos adyacentes sin marcar, marcen el nodo delantero en la cola apagado (es decir, quítelo de la cola) y pasen al siguiente nodo hasta que no haya nodos adicionales

Ahora el rectángulo de la cola contiene una caminata por adelantado del árbol de expansión implícito en una primera búsqueda en la primera búsqueda del gráfico. El árbol de expansión es visible usando las líneas más gruesas. El algoritmo también funcionaría si tratara el rectángulo para la cola como una pila, pero sería un poco más desordenado porque termina con nodos marcados entre los nodos que aún no se procesan: en lugar de mirar el primer nodo desatado que verá el último nodo desatado.

Cuando trabajaba con algoritmos gráficos, me pareció bastante útil visualizar el algoritmo. Aunque sería bueno que la computadora mantenga el dibujo, la alternativa de baja tecnología de dibujar cosas en papel y posiblemente indicar nodos activos por varios lápices etiquetados funciona tan bien, si no mejor.

Solo un comentario sobre el código: siempre que esté leyendo cualquier entrada, asegúrese de leer con éxito los datos. Por cierto, su código es claramente solo el código C y no C ++: las matrices de longitud variable no están disponibles en C ++. En C ++ usarías std::vector<int> followOrder(vertexNumber) en vez de int followOrder[vertexNumber]. Curiosamente, el código no es C tampoco porque usa EG std::queue<int>.