Traversal de prioridad de profundidad
El recorrido de la prioridad de profundidad es similar a caminar un laberinto de una persona:
Como se muestra en la figura, seleccione un borde desde el punto de partida para caminar al siguiente vértice. Antes de llegar a un vértice, se marca que este vértice ha llegado.
Cuando llega un vértice marcado, vuelva al vértice anterior y luego seleccione un vértice que no se haya alcanzado.
Continúe retirándose cuando no haya un paso a la intersección que se ha retirado.
Para el componente conectado , mire el concepto: el sub-gráfico extremadamente conectado del gráfico no se denomina el componente conectado de G. Solo hay un componente conectado de cualquier gráfico conectado, es decir, y el gráfico no conectado no conectado tiene múltiples componentes conectados.
Echemos un vistazo a los ejemplos específicos:
paquete com.datastructure.graph; // Encuentre el componente unicom del gráfico no autorizado Componentes de clase pública {Gráfico privado;// matriz para almacenar la entrada privada booleana [] visitada; // almacenar el estado privado int componentCount; // número de componentes intactados int [] Mark; // almacena la marca de los componentes unidos a la que la noda pertenece // constructor de gráficos privados inicializados inicializados (creación de gráficos privados inicializados (creación de gráficos privados (creación de gráficos privados (componentes conectados marque; {this.graph = graph; componentCount = 0; // El número inicial de componentes conectados es 0 visitado = new Boolean [gráfico está marcado como -1} para (int i = 0; i <graph.v (); i ++) {// El recorrido de prioridad de profundidad del nodo no visitado if (! visited [i]) {dfs (i); componentCount ++; // después de dfs en un nodo hasta el final, un componente conectado termina, el número +1}}}} void privado dfs (int i) (int i) (int i) (int i) (int i) (int i) (int i) (int i) (int i) (int i) (int i) (inti), el número intitir I) en el inicio IT). {visitado [i] = true; // nodo I se ha accedido a Mark [i] = componentCount; // nodo I pertenece al número actual de componentes conectados (marcas) para (int nodo: gráfico.adjacentnode (i)) {// atraviesa los nodos adyacentes de los nodos adyacentes i en el gráfico if (! visitado [nodo]) // dfsdfs (nódulo adyacente}}} nodo público I isConnected(int v, int w) {return mark[v] == mark[w];// judging whether the two nodes are connected based on the marks of the connected components to which the two nodes belong to}public int getComponentCount() {return componentCount;// Return the number of connected components in the graph}}//public class Components {//// private Graph G; // referencia del gráfico // booleano privado [] visitado; // si se accede al nodo durante el proceso DFS // private int ccount; // registrar el número de componentes de China Unicom // private int [] id; // La marca del componente unicom de China correspondiente para cada nodo //// // Traversal de prioridad de profundidad del gráfico // privado void dfs (int v) {//// visitado [v] = true; // El estado de acceso del nodo V se establece en true // id [v] = ccount; // La correspondiente marca de nodo de Node V de China se establece en ccount ///// // atravesando el punto de adyacencia del nodo v i // para (int i: g.adjacentnode (v)) {// // si el punto de adyacencia no ha sido accedido todavía // if (! dfs (i); //} //} /// // constructor para encontrar los componentes conectados del gráfico injustificado // componentes públicos (gráfico gráfico) {///// // algoritmo inicialización // g = gráfica; ///////us visitó el estado accedido del nodo en el almacenamiento de almacenamiento g // visitado = nuevo boolean [gv ()]; componentes a los que el nodo pertenece al gráfico de almacenamiento de matriz g // id = new int [gv ()]; //// // // El número de componentes conectados se inicializa a 0 // ccount = 0; //// // Establezca todas las matrices visitadas en falso; Establezca todas las matrices de id a -1 // for (int i = 0; i <gv (); i ++) {// visited [i] = false; // id [i] = -1; //} // // busca el componente unicom de la gráfica // for (int i = 0; i <gv (); i ++) // access a nodo que no ha sido accesible // // // prioridad de profundidad Traversal // dfs (i); // ccount ++; //} //} /// Devuelve el número de componentes unicom de la gráfica // int Count () {// return cCount; //} ///// // consultas si el punto v y el punto están conectados (w las marcas de los componentes de los comunicantes de los nodo V y W son las mismas componentes de nodo V y W iSconnected (int v, int w) {// afirmar v> = 0 && v <gv (); // afirmar w> = 0 && w <gv (); // return id [v] == id [w]; //} //}El número de componentes de pase es 3
Resumir
Lo anterior es todo el contenido de este artículo sobre la implementación de la programación de Java de los ejemplos de código de componente de transversal y de conectividad de prioridad profunda. Espero que sea útil para todos. Si hay alguna deficiencia, deje un mensaje para señalarlo. Siga Wulin.com y ganará más.