Adjacent Node Iterator

One of the most common operations in graph theory is traversing adjacent edges by starting from a vertex and iterating through its related edges. Traversing adjacent edges using an adjacency matrix has a time complexity of O(V), whereas an adjacency list can directly locate these edges, resulting in higher efficiency.

Adjacency Matrix Iteration:

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

Adjacency List Iteration:

...
// Returns all adjacent edges of a vertex in the graph
// Since Java uses reference mechanisms, returning a Vector does not incur additional overhead,
public Iterable<Integer> adj(int v) {
    assert v >= 0 && v < n;
    return g[v];
}
...

For these two graph representations, we can abstract an interface to generate the framework of this set of algorithms, without needing to consider whether the underlying structure is an adjacency list or an adjacency matrix.

This section includes a test case, GraphReadTest, which demonstrates the graph display by invoking the abstract interface. You can view it in the read package.

/**
 * Abstract interface for graphs
 */
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);
}

Java Example Code

Source Code Download: Download

(1) Adjacency Matrix Iteration

src/tutorialpro/graph/DenseGraphIterater.java File Code:

package tutorialpro.graph;

import java.util.Vector;

/**
 * Adjacency Matrix Iteration
 */
public class DenseGraphIterater {
    // Number of vertices
    private int n;
    // Number of edges
    private int m;
    // Whether the graph is directed
    private boolean directed;
    // Graph data
    private boolean[][] g;

    // Constructor
    public DenseGraphIterater( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;
        this.directed = directed;
        // Initialize g as a boolean matrix of n*n, with each g[i][j] being false, indicating no edges
        // false is the default value for boolean variables
        g = new boolean[n][n];
    }
    // Return the number of vertices
    public int V(){ return n;}
    // Return the number of edges
    public int E(){ return m;}

    // Add an edge to the graph
    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] = true;
        if( !directed )
            g[w][v] = true;
        m ++;
    }

    // Verify if there is an edge from v to w in the graph
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }
}

// Returns all adjacent edges of a vertex in a graph
// Since Java uses reference mechanism, returning a Vector does not incur additional overhead,
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) Adjacency List Iteration

src/tutorialpro/graph/SparseGraphIterater.java File Code:

package tutorialpro.graph;

import java.util.Vector;

/**
 * Adjacency List Iteration
 */
public class SparseGraphIterater {

    private int n;  // Number of vertices
    private int m;  // Number of edges
    private boolean directed;   // Whether the graph is directed
    private Vector<Integer>[] g; // Graph data

    // Constructor
    public SparseGraphIterater( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.m = 0;    // Initialize with no edges
        this.directed = directed;
        // Initialize g with n empty vectors, indicating no edges for each g[i]
        g = (Vector<Integer>[])new Vector[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }
    public int V(){ return n;} // Return the number of vertices
    public int E(){ return m;} // Return the number of edges

    // Add an edge to the graph
    public void addEdge( int v, int w ){

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

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

        m ++;
    }

    // Check if there is an edge from v to w
    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;
    }

    // Return all adjacent edges of a vertex
    // Since Java uses reference mechanism, returning a Vector does not incur additional overhead,
    public Iterable<Integer> adj(int v) {
        assert v >= 0 && v < n;
        return g[v];
    }
}