Graph

This page provides introduction to graph data structure.

Overview

A graph is a collection of nodes connected by edges that represent relationships between entities. Graphs can be directed or undirected, and may be weighted or unweighted.

Build Graph

A graph can be represented as an adjacency matrix or as a adjacency list.

Use an adjacency matrix when dealing with a dense graph, where the number of edges is large compared to the number of vertices, as it allows for quick edge lookups in constant time $\text{O(1)}$.

On the other hand, an adjacency list is more efficient for sparse graphs, where there are fewer edges relative to the number of vertices. It saves space by only storing existing edges and allows efficient traversal of neighbors.

Let's build an adjacency matrix for an undirected weighted graph below.

Java

int[][] graph = new int[][]{
  // adding edge and weight from node 0
  {0, 5, 0, 9, 0, 2},

  // adding edge and weight from node 1
  {5, 0, 2, 0, 0, 0},

  // adding edge and weight from node 2
  {0, 2, 0, 3, 0, 0},

  // adding edge and weight from node 3
  {9, 0, 3, 0, 2, 0},

  // adding edge and weight from node 4
  {0, 0, 0, 2, 0, 3},

  // adding edge and weight from node 5
  {2, 0, 0, 0, 3, 0}
}

Now, let's build the adjacency list for the same graph. We will begin by defining a toNode class.

Java

class ToNode {
  int node;
  int weight;
}

HashMap<Integer, List<ToNode>> graph = new HashMap<>();

// adding edges & weight from node 0
map.put(0, new ArrayList<>(
  new ToNode(1, 5),
  new ToNode(3, 9),
  new ToNode(5, 2),
));

// adding edges & weight from node 1
map.put(1, new ArrayList<>(
  new ToNode(0, 5),
  new ToNode(2, 2),
));


// adding edges & weight from node 2
map.put(2, new ArrayList<>(
  new ToNode(1, 2),
  new ToNode(3, 3)
));


// adding edges & weight from node 3
map.put(3, new ArrayList<>(
  new ToNode(2, 3),
  new ToNode(4, 2)
));


// adding edges & weight from node 4
map.put(4, new ArrayList<>(
  new ToNode(3, 2),
  new ToNode(5, 3)
));


// adding edges & weight from node 5
map.put(5, new ArrayList<>(
  new ToNode(0, 2),
  new ToNode(4, 3)
));

Graph Traversals

There are $2$ types of graph traversals:

• Depth First Search(DFS): It is ideal for exploring deep paths and performing tasks like topological sorting or component finding.

Java

public void dfs() {
  helper(0, new boolean[6]);
}

public void helper(int node, boolean[] visited) {
  visited[node] = true;
  System.out.print(node+" ");
  for(ToNode toNode: graph.getOrDefault(node, new ArrayList<>())) {
    if(visited[toNode.node]) continue;
    helper(toNode.node, visited);
  }
}

• Breadth First Search(BFS): It is best for finding shortest paths in unweighted graphs and when exploring a graph level by level.

Java

public void bfs() {
  boolean[] visited = new boolean[6];
  Queue<Integer> q = new LinkedList<>();

  visited[0] = true;
  q.add(0);
  while(!q.isEmpty()) {
    int node = q.poll();
    System.out.println(node+" ");
    for(ToNode toNode: graph.getOrDefault(node, new ArrayList<>())) {
      if(visited[toNode.node]) continue;
      q.offer(toNode.node);
    }
  }
  System.out.println();
}

Complexity

Let's say there are $\text{V}$ nodes and $\text{E}$ edges.

Time Complexity

In both DFS and BFS traversals, each vertex is visited once, and each edge is traversed once while visiting its adjacent vertices. Therefore, the time complexity is:

$$\text{O(V + E)}$$

Space Complexity

DFS requires space to store a visited array as well as the recursion stack. In the worst case, the recursion stack will need space for every vertex if the graph is linear.

BFS requires space to store a visited array and a queue. In the worst case, the queue will need space for every vertex if the graph has a high fanout from a single node.

$$\text{O(V)}$$

How to Spot These Problems

You can identify graph problems:

• If the problem asks you to model relationships or connections between entities, such as social networks, roadmaps, or dependencies.
• When you notice inefficiencies in operations like traversals, shortest path computations, or connectivity checks.
• If the problem involves cycles, paths, or connected components, as these are common graph-related concerns.
• If the solution requires optimization, such as finding the minimal spanning tree or the shortest path in a weighted graph.

Leetcode Problem Set