Me temo un poco que me faltan algunos detalles importantes en su pregunta, porque es bastante simple y no puedo ver una razón para usar Quora en lugar de una rápida búsqueda en Google. De todos modos, esta es mi respuesta:
Desea eliminar el borde (a, b) (OT: ¿qué tiene de malo todo esto (u, v)? ¿Por qué estamos usando notación con dos letras casi idénticas?).
En un gráfico desordenado, primero debe encontrar el vértice ‘a’ . Big O de esta operación depende de su implementación, debe ser O (1) u O (log | V |) (constante para hashtable y logarithmic para algún tipo de árbol).
- Procesamiento de lenguaje natural: ¿Cuál es la mejor manera de detectar si un fragmento de texto es interrogativo?
- ¿Por qué el número total de respuestas en mi cuenta de Quora disminuyó repentinamente en 10?
- ¿Cuál es el algoritmo más fácil para encontrar el camino más corto en un robot seguidor de línea para un principiante?
- ¿Es posible implementar algoritmos de aprendizaje automático en lenguaje ensamblador?
- Ayúdame con el problema TopCoder SRM - 599, div - I, level - 3?
Entonces quitas el borde. Esta operación depende de su implementación una vez más, varía entre O (a (| E |)) (número de bordes de ‘a’ si necesita copiarlos todos excepto (a, b)) y O (1) (algunos tipo de tabla hash de nuevo). Entonces haga lo mismo para (b, a), que realmente no cambia Big O de esta operación.
Para el gráfico ordenado, usted hace exactamente lo mismo excepto eliminar (b, a).
Como puede ver, solo necesita multiplicar el tiempo de dos operaciones que propuse y obtuvo respuesta para su implementación.
Espero que de alguna manera logré responder tu pregunta y no me perdí algo …
