Este artículo describe el método de implementación del algoritmo transversal de amplitud primero para gráficos en forma de ejemplos. Los métodos específicos son los siguientes:
Utilice la matriz de adyacencia para almacenar el método del gráfico:
1. Determinar el número de vértices y aristas del gráfico.
2. La información del vértice de entrada se almacena en el vértice de la matriz unidimensional.
3. Inicialice la matriz de adyacencia;
4. Ingrese cada borde por turno y guárdelo en el arco de la matriz de adyacencia.
Ingrese los números de serie i y j de los dos vértices adjuntos al borde;
Establezca el valor del elemento de la i-ésima fila y j-ésima columna de la matriz de adyacencia en 1;
Establezca el valor del elemento de la j-ésima fila y la i-ésima columna de la matriz de adyacencia en 1;
Implementación transversal primero en amplitud:
1. Inicializar la cola Q
2. Visite el vértice v; visitado [v] = 1; se agrega el vértice v a la cola Q;
3.mientras (la cola Q no está vacía)
v=El elemento principal de la cola Q está fuera de la cola;
w = primer punto adyacente del vértice v
mientras (w existe)
Si w no ha sido visitado, visite el vértice w; visitado[w]=1 se coloca en la cola Q;
w=siguiente punto adyacente del vértice v
El código de implementación es el siguiente:
paquete com.teradata.lsw.sort;importar java.util.ArrayList;importar java.util.LinkedList;importar java.util.List;importar java.util.Queue;clase pública BFS {//Información del nodo de almacenamiento Objeto privado[] vertices;// Matriz de información de borde de almacenamiento private int[][] arcs;//Número de bordes private int vexnum;// Registre si se ha visitado el i-ésimo nodo private boolean[] visitado;//Construya una lista vinculada temporal para almacenar los nodos que se han atravesado private List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO Método generado automáticamente 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("Recorrido en amplitud del gráfico primero:");g.bfs();}//Anchura- primera implementación transversal private void bfs() {// TODO Método generado automáticamente stubfor (int i = 0; i < vexnum; i++) {visited[i] = false;}Cola<Integer> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i );q.add(i);mientras (!q.isEmpty()) {int j = (Entero) q.remove().intValue();// Juzgue que si se completan todos los recorridos, no es necesario realizar un bucle if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = esto .firstAdjVex(j); k >= 0; k = esto.nextAdjVex(j, k)) {si (!visited[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// Encuentra el siguiente nodo public int firstAdjVex(int i) {for (int j = 0; j < vexnum ; j++) {if (arcos[i][j] > 0)return j;}return -1;}public int nextAdjVex(int i, int k) {para (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}//Inicializa los bordes del gráfico private void addEdge(int i, int j) {/ / TODO Método generado automáticamente stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// Inicializa los nodos del gráfico private void addVertex(Object[] object) {// TODO Método generado automáticamente stubthis.vertices = object;}// Inicializa el gráfico public BFS(int n) {// TODO Constructor generado automáticamente stubvexnum = n ;vértices = nuevo Objeto[n];arcos = nuevo int[n][n];visitado = nuevo booleano[n];for (int i = 0; i < vexnum; i++) {for (int j = 0; j < vexnum; j++) {arcs[i][j] = 0;}}}visita privada vacía (int i) {// TODO Método generado automáticamente stubtemp .add(vértices[i]);System.out.print(vértices[i] + " ");}}