¿Cuál es la complejidad temporal del mejor algoritmo para determinar si un gráfico no dirigido es un árbol?El mejor algoritmo para determinar si un gráfico no dirigido es un árbol
¿Podemos decir Big-oh (n), con n vértices ??
Sí, es O (n).
Elija un nodo de inicio y realice un primer recorrido de profundidad. Si visita un nodo más de una vez, no es un árbol.
Sí, es O (n). Con una búsqueda de profundidad en primer lugar en un gráfico dirigido tiene 3 tipos de bordes no arbóreos: cruz, atrás y adelante.
Para una caja no dirigida, el único tipo de borde no arbóreo es un borde posterior. Entonces, solo necesitas buscar los bordes posteriores.
En resumen, elija un vértice inicial. Recorre y sigue comprobando si el borde encontrado es un borde posterior. Si encuentra n-1 bordes de árbol sin encontrar bordes posteriores y luego, se queda sin bordes, es oro.
(es decir, back edge es donde el vértice en el otro extremo ya se ha encontrado) y debido a las propiedades de los gráficos no dirigidos, el vértice en el otro extremo sería un antecesor del nodo presente en el árbol que se está construyendo.)
thnx .. también podemos hacerlo utilizando BFS en O (n) tiempo – rakesh
Puede hacerlo, pero BFS podría ser más lento porque no encontrará ciclos tan rápido. –
Thnx anthony ... también podemos hacerlo usando BFS con O (n) tiempo – rakesh
Sí, pero la profundidad primero es mejor porque encontrará ciclos más rápidos. –
Verifique también que se visiten todos los nodos, de lo contrario, el gráfico podría ser un bosque. – dieram3