So implementieren Sie einen Graph-Traversal-Algorithmus mit Java

So implementieren Sie den Graph-Traversal-Algorithmus mit Java

Graph ist eine wichtige Datenstruktur in der diskreten Mathematik und wird häufig zur Beschreibung der Beziehung zwischen Dingen verwendet. Der Graph-Traversal-Algorithmus bezieht sich auf den Prozess des sequentiellen Besuchs aller Knoten im Graphen, beginnend mit einem bestimmten Knoten und unter Einhaltung bestimmter Regeln. Zu den häufig verwendeten Graph-Traversal-Algorithmen gehören die Tiefensuche (DFS) und die Breitensuche (BFS). In diesem Artikel wird erläutert, wie die Java-Sprache zum Implementieren dieser beiden Graph-Traversal-Algorithmen verwendet wird, und es wird spezifischer Beispielcode bereitgestellt.

1. Tiefensuche (DFS)

Die Tiefensuche ist ein Vorbestellungs-Traversal-Algorithmus, der ausgehend von einem Startknoten rekursiv seine benachbarten Knoten aufsucht, bis keine nicht besuchten benachbarten Knoten mehr angetroffen werden, und dann zum vorherigen Knoten zurückverfolgt und besuchen Sie weiterhin nicht besuchte benachbarte Knoten, bis der gesamte Graph durchlaufen ist.

Das Folgende ist ein Beispielcode für das Durchlaufen eines Diagramms mithilfe der Tiefensuche:

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);
    }
}

Ausgabeergebnis:

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

2. Breitensuche (BFS)

Die Breitensuche ist ein horizontaler Durchlaufalgorithmus, beginnend mit Besuchen Sie einen Startknoten und besuchen Sie die Knoten Schicht für Schicht nacheinander, bis der gesamte Graph durchlaufen ist. Verwenden Sie eine Warteschlange, um eine Breitensuche zu implementieren, indem Sie jeweils einen Knoten aus der Warteschlange nehmen und dann die nicht besuchten benachbarten Knoten zur Warteschlange hinzufügen.

Das Folgende ist ein Beispielcode zum Durchlaufen eines Diagramms mittels Breitensuche:

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);
    }
}

Ausgabeergebnis:

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

Im obigen Beispielcode verwenden wir Adjazenzlisten, um die Struktur des Diagramms darzustellen und das Diagramm durch Addition aufzubauen Kanten. Anschließend rufen wir die Methoden DFS und BFS auf, um den Graphen zu durchlaufen. Das Ausgabeergebnis ist die vom Traversalalgorithmus erhaltene Knotensequenz.

Zusammenfassung:

Durch die Einführung und den Beispielcode dieses Artikels können wir lernen, wie man die Java-Sprache verwendet, um Graph-Traversal-Algorithmen zu implementieren, einschließlich Tiefensuche und Breitensuche. Diese beiden Durchquerungsalgorithmen werden in der Realität häufig verwendet, beispielsweise in Webcrawlern, Labyrinthlösungen und anderen Bereichen. Durch die Beherrschung des Graph-Traversal-Algorithmus können wir damit verbundene Probleme schnell und effektiv lösen.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie einen Graph-Traversal-Algorithmus mit Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!