Este artigo descreve o método de implementação do algoritmo de travessia em largura baseado em Java para gráficos na forma de exemplos. Os métodos específicos são os seguintes:
Use a matriz de adjacência para armazenar o método gráfico:
1. Determine o número de vértices e arestas do gráfico
2. As informações do vértice de entrada são armazenadas no vértice da matriz unidimensional
3. Inicialize a matriz de adjacência;
4. Insira cada aresta por vez e armazene-a no arco da matriz de adjacência.
Insira os números de série i e j dos dois vértices anexados à aresta;
Defina o valor do elemento da i-ésima linha e j-ésima coluna da matriz de adjacência como 1;
Defina o valor do elemento da j-ésima linha e i-ésima coluna da matriz de adjacência como 1;
Implementação de travessia em amplitude:
1. Inicialize a fila Q
2. Visite o vértice v; visitado[v]=1;
3.while (a fila Q não está vazia)
v=O elemento principal da fila Q foi retirado da fila;
w = primeiro ponto adjacente do vértice v
enquanto(w existe)
Se w não foi visitado, visite o vértice w visitado[w]=1;
w = próximo ponto adjacente do vértice v
O código de implementação é o seguinte:
pacote com.teradata.lsw.sort;importar java.util.ArrayList;importar java.util.LinkedList;importar java.util.List;importar java.util.Queue;classe pública BFS {//Informações do nó de armazenamento objeto privado[] vertices;//Matriz de informações de borda de armazenamento private int[][] arcs;//Número de arestas private int vexnum;// Registre se o i-ésimo nó foi visitado private boolean[] visitado;//Construa uma lista vinculada temporária para armazenar os nós que foram percorridos private List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO Método gerado automaticamente stubBFS g = new BFS(8);Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };g.addVertex(vértices);g.addEdge(0, 1);g .addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(3, 5);g.addEdge(4, 5);g.addEdge(2, 6);g.addEdge(2, 7);System.out.println("Amplitude do primeiro percurso do gráfico:");g.bfs();}//amplitude- implementação da primeira travessia private void bfs() {// TODO Método gerado automaticamente stubfor (int i = 0; i < vexnum; i++) {visited[i] = false;}Queue<Integer> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i );q.add(i);while (!q.isEmpty()) {int j = (inteiro) q.remove().intValue();//Julgue que se todas as travessias forem concluídas, não há necessidade de fazer um loop if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = este .firstAdjVex(j) >= 0; {q.add(k);visited[k] = true;visit(k);}}}}}}// Encontre o próximo nó public int firstAdjVex(int i) {for (int j = 0; j < vexnum ; j++) {if (arcs[i][j] > 0)return j;}return -1;}public int nextAdjVex(int i, int k) {for (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}//inicializar as bordas do gráfico private void addEdge(int i, int j) {/ / TODO Método gerado automaticamente stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// Inicialize os nós do gráfico private void addVertex(Object[] object) {// TODO Método gerado automaticamente stubthis.vertices = object;}// Inicialize o gráfico public BFS(int n) {// TODO Construtor gerado automaticamente stubvexnum = n ;vértices = novo Objeto[n];arcos = novo int[n][n];visitado = novo booleano[n];for (int i = 0; i < vexnum; i++) {for (int j = 0; j < vexnum; j++) {arcs[i][j] = 0;}}}private void visit(int i) {// TODO Método gerado automaticamente stubtemp .add(vértices[i]);System.out.print(vértices[i] + " ");}}