Graph Traversal - BFS & DFS

class Graph {
    constructor() {
        this.adjacencyList = {};
    }

    addVertex(vertex) {
        if (!this.adjacencyList[vertex]) {
            this.adjacencyList[vertex] = [];
        }
    }

    addEdge(v1, v2) {
        this.adjacencyList[v1].push(v2);
        this.adjacencyList[v2].push(v1);
    }

    // Breadth-First Search
    BFS(start) {
        const queue = [start];
        const result = [];
        const visited = { [start]: true };

        while (queue.length) {
            const vertex = queue.shift();
            result.push(vertex);

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

        return result;
    }

    // Depth-First Search (Recursive)
    DFS(start) {
        const result = [];
        const visited = {};

        const dfs = (vertex) => {
            if (!vertex) return;
            visited[vertex] = true;
            result.push(vertex);

            this.adjacencyList[vertex].forEach(neighbor => {
                if (!visited[neighbor]) {
                    dfs(neighbor);
                }
            });
        };

        dfs(start);
        return result;
    }

    // Shortest Path (BFS-based)
    shortestPath(start, end) {
        const queue = [[start]];
        const visited = { [start]: true };

        while (queue.length) {
            const path = queue.shift();
            const vertex = path[path.length - 1];

            if (vertex === end) return path;

            this.adjacencyList[vertex].forEach(neighbor => {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push([...path, neighbor]);
                }
            });
        }

        return null;
    }

    // Cycle Detection
    hasCycle() {
        const visited = {};
        const recStack = {};

        const hasCycleUtil = (vertex) => {
            visited[vertex] = true;
            recStack[vertex] = true;

            for (const neighbor of this.adjacencyList[vertex]) {
                if (!visited[neighbor] && hasCycleUtil(neighbor)) {
                    return true;
                } else if (recStack[neighbor]) {
                    return true;
                }
            }

            recStack[vertex] = false;
            return false;
        };

        for (const vertex in this.adjacencyList) {
            if (!visited[vertex] && hasCycleUtil(vertex)) {
                return true;
            }
        }

        return false;
    }
}

// Usage
const g = new Graph();
g.addVertex('A'); g.addVertex('B'); g.addVertex('C');
g.addEdge('A', 'B'); g.addEdge('B', 'C');
console.log(g.BFS('A')); // ['A', 'B', 'C']
console.log(g.shortestPath('A', 'C')); // ['A', 'B', 'C']