Árbol de expansión - Categoría

El árbol de expansión de un grafo no dirigido es un árbol que incluye todos los vértices de G con el número mínimo posible de aristas.

Para un grafo desconectado, no hay un solo árbol, sino un bosque de expansión, que consiste en un árbol de expansión de cada componente conectado.

Characteristics:

  • It’s implementation is only on undirected graph.

  • Process is done only on edges with positive costs.

  • When the graph is connected

    • The resulting edges make up a tree

  • When the graph is not connected,

    • Finds a minimum spanning tree for each connected component.

    • The resulting edges make up a forest.

Ver también

Índices y tablas