Lo que está tratando de encontrar aquí es un MST o árbol de expansión mínimo. Supongamos que todos los nodos están en el mismo componente.
Un árbol de expansión mínimo (MST) de un gráfico es un árbol de expansión cuyo peso (la suma de los pesos de sus bordes) no es mayor que el peso de cualquier otro árbol de expansión.
Dado que estamos encontrando esto, podemos usar muchos algoritmos diferentes. De lo más simple a lo más difícil:
- Como senior que busca postularse a empresas como Google, Palantir, etc., ¿cómo puedo mejorar mis estructuras de datos avanzadas, algoritmos y cursos de bioinformática y tener más confianza en mí mismo al ingresar a un aula y no pensar automáticamente que soy estúpido? ?
- ¿Cómo saben las computadoras cuándo comienza y termina una cadena binaria?
- ¿Qué algoritmo es mejor para datos no estructurados?
- ¿Cuáles son algunos ejemplos de árboles M aplicados a problemas del mundo real?
- ¿Por qué ocurre el peor de los casos en Max-Heapify cuando la fila final del árbol está medio llena?
BFS
Podríamos usar un algoritmo BFS simple dado que todos los bordes tienen el mismo peso. Simplemente comenzamos nuestro BFS en cualquier nodo y atravesamos todos los nodos a los que está conectado en esa dirección (ya sea que no esté dirigido o dirigido). Marque los nodos visitados y continúe hasta que se atraviesen todos los nodos. Dado que este es un BFS básico, cualquier árbol de expansión es el árbol de expansión mínimo. Este BFS se ejecuta en O (V + E).
DFS
Podríamos usar un algoritmo DFS para encontrar el MST con cualquier gráfico. Al igual que un DFS normal, solo atravesamos cada ruta y retrocedemos hasta que se hayan visitado todos los nodos. El uso de un DFS recursivo o no recursivo funcionará con una pila. Este DFS también se ejecuta en O (V + E).
Algoritmo de Prim / Dijkstra
Una de las formas más comunes de encontrar un MST es usar Prim, un algoritmo que usa principios similares a los de Dijkstra. Dijkstra se usa para encontrar el camino más corto entre dos nodos. Esto no siempre será parte de un MST, pero los conceptos básicos son similares. Prim utiliza el enfoque de Dijkstra para mirar los nodos, excepto que no tiene en cuenta las longitudes de ruta anteriores. El algoritmo de Prim funciona en todos los gráficos y se ejecuta en O (V * V) sin montones u O (Vlog (V) + Elog (V)) con montones binarios.
Algoritmo de Kruskal
Otra forma común es usar el algoritmo de Kruskal. Kruskal funciona colocando todos los vértices en un árbol de nodos y colocando todos los bordes en una cola prioritaria. Luego, tomará el primer borde de la cola de prioridad (se ordena durante la inserción) y lo ignorará (si forma un ciclo) o lo extraerá (si no forma un ciclo, creando un árbol más grande). Una vez que se han agregado los bordes V-1, se encuentra el MST. Este algoritmo se ejecuta en todos los gráficos y se ejecuta en O (Elog (E)) que es igual a O (Elog (V)).
Mediante el uso de estos 4 algoritmos, podríamos encontrar el MST de cualquier gráfico dado. Para obtener más información sobre estos algoritmos, puede leer libros y conferencias sobre estructuras de datos y algoritmos. Estos irán más allá de estos algoritmos básicos y pueden profundizar en la teoría de grafos y otros.
¡Buena suerte y diviértete en todas tus empresas de CS!
Tony Li, los principios subyacentes de la ruta más corta de Dijkstra le permitirán descubrir el algoritmo de Prim que encuentra el árbol de expansión mínima. Dijkstra no necesariamente te dará el MST.
Si toma este ejemplo, el algoritmo de Dijkstra dirá que la longitud total del MST es 15. Mientras tanto, Prim nos dirá que es 7. Por lo tanto, Dijkstra no devolverá el árbol correcto de manera consistente.
