1. Basics of Graph Representation in Java
Graphs can be represented in two main ways:
- Adjacency List (preferred for sparse graphs)
- Adjacency Matrix (used for dense graphs)
Adjacency List Representation (Using HashMap/HashMap or ArrayList)
import java.util.*;
class Graph {
Map<Integer, List<Integer>> adjList = new HashMap<>();
// Add edge to graph (undirected)
public void addEdge(int u, int v) {
adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u); // For undirected graph
}
// Add directed edge (u -> v)
public void addDirectedEdge(int u, int v) {
adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
}
}Adjacency Matrix Representation
class Graph {
int V; // Number of vertices
int[][] adjMatrix;
public Graph(int V) {
this.V = V;
adjMatrix = new int[V][V];
}
// Add edge (directed graph)
public void addEdge(int u, int v) {
adjMatrix[u][v] = 1; // Directed edge from u to v
}
// Add undirected edge
public void addUndirectedEdge(int u, int v) {
adjMatrix[u][v] = 1;
adjMatrix[v][u] = 1; // Undirected edge
}
}2. Basic Graph Traversals
Depth-First Search (DFS)
DFS explores as far as possible along each branch before backtracking. It uses a stack (or recursion).
class GraphDFS {
private Map<Integer, List<Integer>> adjList;
public GraphDFS() {
adjList = new HashMap<>();
}
public void addEdge(int u, int v) {
adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}
public void dfs(int start) {
Set<Integer> visited = new HashSet<>();
dfsUtil(start, visited);
}
private void dfsUtil(int node, Set<Integer> visited) {
visited.add(node);
System.out.println(node);
for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
dfsUtil(neighbor, visited);
}
}
}
}Breadth-First Search (BFS)
BFS explores all nodes at the present depth level before moving on to nodes at the next depth level. It uses a queue.
class GraphBFS {
private Map<Integer, List<Integer>> adjList;
public GraphBFS() {
adjList = new HashMap<>();
}
public void addEdge(int u, int v) {
adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}
public void bfs(int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.println(node);
for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
}3. Shortest Path Algorithms
Dijkstra's Algorithm (for Weighted Graphs with Non-negative Weights)
Dijkstra's algorithm finds the shortest paths from a source node to all other nodes in a graph with non-negative edge weights.
import java.util.*;
class Dijkstra {
private Map<Integer, List<int[]>> adjList = new HashMap<>();
// Add edge to graph (u -> v with weight w)
public void addEdge(int u, int v, int w) {
adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(new int[]{v, w});
adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(new int[]{u, w}); // For undirected graph
}
public int[] dijkstra(int start, int V) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{start, 0}); // {vertex, distance}
while (!pq.isEmpty()) {
int[] current = pq.poll();
int node = current[0];
int d = current[1];
// If already processed
if (d > dist[node]) continue;
for (int[] neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
int neighborNode = neighbor[0];
int weight = neighbor[1];
if (dist[node] + weight < dist[neighborNode]) {
dist[neighborNode] = dist[node] + weight;
pq.offer(new int[]{neighborNode, dist[neighborNode]});
}
}
}
return dist;
}
}Bellman-Ford Algorithm (for Graphs with Negative Weights)
The Bellman-Ford algorithm can handle negative weight edges and detects negative weight cycles.
class BellmanFord {
public int[] bellmanFord(int V, int[][] edges, int start) {
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
for (int i = 1; i < V; i++) {
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int weight = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
// Check for negative weight cycles
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int weight = edge[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
System.out.println("Graph contains negative weight cycle");
return null;
}
}
return dist;
}
}4. Minimum Spanning Tree (MST)
Kruskal's Algorithm (Greedy Approach)
Kruskal’s algorithm finds the minimum spanning tree by sorting all edges and adding edges one by one if they do not form a cycle.
import java.util.*;
class Kruskal {
class Edge implements Comparable<Edge> {
int u, v, weight;
Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
public int kruskal(int V, List<Edge> edges) {
Collections.sort(edges);
UnionFind uf = new UnionFind(V);
int mstWeight = 0;
for (Edge edge : edges) {
if (uf.union(edge.u, edge.v)) {
mstWeight += edge.weight;
}
}
return mstWeight;
}
class UnionFind {
int[] parent;
UnionFind(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
return true;
}
return false;
}
}
}5. Topological Sorting
Topological sorting is used for Directed Acyclic Graphs (DAGs). It orders the vertices so that for every directed edge u -> v, vertex u comes before v.
Kahn's Algorithm (BFS-based)
import java.util.*;
class TopologicalSort {
public List<Integer> topologicalSort(int V, List<List<Integer>> adjList) {
int[] inDegree = new int[V];
for (List<Integer> adj : adjList) {
for (int v : adj) {
inDegree[v]++;
}
}
Queue<Integer> queue = new LinkedList<>();
for
(int i = 0; i < V; i++) {
if (inDegree[i] == 0) {
queue.add(i);
}
}
List<Integer> topoOrder = new ArrayList<>();
while (!queue.isEmpty()) {
int node = queue.poll();
topoOrder.add(node);
for (int neighbor : adjList.get(node)) {
if (--inDegree[neighbor] == 0) {
queue.add(neighbor);
}
}
}
return topoOrder.size() == V ? topoOrder : new ArrayList<>(); // Check for cycle
}
}6. Advanced Topics
Floyd-Warshall Algorithm (All-Pairs Shortest Path)
This algorithm computes shortest paths between all pairs of nodes in a graph with positive or negative edge weights.
class FloydWarshall {
public void floydWarshall(int V, int[][] graph) {
int[][] dist = new int[V][V];
// Initialize distances
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (i == j) dist[i][j] = 0;
else if (graph[i][j] == 0) dist[i][j] = Integer.MAX_VALUE;
else dist[i][j] = graph[i][j];
}
}
// Floyd-Warshall algorithm
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
// Print the solution matrix
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == Integer.MAX_VALUE) System.out.print("INF ");
else System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
}7.Union-Find (Disjoint Set Union)
The Union-Find data structure provides an efficient way to manage a partition of a set into disjoint subsets. It supports two main operations:
- Find: Determines the representative (or root) of the set containing a particular element.
- Union: Merges two sets containing different elements into a single set.
Optimizations
To make the Union-Find operations more efficient, we use two techniques:
- Path Compression: This helps to flatten the tree structure when performing the
findoperation. It reduces the time complexity for futurefindoperations by making each node in the path point directly to the root. - Union by Rank (or Size): This ensures that the tree remains balanced by attaching the smaller tree under the root of the larger tree when performing the
unionoperation. This prevents the tree from becoming too deep, keeping operations efficient.
Code Implementation of Union-Find with Path Compression and Union by Rank
class UnionFind {
private int[] parent;
private int[] rank;
// Constructor to initialize Union-Find data structure
public UnionFind(int size) {
parent = new int[size];
rank = new int[size];
// Initially, each element is its own parent (itself)
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 1; // Rank (or size) of each set is 1
}
}
// Find the representative (root) of the set containing x, with path compression
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // Path compression
}
return parent[x];
}
// Union two sets containing x and y, using union by rank
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
// If both elements are already in the same set, no need to do anything
if (rootX == rootY) {
return;
}
// Union by rank: attach the smaller tree under the larger tree
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++; // Increase rank if both trees are of equal size
}
}
// Check if two elements are in the same set
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}Explanation of the Code
parent[]: This array keeps track of the parent of each node. Initially, each element is its own parent.rank[]: This array keeps track of the rank (or size) of each tree. It helps in deciding which tree to attach to the other during a union operation to keep the tree balanced.find(x): This method returns the root of the set containingx. It uses path compression to flatten the tree, improving the time complexity of futurefindoperations.union(x, y): This method merges the sets containingxandy. It uses union by rank to ensure that the smaller tree gets attached under the root of the larger tree.connected(x, y): This method checks ifxandyare in the same set by comparing their roots.
Time Complexity
- Find Operation: The time complexity is almost constant, specifically O(α(n)), where α is the inverse Ackermann function. For all practical purposes, this is nearly O(1).
- Union Operation: The time complexity is O(α(n)), which is also nearly constant.
Example Usage
Let's now look at a simple example where we perform union and find operations:
public class UnionFindExample {
public static void main(String[] args) {
UnionFind uf = new UnionFind(10); // Create a Union-Find with 10 elements (0 to 9)
uf.union(1, 2); // Union elements 1 and 2
uf.union(2, 3); // Union elements 2 and 3
uf.union(4, 5); // Union elements 4 and 5
uf.union(6, 7); // Union elements 6 and 7
System.out.println(uf.connected(1, 3)); // true, because 1 and 3 are connected through 2
System.out.println(uf.connected(4, 5)); // true, because 4 and 5 are in the same set
System.out.println(uf.connected(1, 4)); // false, because 1 and 4 are in different sets
System.out.println(uf.connected(6, 7)); // true, because 6 and 7 are in the same set
uf.union(3, 4); // Union elements 3 and 4, now the sets are merged
System.out.println(uf.connected(1, 4)); // true, now 1 and 4 are connected
}
}Output:
true
true
false
true
trueApplications of Union-Find
Union-Find is widely used in many applications, including:
- Cycle Detection: In an undirected graph, if two nodes are already connected and you try to union them again, you have found a cycle.
- Connected Components: Union-Find can be used to find connected components in an undirected graph.
- Kruskal’s Minimum Spanning Tree (MST) Algorithm: Union-Find helps efficiently check if two nodes are in the same component while constructing the MST.
- Network Connectivity: Union-Find can be used to manage dynamic connectivity in a network.
- Percolation Problem: It is used in simulations to model the flow of liquids through porous materials (percolation theory).
Conclusion
This cheat sheet covers the basic graph representation and common graph algorithms in Java. These algorithms are the foundation for solving various graph-related problems, from simple traversals (DFS, BFS) to more advanced algorithms like Dijkstra's, Kruskal's, Bellman-Ford, Topological Sorting, and Floyd-Warshall.
When implementing graph algorithms, ensure that the graph is represented efficiently and that you handle edge cases (like negative cycles or disconnected components) appropriately.
Comments (1)