The traversal of a graph is the graph's equivalent of the traversal of a tree, as discussed in an earlier chapter. Just as in the case of a tree, we can traverse either breadth-first or depth-first. However, unlike a tree, a graph can reach all the vertices without going through the edges. This makes it necessary to consider the traversal of all the edges and vertices separately. Another thing is that a graph has no designated root, so we can start from any particular vertex. Finally, since a graph may not be connected, we may not be able to traverse all the vertices/edges, starting from one single vertex. This is achieved by performing the traversal repeatedly, starting each time from any vertex that has not been visited yet already. This is a simple extension of the basic breadth-first or depth-first traversal that we are going to discuss here.
First, let's discuss visiting vertices using both the breadth-first and depth-first search. It involves maintaining two collections of vertices: one that stores all the vertices that are discovered but are yet to be visited/explored and another that stores a Boolean array that checks whether a vertex has already been explored/visited.
The collection of vertices that are discovered but yet to be explored can be of two types: if it is a stack, we have a depth-first traversal, and if it is a queue, we have a breadth-first traversal.
To implement both depth-first and breadth-first searches in a single method, we need to create a super interface of our Stack and Queue interfaces. We will need to define three methods in it:
public interface OrderedStore<E> {
void insert(E value);
E pickFirst();
E checkFirst();
}Now implement these methods in the Stack and Queue interfaces as default methods to delegate to their appropriate methods:
public interface Stack<E> extends OrderedStore<E>{
void push(E value);
E pop();
E peek();
@Override
default E checkFirst(){
return peek();
}
@Override
default void insert(E value){
push(value);
}
@Override
default E pickFirst(){
return pop();
}
}
public interface Queue<E> extends OrderedStore<E>{
void enqueue(E value);
E dequeue();
E peek();
@Override
default E checkFirst(){
return peek();
}
@Override
default void insert(E value){
enqueue(value);
}
@Override
default E pickFirst(){
return dequeue();
}
}This allows us to use the OrderedStore interface to hold both a stack and a queue. We also create a new functional interface that represents a lambda that takes two arguments and does not return anything:
public interface TwoArgumentStatement<E,F> {
void doSomething(E e, F f);
}We implement this search as a default method in the Graph interface itself.
enum TraversalType{
DFT, BFT
}In the beginning, we only insert the starting vertex to the collection of vertices that are not yet explored. Then, we loop until all the vertices that can be discovered in the search are processed and there are no more elements in the collection of vertices. We avoid processing each vertex from the collection of vertices if it has already been processed. Otherwise, we mark it as "being processed" and invoke the visitor on it. Finally, we expand this vertex by inserting all its neighbors to the collection of elements that have to be processed:
default void visitAllConnectedVertices(int startingNode, TwoArgumentStatement<Integer, V> visitor, TraversalType type) {
OrderedStore<Integer> toBeProcessed = null;
boolean doneProcessing[] = new boolean[maxVertexID()+1];
switch (type){
case BFT:
toBeProcessed = new QueueImplLinkedList<Integer>();
break;
case DFT:
toBeProcessed = new StackImplLinkedList<Integer>();
break;
}
toBeProcessed.insert(startingNode);
while(toBeProcessed.checkFirst()!=null){
int currentVertex = toBeProcessed.pickFirst();
if(doneProcessing[currentVertex]){
continue;
}
doneProcessing[currentVertex] = true;
visitor.doSomething(currentVertex,
getVertexValue(currentVertex)); for(int neighbor:getNeighbors(currentVertex)){
if(doneProcessing[neighbor]==false){
toBeProcessed.insert(neighbor);
}
}
}
}The process of traversal of edges is also very similar; we can follow either the breadth-first or depth-first traversal. In this case, the visitor needs access to both the source and target of the edges, which makes it necessary to store both of them in the stack or queue we use. For this purpose, we create a class named Edge. The class is comparable so that edges can be stored in a binary search tree for easy search ability:
class Edge implements Comparable<Edge>{
int source;
int target;
public Edge(int source, int target) {
this.source = source;
this.target = target;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Edge edge = (Edge) o;
if (source != edge.source) return false;
return target == edge.target;
}
@Override
public int hashCode() {
int result = source;
result = 31 * result + target;
return result;
}
@Override
public int compareTo(Edge o) {
if(source!=o.source){
return source - o.source;
}else {
return target - o.target;
}
}
}Now we can implement the process of traversal of edges using the breadth-first and depth-first traversal:
default void visitAllConnectedEdges(int startingNode, ThreeArgumentStatement<Integer, Integer, E> visitor,
TraversalType type){
OrderedStore<Edge> toBeProcessed = null;
boolean doneProcessing[] = new boolean[maxVertexID()+1];
switch (type){
case BFT: toBeProcessed = new QueueImplLinkedList<Edge>(); break;
case DFT: toBeProcessed = new StackImplLinkedList<Edge>(); break;
}
toBeProcessed.insert(new Edge(-1, startingNode));
while (toBeProcessed.checkFirst()!=null){
Edge edge = toBeProcessed.pickFirst();
LinkedList<Integer> neighbors = getNeighbors(edge.target);
if(edge.source>=0) {
visitor.doSomething(edge.source, edge.target,
getEdgeValue(edge.source, edge.target));
}
if(doneProcessing[edge.target]){
continue;
}
for(int target: neighbors){
if(isUndirected() && doneProcessing[target]){
continue;
}
Edge nextEdge = new Edge(edge.target, target);
if(nextEdge.target!=edge.source)
toBeProcessed.insert(nextEdge);
}
doneProcessing[edge.target] = true;
}
}For each traversal, either all vertices or edges, all edges must be traversed. This is true even if you just want to visit the vertices. The actual complexity depends on the particular map implementation, so we will use that the complexity of the operation getNeighbors method is θ(g(|V|)).
If you're visiting either the edges or vertices, ensure that each vertex is expanded only once. This operation is done |V| times, each of which is θ(g(|V|)). So the complexity, due to the expansion of the vertex, to find out the neighbors is θ(|V|g(|V|)). When expanded, they are visited once, and for each edge, we have one neighbor. Some of these neighbors have been visited before; however, we need to perform constant time to verify this. So each vertex is visited once and each neighbor is checked once. This changes the complexity to θ(|V|g(|V|) + |E| ). Since we have seen an implementation of a graph that has the constant time getNeighbors method, we can have a traversal in θ(|V| + |E| ).