Algoritmo de etiquetado de tiempo lineal para un árbol?

Tengo un árbol no dirigido cuyos vértices quiero etiquetar. Los nodos de la hoja deben etiquetarse como uno. Luego, suponga que las hojas fueron removidas. En el árbol que queda, las hojas deben etiquetarse como dos. Este proceso continúa de la manera obvia hasta que todos los vértices tengan una etiqueta. La razón por la que hago esto es porque quiero almacenar los vértices en una cola y pasar por ellos "las hojas primero". ¿Hay una manera fácil de hacer este tiempo $O(n+m)$ ?

Puedo resolver el problema haciendo un BFS en cada paso. Pero en el peor de los casos, en cada paso que paso por cada vértice, elimino exactamente dos hojas y las pongo en cola. Creo que esto lleva tiempo cuadrático.

Otra idea era encontrar primero todas las hojas y luego hacer un BFS de cada hoja. Esto no me da la solución deseada. Por ejemplo, considere un tipo de "gráfico de corona" como en la figura a continuación. Se muestra la solución deseada, pero el lanzamiento de un BFS desde cada hoja daría como resultado solo dos etiquetas utilizadas.

Idealmente, el algoritmo de tiempo lineal también sería fácil de explicar e implementar.

Árboles sin raíces

$O(E+V\log V)$

• Ponga todos los vértices en una cola de prioridad, siendo su prioridad su grado.
• Mientras la cola no está vacía:
  • $v$$1$$0$
  • $\sigma(v) = 1 + \max \sigma(u)$$u$$v$
  • Reste de la prioridad del vecino único restante de (si lo hay).$1$$u$

De hecho, realmente no necesitamos una cola prioritaria, y este algoritmo puede implementarse usando una cola simple en el tiempo :$O(E+V)$

• Inicialice una matriz de longitud con los grados de todos los vértices.$V$
• Inicialice otra matriz de longitud con "vivo".$V$
• Ir una vez a través de la primera matriz y empujar todos los vértices de grado a una cola.$1$
• Mientras la cola no está vacía:
  • Pop un vértice .$v$
  • Let , donde va sobre todos los vecinos originales de .$\sigma(v) = 1 + \max \sigma(u)$$u$$v$
  • Marque como "muerto".$v$
  • Si tiene algún vecino "vivo" , reste del grado de .$v$$u$$1$$u$
  • Si el nuevo grado de es , empujar a la cola.$u$$1$$u$

Árboles enraizados

Use DFS en su lugar. Aquí hay un boceto del algoritmo.

• Dado un nodo , si es una hoja, establezca .$v$$v$$d(v) = 1$
• Si no es una hoja, ejecute el algoritmo en todos sus elementos secundarios y luego deje que , donde va sobre el conjunto de todos los elementos secundarios.$v$$d(v) = 1 + \max d(u)$$u$

Ejecutas este algoritmo en la raíz.

Una respuesta directa es la siguiente:

• Convierta esto en un gráfico dirigido, donde tengamos una arista desde cada nodo hasta su padre . Tenga en cuenta que obtiene un dag (gráfico acíclico dirigido).$(u,v)$$u$$v$

• Topológicamente ordenar el gráfico.

• Escanee los vértices, en orden ordenado. Etiquete cada vértice con una más que la mayor de las etiquetas en sus predecesores. Como estamos escaneando en orden topológico, todos los predecesores de ya habrán recibido una etiqueta antes de intentar etiquetar .$v$$v$

Cada uno de estos pasos se puede realizar en tiempo , por lo que el tiempo total de ejecución es . Menciono este enfoque alternativo solo en caso de que te resulte conceptualmente más fácil de entender que la respuesta de Yuval.$O(n+m)$$O(n+m)$