Graphs

Graphs in Java

Graphs are a fundamental data structure in Java and are widely used in Leetcode problems. A graph is a collection of nodes (vertices) connected by edges. Graphs can be directed or undirected and can have weighted or unweighted edges.

Table of Contents

1. Graph Basics
2. Graph Representations
3. Graph Traversal
4. Shortest Path Algorithms
5. Minimum Spanning Tree Algorithms
6. Disjoint-Set (Union-Find) Data Structure
7. Time and Space Complexity
8. Related Leetcode Questions

Graph Basics

1. Directed Graph

• Definition: A graph where edges have a direction, meaning they go from one vertex to another. For example, an edge from vertex A to vertex B does not imply an edge from B to A.
• Example: Social media follow relationships (if A follows B, it doesn’t mean B follows A).

2. Undirected Graph

• Definition: A graph where edges have no direction, meaning they are bidirectional. For example, an edge between vertex A and vertex B implies a connection from A to B and from B to A.
• Example: Facebook friendships (if A is friends with B, then B is also friends with A).

3. Weighted Graph

• Definition: A graph where edges have weights or costs associated with them. These weights can represent distances, costs, or any other metric.
• Example: Road networks where edges represent roads and weights represent distances or travel times.

4. Unweighted Graph

• Definition: A graph where edges have no weights or costs associated with them.
• Example: Social networks where edges represent connections without any associated cost.

Graph Representations

1. Adjacency Matrix

• Definition: A 2D array where matrix[i][j] represents the edge between vertex i and vertex j. For weighted graphs, matrix[i][j] stores the weight of the edge.
• Example:

  int[][] adjMatrix = {
      {0, 1, 0},
      {1, 0, 1},
      {0, 1, 0}
  };

• Time Complexity:
  • Check if there is an edge between two vertices: O(1)
  • Find all edges from a vertex: O(V) (where V is the number of vertices)
• Space Complexity: O(V^2)

2. Adjacency List

• Definition: An array of lists where each list stores the neighbors of a vertex. For weighted graphs, each list stores pairs of neighbors and their corresponding weights.
• Example:

  List<List<Integer>> adjList = new ArrayList<>();
  adjList.add(Arrays.asList(1));
  adjList.add(Arrays.asList(0, 2));
  adjList.add(Arrays.asList(1));

• Time Complexity:
  • Check if there is an edge between two vertices: O(V)
  • Find all edges from a vertex: O(1)
• Space Complexity: O(V + E) (where E is the number of edges)

Graph Traversal

1. Depth-First Search (DFS)

• Algorithm: Explore as far as possible along each branch before backtracking.
• Example:

  public void dfs(int node, boolean[] visited, List<List<Integer>> adjList) {
      visited[node] = true;
      System.out.println(node);
      for (int neighbor : adjList.get(node)) {
          if (!visited[neighbor]) {
              dfs(neighbor, visited, adjList);
          }
      }
  }

• Time Complexity: O(V + E)
• Space Complexity: O(V)

2. Breadth-First Search (BFS)

• Algorithm: Explore all neighbors at the present depth before moving on to nodes at the next depth level.
• Example:

  public void bfs(int start, List<List<Integer>> adjList) {
      boolean[] visited = new boolean[adjList.size()];
      Queue<Integer> queue = new LinkedList<>();
      queue.add(start);
      visited[start] = true;
      while (!queue.isEmpty()) {
          int node = queue.poll();
          System.out.println(node);
          for (int neighbor : adjList.get(node)) {
              if (!visited[neighbor]) {
                  visited[neighbor] = true;
                  queue.add(neighbor);
              }
          }
      }
  }

• Time Complexity: O(V + E)
• Space Complexity: O(V)

Shortest Path Algorithms

1. Dijkstra’s Algorithm

• Algorithm: Finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights. It uses a priority queue to greedily select the vertex with the smallest distance.
• Example:

  public int[] dijkstra(int[][] graph, int src) {
      int V = graph.length;
      int[] dist = new int[V];
      Arrays.fill(dist, Integer.MAX_VALUE);
      dist[src] = 0;
      PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
      pq.add(new int[]{src, 0});
      while (!pq.isEmpty()) {
          int[] current = pq.poll();
          int u = current[0];
          for (int v = 0; v < V; v++) {
              if (graph[u][v] != 0 && dist[u] + graph[u][v] < dist[v]) {
                  dist[v] = dist[u] + graph[u][v];
                  pq.add(new int[]{v, dist[v]});
              }
          }
      }
      return dist;
  }

• Time Complexity: O((V + E) log V)
• Space Complexity: O(V)

2. Bellman-Ford Algorithm

• Algorithm: Finds the shortest path from a source vertex to all other vertices in a weighted graph, even with negative weights (but no negative weight cycles). It relaxes all edges V-1 times.
• Example:

  public int[] bellmanFord(int[][] edges, int V, int src) {
      int[] dist = new int[V];
      Arrays.fill(dist, Integer.MAX_VALUE);
      dist[src] = 0;
      for (int i = 1; i < V; i++) {
          for (int[] edge : edges) {
              int u = edge[0], v = edge[1], w = edge[2];
              if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
                  dist[v] = dist[u] + w;
              }
          }
      }
      return dist;
  }

• Time Complexity: O(V * E)
• Space Complexity: O(V)

Minimum Spanning Tree Algorithms

1. Minimum Spanning Tree (MST)

• Definition: A subset of edges in a weighted undirected graph that connects all vertices without cycles and with the minimum possible total edge weight.

2. Prim’s Algorithm

• Algorithm: Grows the MST by adding the smallest edge connecting a vertex in the MST to a vertex outside the MST.
• Example:

  public int primMST(int[][] graph) {
      int V = graph.length;
      int[] parent = new int[V];
      int[] key = new int[V];
      boolean[] mstSet = new boolean[V];
      Arrays.fill(key, Integer.MAX_VALUE);
      key[0] = 0;
      parent[0] = -1;
      for (int count = 0; count < V - 1; count++) {
          int u = minKey(key, mstSet);
          mstSet[u] = true;
          for (int v = 0; v < V; v++) {
              if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                  parent[v] = u;
                  key[v] = graph[u][v];
              }
          }
      }
      int totalWeight = 0;
      for (int i = 1; i < V; i++) {
          totalWeight += graph[parent[i]][i];
      }
      return totalWeight;
  }
  private int minKey(int[] key, boolean[] mstSet) {
      int min = Integer.MAX_VALUE, minIndex = -1;
      for (int v = 0; v < key.length; v++) {
          if (!mstSet[v] && key[v] < min) {
              min = key[v];
              minIndex = v;
          }
      }
      return minIndex;
  }

• Time Complexity: O(V^2) (can be improved to O((V + E) log V) with a priority queue)
• Space Complexity: O(V)

3. Kruskal’s Algorithm

• Algorithm: Grows the MST by adding the smallest edge that doesn’t form a cycle, using a disjoint-set (Union-Find) data structure to detect cycles.
• Example:

  public int kruskalMST(int[][] edges, int V) {
      Arrays.sort(edges, (a, b) -> a[2] - b[2]);
      int[] parent = new int[V];
      Arrays.fill(parent, -1);
      int totalWeight = 0;
      for (int[] edge : edges) {
          int u = edge[0], v = edge[1], w = edge[2];
          int setU = find(parent, u);
          int setV = find(parent, v);
          if (setU != setV) {
              totalWeight += w;
              union(parent, setU, setV);
          }
      }
      return totalWeight;
  }
  private int find(int[] parent, int i) {
      if (parent[i] == -1) {
          return i;
      }
      return find(parent, parent[i]);
  }
  private void union(int[] parent, int x, int y) {
      int setX = find(parent, x);
      int setY = find(parent, y);
      parent[setX] = setY;
  }

• Time Complexity: O(E log E) or O(E log V)
• Space Complexity: O(V)

Disjoint-Set (Union-Find) Data Structure

1. Definition

• A data structure that keeps track of a partition of a set into disjoint subsets. It supports two operations:
  • Find: Determine which subset a particular element is in.
  • Union: Join two subsets into a single subset.

2. Example

• Used in Kruskal’s Algorithm to detect cycles by checking if two vertices belong to the same subset.

Time and Space Complexity

Algorithm	Time Complexity	Space Complexity
DFS	O(V + E)	O(V)
BFS	O(V + E)	O(V)
Dijkstra’s Algorithm	O((V + E) log V)	O(V)
Bellman-Ford Algorithm	O(V * E)	O(V)
Prim’s Algorithm	O(V^2)	O(V)
Kruskal’s Algorithm	O(E log E)	O(V)

Related Leetcode Questions

Easy

1. Number of Islands
2. Flood Fill
3. Find the Town Judge

Medium

1. Clone Graph
2. Course Schedule
3. Network Delay Time

Hard

1. Word Ladder
2. Cheapest Flights Within K Stops
3. Minimum Cost to Connect All Points