Depth-First Search (DFS) Algorithm

Graph traversal algorithms play a crucial role in analyzing and navigating graph structures. DFS is one such algorithm that explores as far as possible along each branch before backtracking, making it particularly useful for traversing deep into graph structures.

DFS operates by recursively visiting each vertex in the graph and exploring as far as possible along each branch before backtracking. This traversal strategy results in a depth-first exploration of the graph, visiting vertices in a depth-first manner.

class Graph {
    constructor() {
        this.adjacencyList = {};
    }
    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = [];
        }
    }
    addEdge(vertex1, vertex2) {
        this.adjacencyList[vertex1].push(vertex2);
        this.adjacencyList[vertex2].push(vertex1);
    }
    depthFirstSearch(startVertex) {
        const visited = {};
        const result = [];

        const dfs = (vertex) => {
            if (!vertex) return;
            visited[vertex] = true;
            result.push(vertex);
            this.adjacencyList[vertex].forEach((neighbor) => {
                if (!visited[neighbor]) {
                    dfs(neighbor);
                }
            });
        };

        dfs(startVertex);
        return result;
    }
}

// Example usage:
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');

console.log("DFS traversal:", graph.depthFirstSearch('A'));

The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This complexity arises from visiting each vertex and each edge once in the worst-case scenario.

DFS is commonly used in various real-world applications, such as maze solving, network traversal, and cycle detection in directed graphs.