Graph

class Graph { private int vertices; private List<List<Integer>> adj; Graph(int v) { vertices = v; adj = new ArrayList<>(); for (int i = 0; i < v; i++) adj.add(new ArrayList<>()); } void addEdge(int u, int v) { adj.get(u).add(v); adj.get(v).add(u); // Undirected graph } // BFS — O(V + E) void bfs(int start) { boolean[] visited = new boolean[vertices]; Queue<Integer> queue = new LinkedList<>(); visited[start] = true; queue.offer(start); while (!queue.isEmpty()) { int node = queue.poll(); System.out.print(node + " "); for (int neighbor : adj.get(node)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } } // DFS — O(V + E) void dfs(int start) { boolean[] visited = new boolean[vertices]; dfsHelper(start, visited); } private void dfsHelper(int node, boolean[] visited) { visited[node] = true; System.out.print(node + " "); for (int neighbor : adj.get(node)) { if (!visited[neighbor]) dfsHelper(neighbor, visited); } } // Detect cycle in undirected graph boolean hasCycle() { boolean[] visited = new boolean[vertices]; for (int i = 0; i < vertices; i++) if (!visited[i] && cycleDetect(i, visited, -1)) return true; return false; } private boolean cycleDetect(int node, boolean[] visited, int parent) { visited[node] = true; for (int neighbor : adj.get(node)) { if (!visited[neighbor]) { if (cycleDetect(neighbor, visited, node)) return true; } else if (neighbor != parent) return true; } return false; } // Shortest path (BFS — unweighted) int[] shortestPath(int src) { int[] dist = new int[vertices]; Arrays.fill(dist, -1); Queue<Integer> q = new LinkedList<>(); dist[src] = 0; q.offer(src); while (!q.isEmpty()) { int node = q.poll(); for (int neighbor : adj.get(node)) { if (dist[neighbor] == -1) { dist[neighbor] = dist[node] + 1; q.offer(neighbor); } } } return dist; } }