22.23 Graphs
Graphs
Overview
A Graph is a collection of nodes (vertices) connected by edges. It can be directed or undirected.
Topics
- Representations (Adjacency List, Adjacency Matrix)
- Graph Traversals (DFS, BFS)
Examples
Adjacency List Representation
import java.util.*;
Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(4));
graph.put(3, Arrays.asList(4));
graph.put(4, new ArrayList<>());
System.out.println(graph);
DFS Traversal
void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
if (visited.contains(node)) return;
visited.add(node);
System.out.println(node);
for (int neighbor : graph.get(node)) {
dfs(neighbor, graph, visited);
}
}
Set<Integer> visited = new HashSet<>();
dfs(1, graph, visited);