YouTipGraph Theory Iter
## Adjacent Node Iterator
The most common operation in graph theory is traversing adjacent edges, traversing related adjacent edges through a vertex. The time complexity of traversing adjacent edges in an adjacency matrix is O(V), while adjacency list can be found directly, which is more efficient.
!(#)
**Adjacency Matrix Iteration:**
...
public Iterable adj(int v){
assert v >=0&& v < n;
Vector adjV =new Vector();
for(int i =0; i < n ; i ++)
if( g)
adjV.add(i);
return adjV;
}
...
**Adjacency List Iteration:**
...
// Return all adjacent edges of a vertex in the graph
// Since Java uses reference mechanism, returning a Vector does not bring additional overhead
public Iterable adj(int v){
assert v >=0&& v < n;
return g;
}
...
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 adjacency matrix.
In this section, we wrote a test case GraphReadTest, which implements graph display by calling the abstract interface, and can be viewed in the read package.
/**
* Abstract interface for 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 adj(int v);
}
### Java Example Code
**Source package download:***οΌ1οΌAdjacency Matrix Iteration**
## src/tutorial/graph/DenseGraphIterater.java file code:
package tutorial.graph;
import java.util.Vector;
/**
* Adjacency Matrix Iteration
*/
public class DenseGraphIterater {
// Number of nodes
private int n;
// Number of edges
private int m;
// Whether it is a directed graph
private boolean directed;
// The 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;
// Initialize g as an n*n boolean matrix, each g is false, meaning there is no edge
// false is the default value of boolean variable
g =new boolean;
}
// 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 =0&& w =0&& v =0&& w < n ;
return g;
}
// Return all adjacent edges of a vertex in the graph
// Since Java uses reference mechanism, returning a Vector does not bring additional overhead,
public Iterable adj(int v){
assert v >=0&& v < n;
Vector adjV =new Vector();
for(int i =0; i < n ; i ++)
if( g)
adjV.add(i);
return adjV;
}
}
**οΌ2οΌAdjacency List Iteration**
## src/tutorial/graph/SparseGraphIterater.java file code:
package tutorial.graph;
import java.util.Vector;
/**
* Adjacency List Iteration
*/
public class SparseGraphIterater {
private int n;// Number of nodes
private int m;// Number of edges
private boolean directed;// Whether it is a directed graph
private Vector[] g;// The 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;
// Initialize g as n empty vectors, each g is empty, meaning there is no edge
g =(Vector[])new Vector;
for(int i =0; i < n ; i ++)
g=new Vector();
}
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 =0&& w =0&& v =0&& w < n ;
for(int i =0; i < g.size(); i ++)
if( g.elementAt(i)== w )
return true;
return false;
}
// Return all adjacent edges of a vertex in the graph
// Since Java uses reference mechanism, returning a Vector does not bring additional overhead,
public Iterable adj(int v){
assert v >=0&& v < n;
return g;
}
}