Structures de données de graphe en Java

Introduction

Dans ce tutoriel, vous allez apprendre à créer et à manipuler des structures de données de graphe en Java. Les graphes sont une structure de données fondamentale utilisée pour représenter les relations entre des objets. Nous allons explorer les différents types de graphes, la manière de les représenter et la manière de mettre en œuvre des opérations courantes telles que l'ajout et la suppression de sommets et d'arêtes, la recherche en largeur, la recherche en profondeur, etc.

Skills Graph

Créez une classe Node

Tout d'abord, nous allons créer une classe Node pour représenter les sommets dans le graphe. Chaque nœud aura un nom et éventuellement d'autres informations, telles qu'une valeur ou un poids.

public class Node {
    private String name;

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

    public String getName() {
        return name;
    }
}

Créez une classe Graph

Ensuite, nous allons créer une classe Graph pour représenter le graphe lui-même. Nous utiliserons une liste d'adjacence pour stocker les arêtes et leurs extrémités.

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

Créez un graphe

Maintenant, créons un graphe et ajoutons quelques nœuds et arêtes.

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

Recherche en largeur

Nous allons maintenant implémenter un algorithme de recherche en largeur pour parcourir les nœuds du graphe dans l'ordre de largeur.

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

Exemple de la manière d'exécuter :

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

Recherche en profondeur

Nous allons maintenant implémenter un algorithme de recherche en profondeur pour parcourir les nœuds du graphe dans l'ordre de profondeur.

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

Exemple de la manière d'exécuter :

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

Supprimez un nœud

Nous pouvons supprimer un nœud du graphe et également supprimer toutes les arêtes connectées à ce nœud.

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

Supprimez une arête

Nous pouvons supprimer une arête entre deux nœuds du graphe.

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

Sommaire

Dans ce tutoriel, nous avons appris à créer une structure de données de graphe en Java en utilisant une représentation de nœud et de liste d'adjacence. Nous avons également implémenté des opérations pour manipuler le graphe, y compris l'ajout et la suppression de nœuds et d'arêtes. Enfin, nous avons implémenté deux algorithmes de recherche : la recherche en largeur et la recherche en profondeur.