Proversal prioritária de profundidade
A prioridade da profundidade Traversal é semelhante a caminhar um labirinto por uma pessoa:
Como mostrado na figura, selecione uma borda do ponto de partida para caminhar até o próximo vértice. Antes de chegar a um vértice, está marcado que este vértice chegou.
Quando um vértice marcado chegar, volte ao vértice anterior e selecione um vértice que não foi alcançado.
Continue a recuar quando não houver passagem para o cruzamento que foi retirado.
Para o componente conectado , consulte o conceito: o sub-gráfico extremamente conectado do gráfico não direcionado G é chamado de componente conectado de G. Existe apenas um componente conectado de qualquer gráfico conectado, ou seja, ele próprio, e o gráfico não direcionado não conectado possui vários componentes conectados.
Vamos dar uma olhada nos exemplos específicos:
pacote com.datastructure.graph; // Encontre o componente unicom do gráfico não autorizado componentes da classe pública {Gráfico privado; // Matriz para armazenar o booleano privado de entrada [] visitado; // armazenar a marca privada componentCount; // número de componentes conectados privados [] marcação; // armazenam a marca privada do componente unido; Componentes (gráfico do gráfico) {this.graph = Graph; componentCount = 0; // O número inicial de componentes conectados é 0 visitado = new boolean [graph.v ()]; mark = new int [graph.v ()]; para (int i = 0; i <graph.v (); i ++) {visitado [i] = [false status; O componente do nó é marcado como -1} para (int i = 0; i <graf.v (); i ++) {// a traseira de prioridade da profundidade do nó não visitado se (! i) {visitou [i] = true; // nó I foi acessado Mark [i] = componentCount; // O nó I pertence ao número atual de componentes conectados (marcas) para (int node: Graph.adjacentNode (i)) {// Traverse os nós adjacentes de node i no gráfico se (! Boolean 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; // referência do gráfico // private boolean [] visitado; // se o nó é acessado durante o processo DFS // private int ccount; // registra o número de componentes da China Unicom // private Int [] id; // A marca do componente unicom da China correspondente para cada nó //// // travessia de prioridade de profundidade do gráfico // private void dfs (int v) {//// visitou [v] = true; // O status de acesso do nó v é definido como true // id [v] = ccount; // A marca unicom da China correspondente do nó V é definida como ccount //// // percorrendo o ponto de adjacência do nó v i // para (int i: g.adjacentNode (v)) {// // se o ponto de adjacência não foi acessado ainda // se (! dfs (i); //} //} /// // construtor para encontrar os componentes conectados do gráfico não -rigoroso // componentes públicos (gráfico do gráfico) {/////// algoritmo inicialização // g = gráfico; //// ///////////////sicorithm Initialization // g = GRAPH; Componentes aos quais o nó pertence ao gráfico de armazenamento da matriz g // id = new int [gv ()]; //// // // o número de componentes conectados é inicializado como 0 // ccount = 0; /////// defina todas as matrizes visitadas como false; set all id arrays to -1// for (int i = 0; i < GV(); i++) {// visited[i] = false;// id[i] = -1;// }/// // Find the Unicom component of the graph// for (int i = 0; i < GV(); i++)// // Access a node that has not been accessed// if (!visited[i]) {// // // traslado de prioridade de profundidade // dfs (i); // ccount ++; //} //} /// retorna o número de componentes unicom do gráfico // int count () {// return ccount; //} /////sery Point V e Point W são conectados (W, Wheds the Mards of the Marks of the Marks of the Marks of the Malks of the Malks of the Malks of the Malks of the Malks of the Malt; isConnected (int v, int w) {// Assert V> = 0 && V <gv (); // Assert w> = 0 && w <gv (); // Return ID [v] == id [w]; //} //}O número de componentes de aprovação é 3
Resumir
O exposto acima é todo o conteúdo deste artigo sobre a implementação de programação Java de exemplos de código de componentes de travessia e conectividade de prioridade profunda. Espero que seja útil para todos. Se houver alguma falha, deixe uma mensagem para apontá -la. Siga wulin.com e você ganhará mais.