Búsqueda lexicográfica en amplitud

En informática , la búsqueda en anchura lexicográfica o Lex-BFS es un algoritmo de tiempo lineal para ordenar los vértices de un grafo . Este algoritmo difiere de la búsqueda en anchura , pero produce un ordenamiento consistente con ella.

El algoritmo de búsqueda en amplitud lexicográfica se basa en la idea del refinamiento de particiones y fue desarrollado inicialmente por Donald J. Rose, Robert E. Tarjan y George S. Lueker ( 1976 ) . Corneil (2004) presenta un análisis más detallado del tema . Se ha utilizado como subrutina en otros algoritmos de grafos, incluyendo el reconocimiento de grafos cordales y la coloración óptima de grafos hereditarios de distancia . 

El algoritmo de búsqueda en anchura se define comúnmente mediante el siguiente proceso:

• Inicializa una cola de vértices del grafo, con el vértice inicial del grafo como único elemento de la cola.
• Mientras la cola no esté vacía, elimine (desencola) un vértice v de la cola y agregue a la cola (encola) todos los demás vértices a los que se puede llegar mediante una arista desde v que no se hayan agregado en pasos anteriores.

Sin embargo, en lugar de definir el vértice a elegir en cada paso de forma imperativa , como el que produce la operación de extracción de una cola, se puede definir la misma secuencia de vértices de forma declarativa mediante las propiedades de estos vértices. Es decir, una búsqueda en anchura estándar es simplemente el resultado de aplicar repetidamente esta regla:

• Generar repetidamente un vértice v , eligiendo en cada paso un vértice v que no haya sido elegido previamente y que tenga un predecesor (un vértice que tenga una arista hacia v ) lo antes posible en la salida.

En algunos casos, este ordenamiento de vértices según las posiciones de salida de sus predecesores puede presentar empates: dos vértices diferentes tienen el mismo predecesor más antiguo. En este caso, el orden en que se eligen esos dos vértices puede ser arbitrario. El resultado de la búsqueda en anchura lexicográfica difiere de una búsqueda en anchura estándar al tener una regla consistente para resolver dichos empates. En la búsqueda en anchura lexicográfica, el orden de salida es el que produciría la siguiente regla:

• Generar repetidamente un vértice v , eligiendo en cada paso un vértice v que no haya sido elegido previamente y cuyo conjunto completo de predecesores ya generados sea lo más pequeño posible en orden lexicográfico .

Así, cuando dos vértices v y w tienen el mismo predecesor más antiguo, anterior a cualquier otro vértice no seleccionado, el algoritmo estándar de búsqueda en anchura los ordenará arbitrariamente. En cambio, en este caso, el algoritmo LexBFS elegiría entre v y w según el orden de salida de sus segundos predecesores más antiguos. Si solo uno de ellos tiene un segundo predecesor más antiguo que ya se ha mostrado, se elige ese. Si tanto v como w tienen el mismo segundo predecesor más antiguo, el empate se resuelve considerando sus terceros predecesores más antiguos, y así sucesivamente.

Aplicar esta regla directamente comparando vértices según ella daría como resultado un algoritmo ineficiente. En cambio, la búsqueda en anchura lexicográfica utiliza una estructura de datos de partición de conjuntos para producir el mismo ordenamiento de forma más eficiente, del mismo modo que una búsqueda en anchura estándar utiliza una estructura de datos de cola para producir su ordenamiento de forma eficiente.

El algoritmo de búsqueda en anchura lexicográfica reemplaza la cola de vértices de una búsqueda en anchura estándar con una secuencia ordenada de conjuntos de vértices. Los conjuntos de la secuencia forman una partición de los vértices restantes. En cada paso, se elimina un vértice v del primer conjunto de la secuencia, y si dicha eliminación provoca que el conjunto quede vacío, se elimina el conjunto de la secuencia. A continuación, cada conjunto de la secuencia se reemplaza por dos subconjuntos: los vecinos de v y los no vecinos de v . El subconjunto de vecinos se coloca antes en la secuencia que el subconjunto de no vecinos. En pseudocódigo , el algoritmo se puede expresar de la siguiente manera:

• Inicializa una secuencia Σ de conjuntos, que contenga un único conjunto con todos los vértices.
• Inicializa la secuencia de vértices de salida como vacía.
• Mientras Σ no sea vacío:
  • Encuentra y elimina un vértice v del primer conjunto en Σ
  • Si el primer conjunto en Σ ahora está vacío, retírelo de Σ.
  • Agregue v al final de la secuencia de salida.
  • Para cada arista vw tal que w todavía pertenece a un conjunto S en Σ:
    • Si el conjunto S que contiene w aún no ha sido reemplazado mientras se procesa v , cree un nuevo conjunto de reemplazo vacío T y colóquelo antes de S en la secuencia; de lo contrario, sea T el conjunto anterior a S.
    • Mueva w de S a T , y si esto hace que S quede vacío, retire S de Σ.

Cada vértice se procesa una sola vez, cada arista se examina únicamente cuando se procesan sus dos extremos y (con una representación adecuada para los conjuntos en Σ que permite mover elementos de un conjunto a otro en tiempo constante) cada iteración del bucle interno solo requiere tiempo constante. Por lo tanto, al igual que algoritmos de búsqueda en grafos más sencillos, como la búsqueda en amplitud y la búsqueda en profundidad , este algoritmo requiere tiempo lineal.

El algoritmo se llama búsqueda en anchura lexicográfica porque el orden que produce es un ordenamiento que también podría haber sido producido por una búsqueda en anchura, y porque si el ordenamiento se utiliza para indexar las filas y columnas de una matriz de adyacencia de un grafo, entonces el algoritmo ordena las filas y columnas en orden lexicográfico .

Se dice que una enumeración de los vértices de un grafo es un ordenamiento LexBFS si es un resultado posible de la aplicación de LexBFS a dicho grafo.

Dejar${\displaystyle G=(V,E)}$ser un gráfico con${\displaystyle n}$vértices. Recuerda que${\displaystyle N(v)}$es el conjunto de vecinos de${\displaystyle v}$. Dejar${\displaystyle \sigma =(v_{1},\dots,v_{n})}$ser una enumeración de los vértices de${\displaystyle V}$. La enumeración${\displaystyle \sigma }$es un ordenamiento LexBFS (con fuente)${\displaystyle v_{1}}$) si, para todos${\displaystyle 1\leq i<j<k\leq n}$con${\ Displaystyle v_ {i} \ en N (v_ {k}) \ setminus N (v_ {j})}$, existe${\displaystyle m<i}$de tal manera que ${\ Displaystyle v_ {m} \ en N (v_ {j}) \ setminus N (v_ {k})}$.

• Brandstädt, Andreas ; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey , SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Bretscher, Anna; Corneil, Derek ; Habib, Michel; Paul, Christophe (2008), "Un algoritmo simple de reconocimiento de cografos LexBFS en tiempo lineal" , SIAM Journal on Discrete Mathematics , 22 (4): 1277–1296 , CiteSeerX 10.1.1.188.5016 , doi : 10.1137/060664690 .
• Corneil, Derek G. (2004), "Búsqueda en amplitud lexicográfica: una revisión", Métodos de teoría de grafos en informática: 30.º taller internacional, WG 2004, Bad Honnef, Alemania, 21-23 de junio de 2004, Artículos revisados , Lecture Notes in Computer Science, vol.  3353, Springer-Verlag, pp. 1-19 , doi : 10.1007/978-3-540-30559-0_1 , ISBN  978-3-540-24132-4.
• Habib, Michel; McConnell, Ross; Paul, Christophe; Viennot, Laurent (2000), "Lex-BFS y refinamiento de particiones, con aplicaciones a la orientación transitiva, el reconocimiento de grafos de intervalos y la comprobación de unos consecutivos", Theoretical Computer Science , 234 ( 1–2 ): 59–84 , doi : 10.1016/S0304-3975(97)00241-7.
• Rose, DJ; Tarjan, RE ; Lueker, GS (1976), "Aspectos algorítmicos de la eliminación de vértices en grafos", SIAM Journal on Computing , 5 (2): 266–283 , doi : 10.1137/0205021.