-Árbol de expansión y árbol de expansión mínimo-Árbol de expansión
El árbol libre es un gráfico conectado acíclico (sin raíz definida) (seleccionando un vértice como raíz en un árbol libre se convierte en un árbol ordinario).
Comenzando en la raíz y asignando un orden de izquierda a derecha a los nodos secundarios de cada vértice (a menudo llamado nodo en el árbol), se convierte en un árbol ordenado.
En aplicaciones de gráficos, a menudo necesitamos encontrar un subgrafo de un gráfico determinado para convertirlo en un árbol.
Árbol de expansión
Árbol de expansión
Si un subgrafo de un grafo conexo G es un árbol que contiene todos los vértices de G, entonces el subgrafo se llama generación del árbol G.
Un árbol de expansión es el subgrafo conectado más pequeño que contiene todos los vértices de un gráfico conectado.
El árbol de expansión de un gráfico no solo comienza a atravesar desde diferentes vértices, sino que también puede obtener diferentes árboles de expansión.
Árbol de expansión primero en profundidad y árbol de expansión primero en amplitud
() Método de solución del árbol de expansión
Supongamos que el gráfico G = (V E) es un gráfico conexo con n vértices Gráfico, búsquelo mediante búsqueda en profundidad (búsqueda en amplitud) desde cualquier vértice (punto fuente) de G.
Durante el proceso de búsqueda, los n vértices y aristas (V I V J) pasaron al buscar desde el vértice visitado vi hasta el punto adyacente no visitado v j (* * * n elementos).
El subgrafo conectado mínimo es un árbol de expansión (el punto de origen es la raíz del árbol de expansión)
El árbol de expansión obtenido mediante la búsqueda en profundidad generalmente se denomina profundidad -primer árbol de expansión o árbol de expansión DFS. El árbol de expansión obtenido mediante la búsqueda en amplitud se denomina árbol de expansión en amplitud.
Se llama árbol de expansión BPS
Por ejemplo, el árbol de expansión DFS obtenido del vértice V del gráfico G se muestra en la Figura (a) a continuación. El proceso de generación específico se muestra en la demostración de animación del árbol de expansión BFS que se muestra en la Figura (b) a continuación.
Vea una demostración animada del proceso de generación de volúmenes.
() Algoritmo para encontrar el árbol de expansión DFS y el árbol de expansión BFS
Siempre que agregue el borde generador apropiado (v i v j) a la declaración if del algoritmo DFS (o DFSM) antes de la declaración de llamada recursiva Se puede obtener realizando operaciones como exportar o guardar bordes.
Encontrar el algoritmo del árbol de expansión DFS
Al agregar la operación de borde del árbol de expansión a la declaración if del algoritmo BFS (BFSM), se puede obtener el algoritmo del árbol de expansión BFS . Ver ejercicio.
Nota
①La altura del árbol de expansión del gráfico no excederá la altura de otros árboles de expansión del gráfico.
②El árbol de expansión del gráfico no solo comienza a atravesar desde diferentes vértices, sino que también puede obtener diferentes árboles de expansión.
Definición general de árbol de expansión
Si se puede acceder sistemáticamente a todos los vértices del gráfico desde un determinado vértice del gráfico, entonces consta de los bordes pasados durante el recorrido y todos los vértices del gráfico El subgrafo se llama árbol de expansión del gráfico (esta definición se aplica no solo a los gráficos no dirigidos, sino también a los gráficos dirigidos)
() Si G es un gráfico dirigido fuertemente conectado, entonces se puede acceder a todos los vértices en G desde cualquier vértice V, de modo que se puede obtener un árbol de expansión con V como raíz.
() Si G es un gráfico dirigido con raíz y la raíz es V, puede completar el recorrido de G comenzando desde la raíz V para obtener el árbol de expansión de G con la raíz V.
En la siguiente figura, (a) es un gráfico dirigido con V como raíz, y su árbol de expansión DFS y árbol de expansión BPS se muestran en las figuras (b) y (c) respectivamente.
() Si G es un gráfico no dirigido desconectado, el algoritmo DFS (o BFS) debe llamarse varias veces desde el exterior para completar el recorrido de G. Cada llamada externa sólo puede acceder a uno de G.
El conjunto de vértices de componentes conectados Estos vértices y los bordes por los que pasan constituyen el árbol de expansión DFS (o BPS) de los componentes conectados y la generación DFS (o BFS) de cada componente conectado de g.
Los árboles forman el bosque BFS.
() Si G es un gráfico dirigido no fuertemente conectado y el punto de origen no es la raíz del gráfico dirigido, generalmente solo se puede obtener el bosque generador del gráfico dirigido durante el recorrido.
Por ejemplo, en el gráfico dirigido que se muestra en (a) a continuación, los bosques que abarcan DFS y BFS se muestran en (b) y (c) respectivamente.
Lishi Xinzhi/Article/program/sjjg/201311/23831