Adjacent Node Iterator
The most common operation in graph theory is traversing adjacent edges, using a vertex to traverse the related adjacent edges. The time complexity of traversing adjacent edges in an adjacency matrix is O(V), while an adjacency list can find them directly, which is more efficient.
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;
}
...
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:
...
// Return all adjacent edges of a vertex in the graph
// Since Java uses a reference mechanism, returning a Vector does not incur extra overhead,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
...
// Return all adjacent edges of a vertex in the graph
// Since Java uses a reference mechanism, returning a Vector does not incur extra overhead,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
...
For these two graph representation methods, we can abstract an interface to generate the framework of this set of algorithms, without having to consider whether the underlying layer is an adjacency list or an adjacency matrix.
This section writes a test case GraphReadTest, which implements graph display by calling the abstract interface and can be viewed in the read package.
/**
* Abstract interface of the graph
*/
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);
}
* Abstract interface of the graph
*/
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 Package Download:Download
(1) Adjacency matrix iteration
src/example/graph/DenseGraphIterater.java file code:
package example.graph;
import java.util.Vector;
/**
* Adjacency matrix iteration
*/
public class DenseGraphIterater {
// Node count
private int n;
// Edge count
private int m;
// Whether it is a directed graph
private boolean directed;
// Specific data of the graph
private boolean[][] g;
// constructor
public DenseGraphIterater( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g is initialized as an n*n boolean matrix, each g[i][j] is false, indicating no edges
// false is the default value for boolean variables
g = new boolean[n][n];
}
// Return the number of nodes
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 whether 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];
}
// Return all adjacent edges of a vertex in the graph
// Since Java uses a reference mechanism, returning a Vector does not incur extra 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;
}
}
import java.util.Vector;
/**
* Adjacency matrix iteration
*/
public class DenseGraphIterater {
// Node count
private int n;
// Edge count
private int m;
// Whether it is a directed graph
private boolean directed;
// Specific data of the graph
private boolean[][] g;
// constructor
public DenseGraphIterater( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0;
this.directed = directed;
// g is initialized as an n*n boolean matrix, each g[i][j] is false, indicating no edges
// false is the default value for boolean variables
g = new boolean[n][n];
}
// Return the number of nodes
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 whether 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];
}
// Return all adjacent edges of a vertex in the graph
// Since Java uses a reference mechanism, returning a Vector does not incur extra 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/example/graph/SparseGraphIterater.java file code:
package example.graph;
import java.util.Vector;
/**
* Adjacency list iteration
*/
public class SparseGraphIterater {
private int n; // Node count
private int m; // Edge count
private boolean directed; // Whether it is a directed graph
private Vector<Integer>[] g; // Specific data of the graph
// constructor
public SparseGraphIterater( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // Initialize with no edges
this.directed = directed;
// g is initialized as n empty vectors, meaning each g[i] is empty, i.e., no edges
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 nodes
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 ++;
}
// Verify whether 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 ;
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 in the graph
// Since Java uses a reference mechanism, returning a Vector does not incur extra overhead,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}
import java.util.Vector;
/**
* Adjacency list iteration
*/
public class SparseGraphIterater {
private int n; // Node count
private int m; // Edge count
private boolean directed; // Whether it is a directed graph
private Vector<Integer>[] g; // Specific data of the graph
// constructor
public SparseGraphIterater( int n , boolean directed ){
assert n >= 0;
this.n = n;
this.m = 0; // Initialize with no edges
this.directed = directed;
// g is initialized as n empty vectors, meaning each g[i] is empty, i.e., no edges
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 nodes
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 ++;
}
// Verify whether 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 ;
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 in the graph
// Since Java uses a reference mechanism, returning a Vector does not incur extra overhead,
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
}