Depth-First Search Algorithm for Graphs

Depth-First Search (DFS) is an algorithm used to traverse or search a tree or graph. In depth-first traversal, we begin traversing the graph from a specific vertex. When an unvisited adjacent vertex is encountered, it is marked as visited, and its adjacent vertices are recursively visited until all adjacent vertices have been visited or the current vertex has no unvisited adjacent vertices left.

Depth-first traversal is typically implemented using recursion or a stack. Specifically, we can start at any vertex in the graph, mark it as visited, and push it onto the stack. Then, we pop a vertex from the stack, visit all its unvisited adjacent vertices, mark them as visited, and push them onto the stack one by one. This process is repeated until the stack is empty, indicating the end of the traversal.

Depth-first traversal is very useful for handling connected graphs and tree structures. It can help us identify connected components in a graph, determine if a graph is bipartite, solve topological sorting problems, and more. Additionally, depth-first traversal can be applied to solve maze problems, Sudoku puzzles, and other similar challenges. However, it should be noted that the time complexity of depth-first traversal can reach O(n+m), where n and m are the number of vertices and edges in the graph, respectively. Therefore, when dealing with large-scale graphs, other algorithms might need to be considered.

Java Implementation

::: code-tabs
@tab DFS

public class DFS {
    public static String dfs(Graph g){
        String result = "";
        if (g.vertices < 1){
            return result;
        }
        boolean[] visited = new boolean[g.vertices];
        for(int i=0; i<g.vertices; i++) { 
            if(!visited[i]) { 
                result = result + dfsVisit(g, i, visited); 
            } 
        }
        return result;
    }
    public static String dfsVisit(Graph g, int source, boolean[] visited) {
        String result = "";
        Stack<Integer> stack = new Stack<Integer>(g.vertices);
        stack.push(source);
        while (!stack.isEmpty()) {
            int current_node = stack.pop();
            result += String.valueOf(current_node);
            DoublyLinkedList<Integer>.Node temp = null;
            if(g.adjacencyList[current_node] != null)
                temp = g.adjacencyList[current_node].headNode;
            while (temp != null) {
                if (!visited[temp.data]) {
                    stack.push(temp.data);
                }
                temp = temp.nextNode;
            }
            visited[current_node] = true;
        }
        return result;
    }
}

@tab Graph

public class Graph{
    int vertices;
    DoublyLinkedList<Integer> adjacencyList[];
    
    @SuppressWarnings("unchecked")
    public Graph(int vertices) {
        this.vertices = vertices;
        adjacencyList = new DoublyLinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyList[i] = new DoublyLinkedList<>();
        }
    }
    public void addEdge(int source, int destination){
        if (source < vertices && destination < vertices){
        this.adjacencyList[source].insertAtEnd(destination);
        }
    }
    public void printGraph(){
        System.out.println(">>Adjacency List of Directed Graph<<");
        for (int i = 0; i < vertices; i++){
            if(adjacencyList[i]!=null){
                System.out.print("|" + i + "| => ");
                DoublyLinkedList<Integer>.Node temp = adjacencyList[i].getHeadNode();
                while (temp != null){
                    System.out.print("[" + temp.data + "] -> ");
                    temp = temp.nextNode;
                }
                System.out.println("null");
            }else{
                System.out.println("|" + i + "| => "+ "null");
            }
        }
    }
}

@tab DoublyLinkedList

public class DoublyLinkedList<T> {
    public class Node {
        public T data;
        public Node nextNode;
        public Node prevNode;
    }
    public Node headNode;
    public Node tailNode;
    public int size;
    public DoublyLinkedList() {
        this.headNode = null;
        this.tailNode = null;
    }
    public boolean isEmpty() {
        if (headNode == null && tailNode == null)
            return true;
        return false;
    }
    public Node getHeadNode() {
        return headNode;
    }
    public Node getTailNode() {
        return tailNode;
    }
    public int getSize() {
        return size;
    }
    public void insertAtHead(T data) {
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = this.headNode; 
        newNode.prevNode = null;
        if (headNode != null)
            headNode.prevNode = newNode;
        else
            tailNode = newNode;
        this.headNode = newNode;
        size++;
    }
    public void insertAtEnd(T data) {
        if(isEmpty()) {
            insertAtHead(data);
            return;
        }
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;
        newNode.prevNode = tailNode;
        tailNode.nextNode = newNode;
        tailNode = newNode;
        size++;
    }
    public void printList() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
            return;
        }
        Node temp = headNode;
        System.out.print("List : null <- ");
        while (temp.nextNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.nextNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }
    public void printListReverse() {
        if (isEmpty()) {
            System.out.println("List is Empty!");
        }
        Node temp = tailNode;
        System.out.print("List : null <- ");
        while (temp.prevNode != null) {
            System.out.print(temp.data.toString() + " <-> ");
            temp = temp.prevNode;
        }
        System.out.println(temp.data.toString() + " -> null");
    }
    public void deleteAtHead() {
        if (isEmpty())
            return;
        headNode = headNode.nextNode;
        if (headNode == null)
            tailNode = null;
        else
            headNode.prevNode = null;
        size--;
    }
    public void deleteAtTail() {
        if (isEmpty())
            return;
        tailNode = tailNode.prevNode;
        if (tailNode == null)
            headNode = null;
        else
            tailNode.nextNode = null;
        size--;
    }
}

@tab Stack

public class Stack<V> {
    private int maxSize;
    private int top;
    private V[] array;
    private int currentSize;
    @SuppressWarnings("unchecked")
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        this.top = -1; 
        array = (V[]) new Object[maxSize];
        this.currentSize = 0;
    }
    public int getCurrentSize() {
        return currentSize;
    }
    public int getMaxSize() {
        return maxSize;
    }
    public boolean isEmpty() {
        return top == -1;
    }
    public boolean isFull() {
        return top == maxSize - 1;
    }
    public V top() {
        if (isEmpty())
            return null;
        return array[top];
    }
    public void push(V value) {
        if (isFull()) {
            System.err.println("Stack is Full!");
            return;
        }
        array[++top] = value; 
        currentSize++;
    }
    public V pop() {
        if (isEmpty())
            return null;
        currentSize--;
        return array[top--]; 
    }
}

:::