Comment implémenter un algorithme de parcours graphique à l'aide de Java

Comment utiliser Java pour implémenter un algorithme de parcours graphique

Le graphique est une structure de données importante en mathématiques discrètes et est souvent utilisé pour décrire la relation entre les choses. L'algorithme de parcours de graphe fait référence au processus de visite séquentielle de tous les nœuds du graphe à partir d'un certain nœud et en suivant certaines règles. Les algorithmes de traversée de graphiques couramment utilisés incluent la recherche en profondeur d'abord (DFS) et la recherche en largeur d'abord (BFS). Cet article expliquera comment utiliser le langage Java pour implémenter ces deux algorithmes de traversée de graphiques et fournira des exemples de codes spécifiques.

1. Recherche en profondeur (DFS)

La recherche en profondeur est un algorithme de traversée de pré-ordre qui visite récursivement ses nœuds adjacents à partir d'un nœud de départ jusqu'à ce qu'il ne rencontre aucun nœud adjacent non visité, puis revient au nœud précédent. et continuez à visiter les nœuds adjacents non visités jusqu'à ce que tout le graphique soit parcouru.

Ce qui suit est un exemple de code pour parcourir un graphique via une recherche en profondeur d'abord :

import java.util.*;
 
class Graph {
    private int V; // 顶点的数量
    private LinkedList<Integer> adj[]; // 邻接表
 
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
 
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
 
    void DFSUtil(int v, Boolean visited[]) {
        visited[v] = true;
        System.out.print(v + " ");
 
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }
 
    void DFS(int v) {
        Boolean visited[] = new Boolean[V];
        Arrays.fill(visited, false);
 
        DFSUtil(v, visited);
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.DFS(2);
    }
}

Résultat de sortie :

从顶点2开始的遍历结果：
2 0 1 3

2. Recherche en largeur d'abord (BFS)

La recherche en largeur d'abord est un algorithme de traversée horizontale, à partir de un nœud de départ, visitez les nœuds dans l'ordre un par un jusqu'à ce que tout le graphe soit parcouru. Utilisez une file d'attente pour implémenter une recherche en largeur, en prenant un nœud de la file d'attente à la fois, puis en ajoutant ses nœuds adjacents non visités à la file d'attente.

Ce qui suit est un exemple de code pour parcourir un graphique via une recherche en largeur d'abord :

import java.util.*;
 
class Graph {
    private int V; // 顶点的数量
    private LinkedList<Integer> adj[]; // 邻接表
 
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }
 
    void addEdge(int v, int w) {
        adj[v].add(w);
    }
 
    void BFS(int v) {
        boolean visited[] = new boolean[V];
 
        LinkedList<Integer> queue = new LinkedList<Integer>();
 
        visited[v] = true;
        queue.add(v);
 
        while (queue.size() != 0) {
            v = queue.poll();
            System.out.print(v + " ");
 
            Iterator<Integer> i = adj[v].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
 
    public static void main(String args[]) {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("从顶点2开始的遍历结果：");
        g.BFS(2);
    }
}

Résultat de sortie :

从顶点2开始的遍历结果：
2 0 3 1

Dans l'exemple de code ci-dessus, nous utilisons des listes de contiguïté pour représenter la structure du graphique et construisons le graphique en ajoutant bords. Ensuite, nous appelons respectivement les méthodes DFS et BFS pour parcourir le graphe. Le résultat de sortie est la séquence de nœuds obtenue par l'algorithme de parcours.

Résumé :

Grâce à l'introduction et à l'exemple de code de cet article, nous pouvons apprendre à utiliser le langage Java pour implémenter des algorithmes de traversée de graphes, y compris la recherche en profondeur d'abord et la recherche en largeur d'abord. Ces deux algorithmes de traversée sont largement utilisés dans la réalité, comme les robots d'exploration Web, la résolution de labyrinthes et d'autres domaines. En maîtrisant l'algorithme de parcours de graphes, nous pouvons résoudre les problèmes associés rapidement et efficacement.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!