Meisterung von Graphendatenstrukturen in Java

Einführung

In diesem Tutorial lernst du, wie du in Java Graphen-Datenstrukturen erstellen und manipulieren kannst. Graphen sind eine grundlegende Datenstruktur, die verwendet wird, um Beziehungen zwischen Objekten darzustellen. Wir werden die verschiedenen Typen von Graphen erkunden, wie man sie repräsentiert und wie man übliche Operationen wie das Hinzufügen und Entfernen von Knoten und Kanten, Breitensuche, Tiefensuche und vieles mehr implementiert.

Erstellen einer Knotenklasse

Zunächst erstellen wir eine Node-Klasse, um die Knoten im Graphen zu repräsentieren. Jeder Knoten wird einen Namen und möglicherweise andere Informationen wie einen Wert oder ein Gewicht haben.

public class Node {
    private String name;

    public Node(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

Erstellen einer Graphenklasse

Als nächstes erstellen wir eine Graph-Klasse, um den Graphen selbst zu repräsentieren. Wir verwenden eine Adjazenzliste, um Kanten und deren Endpunkte zu speichern.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Node, List<Node>> adjacencyList;

    public Graph() {
        this.adjacencyList = new HashMap<>();
    }

    public void addNode(Node node) {
        adjacencyList.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(Node node1, Node node2) {
        adjacencyList.get(node1).add(node2);
        adjacencyList.get(node2).add(node1);
    }

    public void removeNode(Node node) {
        adjacencyList.values().stream().forEach(e -> e.remove(node));
        adjacencyList.remove(node);
    }

    public void removeEdge(Node node1, Node node2) {
        List<Node> list1 = adjacencyList.get(node1);
        List<Node> list2 = adjacencyList.get(node2);
        if (list1!= null) {
            list1.remove(node2);
        }
        if (list2!= null) {
            list2.remove(node1);
        }
    }

    public List<Node> getNeighbors(Node node) {
        return adjacencyList.get(node);
    }
}

Erstellen eines Graphen

Lassen Sie uns jetzt einen Graphen erstellen und einige Knoten und Kanten hinzufügen.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

Breitensuche

Wir implementieren nun einen Breitensuche-Algorithmus, um die Knoten im Graphen in Breitensuche-Reihenfolge zu traversieren.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class BreadthFirstSearch {
    public List<Node> bfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        Deque<Node> queue = new ArrayDeque<>();
        visited.add(start);
        queue.add(start);

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            List<Node> neighbors = graph.getNeighbors(node);
            for (Node neighbor : neighbors) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }

        return visited;
    }
}

Beispiel, wie man es ausführt:

javac Graph.java BreadthFirstSearch.java Node.java && java BreadthFirstSearch

Tiefensuche

Wir implementieren nun einen Tiefensuche-Algorithmus, um die Knoten im Graphen in Tiefensuche-Reihenfolge zu traversieren.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class DepthFirstSearch {
    public List<Node> dfs(Graph graph, Node start) {
        List<Node> visited = new ArrayList<>();
        dfsHelper(graph, start, visited, new HashSet<>());
        return visited;
    }

    private void dfsHelper(Graph graph, Node current, List<Node> visited, Set<Node> seen) {
        visited.add(current);
        seen.add(current);
        for (Node neighbor : graph.getNeighbors(current)) {
            if (!seen.contains(neighbor)) {
                dfsHelper(graph, neighbor, visited, seen);
            }
        }
    }
}

Beispiel, wie man es ausführt:

javac Graph.java DepthFirstSearch.java Node.java && java DepthFirstSearch

Entfernen eines Knotens

Wir können einen Knoten aus dem Graphen entfernen und auch alle an diesen Knoten angeschlossenen Kanten entfernen.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");
Node nodeC = new Node("C");
Node nodeD = new Node("D");

graph.addNode(nodeA);
graph.addNode(nodeB);
graph.addNode(nodeC);
graph.addNode(nodeD);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);
graph.addEdge(nodeC, nodeD);
graph.addEdge(nodeD, nodeA);

graph.removeNode(nodeC);

Entfernen einer Kante

Wir können eine Kante zwischen zwei Knoten im Graphen entfernen.

Graph graph = new Graph();
Node nodeA = new Node("A");
Node nodeB = new Node("B");

graph.addNode(nodeA);
graph.addNode(nodeB);

graph.addEdge(nodeA, nodeB);
graph.addEdge(nodeB, nodeC);

graph.removeEdge(nodeA, nodeB);

需要注意的是，你提供的代码中graph.addEdge(nodeB, nodeC);这里的nodeC未定义，我按照原文翻译了，但实际代码可能存在问题。

Zusammenfassung

In diesem Tutorial haben wir gelernt, wie man in Java eine Graphendatenstruktur mit Hilfe von Knoten und Adjazenzliste repräsentiert. Wir haben auch Operationen implementiert, um den Graphen zu manipulieren, einschließlich des Hinzufügens und Entfernens von Knoten und Kanten. Schließlich haben wir zwei Suchalgorithmen implementiert: Breitensuche und Tiefensuche.

Graphendatenstrukturen in Java