Itérateur de nœuds adjacents

L'opération la plus courante en théorie des graphes est de parcourir les arêtes adjacentes, en utilisant un sommet pour parcourir les arêtes adjacentes associées. La complexité temporelle du parcours des arêtes adjacentes dans une matrice d'adjacence est O(V), tandis qu'une liste d'adjacence peut les trouver directement, ce qui est plus efficace.

Itération de la matrice d'adjacence :

...
public Iterable<Integer> adj(int v) {
    assert v >= 0 && v < n;
    Vector<Integer> adjV = new Vector<Integer>();
    for(int i = 0 ; i < n ; i ++ )
        if( g[v][i] )
            adjV.add(i);
    return adjV;
}
...

Itération de la liste d'adjacence :

...
// Renvoie toutes les arêtes adjacentes à un sommet du graphe
// Comme Java utilise un mécanisme de référence, renvoyer un Vector n'entraîne pas de surcoût supplémentaire,
public Iterable<Integer> adj(int v) {
    assert v >= 0 && v < n;
    return g[v];
}
...

Pour ces deux méthodes de représentation de graphe, nous pouvons abstraire une interface afin de générer le cadre de cet ensemble d'algorithmes, sans avoir à se demander si la couche sous-jacente est une liste d'adjacence ou une matrice d'adjacence.

Cette section écrit un cas de test GraphReadTest, qui implémente l'affichage du graphe en appelant l'interface abstraite et peut être consulté dans le package read.

/**
* Interface abstraite du graphe
 */
public interface Graph {
    public int V();
    public int E();
    public void addEdge( int v , int w );
    boolean hasEdge( int v , int w );
    void show();
    public Iterable<Integer> adj(int v);
}

Exemple de code Java

Téléchargement du paquet de code source :Télécharger

(1) Itération de la matrice d'adjacence

Code du fichier src/example/graph/DenseGraphIterater.java :

package example.graph;

import java.util.Vector;

/**
* Itération de la matrice d'adjacence
 */
public class DenseGraphIterater {
    // Nombre de nœuds
    private int n;
    // Nombre d'arêtes
    private int m;
    // Indique s'il s'agit d'un graphe orienté
    private boolean directed;
    // Données spécifiques du graphe
    private boolean[][] g;

    // constructeur
    public DenseGraphIterater( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = directed;
        // g est initialisé comme une matrice booléenne n*n, chaque g[i][j] est false, ce qui indique qu'il n'y a pas d'arêtes
        // false est la valeur par défaut des variables booléennes
        g = new boolean[n][n];
    }
    // Renvoie le nombre de nœuds
    public int V(){ return n;}
    // Renvoie le nombre d'arêtes
    public int E(){ return m;}

    // Ajoute une arête au graphe
    public void addEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        if( hasEdge( v , w ) )
            return;
        g[v][w] = vrai;
        if( !directed )
            g[w][v] = vrai;
        m ++;
    }

    // Vérifie s'il existe une arête de v à w dans le graphe
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }
    // Renvoie toutes les arêtes adjacentes à un sommet du graphe
    // Comme Java utilise un mécanisme de référence, renvoyer un Vector n'entraîne pas de surcoût supplémentaire,
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        Vector<Integer> adjV = new Vector<Integer>();
        for(int i = 0 ; i < n ; i ++ )
            if( g[v][i] )
                adjV.add(i);
        return adjV;
    }
}

(2) Itération de liste d'adjacence

Code du fichier src/example/graph/SparseGraphIterater.java :

package example.graph;

import java.util.Vector;

/**
* Itération de liste d'adjacence
 */
public class SparseGraphIterater {

    private int n;  // Nombre de nœuds
    private int m;  // Nombre d'arêtes
    private boolean directed;    // Indique s'il s'agit d'un graphe orienté
    private Vector<Integer>[] g; // Données spécifiques du graphe

    // constructeur
    public SparseGraphIterater( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;    // Initialiser sans arêtes
        this.directed = directed;
        // g est initialisé comme n vecteurs vides, ce qui signifie que chaque g[i] est vide, c'est-à-dire aucune arête
        g = (Vector<Integer>[])new Vecteur[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }
    public int V(){ return n;} // Renvoie le nombre de nœuds
    public int E(){ return m;} // Renvoie le nombre d'arêtes

    // Ajoute une arête au graphe
    public void addEdge( int v, int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        g[v].ajoutez(w);
        if( v != w && !directed )
            g[w].ajoutez(v);

        m ++;
    }

    // Vérifie s'il existe une arête de v à w dans le graphe
    boolean hasEdge( int v , int w ){

        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;

        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v].elementAt(i) == w )
                return true;
        return false;
    }

    // Renvoie toutes les arêtes adjacentes à un sommet du graphe
    // Comme Java utilise un mécanisme de référence, renvoyer un Vector n'entraîne pas de surcoût supplémentaire,
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        return g[v];
    }
}
autres extensions