Cet article décrit la méthode d'implémentation de l'algorithme de parcours en largeur basé sur Java pour les graphiques sous forme d'exemples. Les méthodes spécifiques sont les suivantes :
Utilisez la matrice de contiguïté pour stocker la méthode graphique :
1. Déterminez le nombre de sommets et d'arêtes du graphique
2. Les informations sur le sommet d'entrée sont stockées dans le sommet du tableau unidimensionnel
3. Initialisez la matrice de contiguïté ;
4. Entrez chaque arête tour à tour et stockez-la dans l'arc de la matrice de contiguïté.
Entrez les numéros de série i et j des deux sommets attachés à l'arête ;
Définissez la valeur de l'élément de la i-ème ligne et de la j-ème colonne de la matrice de contiguïté sur 1 ;
Définissez la valeur de l'élément de la j-ème ligne et de la i-ème colonne de la matrice de contiguïté sur 1 ;
Implémentation du parcours en largeur d'abord :
1. Initialiser la file d'attente Q
2. Visitez le sommet v ; visité[v]=1 ; le sommet v est ajouté à la file d'attente Q ;
3. while (la file d'attente Q n'est pas vide)
v=L'élément de tête de la file d'attente Q est retiré de la file d'attente ;
w = premier point adjacent du sommet v
pendant que (w existe)
Si w n'a pas été visité, visitez le sommet w ; visité[w]=1 ; le sommet w est placé dans la file d'attente Q ;
w = prochain point adjacent du sommet v
Le code d'implémentation est le suivant :
package com.teradata.lsw.sort; importer java.util.ArrayList; importer java.util.LinkedList; importer java.util.List; importer java.util.Queue; classe publique BFS {//informations sur le nœud de stockage objet privé [] sommets;//Tableau d'informations sur les bords de stockage private int[][] arcs;//Nombre d'arêtes private int vexnum;// Enregistrez si le i-ème nœud a été visité private boolean[] visité;//Construisez une liste chaînée temporaire pour stocker les nœuds qui ont été traversés private List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO Méthode générée automatiquement stubBFS g = new BFS(8);Character[] vertices = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H' };g.addVertex(sommets);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("Parcours du graphique en largeur en premier :");g.bfs();}//Breadth- première implémentation de traversée private void bfs() {// TODO Méthode générée automatiquement 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 = (Entier) q.remove().intValue();//Jugez que si toutes les traversées sont terminées, il n'est pas nécessaire de faire une boucle if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = this .firstAdjVex(j); k >= 0; k = this.nextAdjVex(j, k)) {if (!visité[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// Trouver le nœud suivant 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;}//Initialiser les bords du graphe private void addEdge(int i, int j) {/ / TODO Méthode générée automatiquement stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// Initialiser les nœuds du graphe private void addVertex(Object[] object) {// TODO Méthode générée automatiquement stubthis.vertices = object;}// Initialiser le graphe public BFS(int n) {// TODO Constructeur généré automatiquement stubvexnum = n ;vertices = new Object[n];arcs = new int[n][n];visited = new boolean[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éthode générée automatiquement stubtemp .add(sommets[i]);System.out.print(sommets[i] + " ");}}