Reachability

Reachability refers to determining if there exists a path from one vertex to another in a graph. This allows answering connectivity queries.

Some key algorithms for testing reachability from u to v:

  • Depth/breadth-first search
  • Computing strongly connected components
  • Finding transitive closure

Java - DFS:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

boolean reachableDFS(Graph graph, int u, int v) {
  boolean[] visited = new boolean[graph.V];
  visited[u] = true;

  Stack<Integer> stack = new Stack();
  stack.push(u);

  while (!stack.isEmpty()) {
    int curr = stack.pop();
    if (curr == v) return true;

    for (int neighbor : graph.adjList[curr]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        stack.push(neighbor);
      } 
    }
  }

  return false;
}

C++ - Flood fill:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

bool reachableBFS(Graph graph, int src, int dest) {
  vector<bool> visited(graph.V, false);
  visited[src] = true;
  
  queue<int> q; 
  q.push(src);

  while (!q.empty()) {
    int u = q.front(); q.pop();
    if (u == dest) return true;
    
    for (int v : graph.adjList[u]) {
      if (!visited[v]) {
        visited[v] = true;
        q.push(v);
      }
    }
  }

  return false; 
}

Python - Transitive closure:

1
2
3

def reachable(graph, src, dest):
  trans_closure = FloydWarshall(graph) 
  return trans_closure[src][dest]

Checking reachability has applications in routing, connectivity, and graph problems.

In graph theory, reachability refers to the ability to get from one vertex to another within a directed or undirected graph. Essentially, vertex ( v ) is reachable from vertex ( u ) if there exists a path between ( u ) and ( v ).

Algorithm

  1. Initialization: Start from a source vertex.
  2. Traversal: Use a traversal algorithm like Depth First Search (DFS) or Breadth First Search (BFS) to explore the graph.
  3. Check: For each vertex, check if it was visited during the traversal.

Java Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.ArrayList;
import java.util.Arrays;

public class Reachability {
    static boolean[] visited;
  
    public static void DFS(ArrayList<ArrayList<Integer>> graph, int vertex) {
        visited[vertex] = true;

        for (int neighbor : graph.get(vertex)) {
            if (!visited[neighbor]) {
                DFS(graph, neighbor);
            }
        }
    }
}

C++ Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <vector>
#include <iostream>

std::vector<bool> visited;

void DFS(std::vector<std::vector<int>> &graph, int vertex) {
    visited[vertex] = true;
  
    for (int neighbor : graph[vertex]) {
        if (!visited[neighbor]) {
            DFS(graph, neighbor);
        }
    }
}

Python Code:

1
2
3
4
5
6
7
8

visited = []

def DFS(graph, vertex):
    visited[vertex] = True
    
    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            DFS(graph, neighbor)

To check reachability, initialize the visited array as false for all vertices. Run DFS(graph, startVertex) and then check the visited array. If visited[targetVertex] is true, then targetVertex is reachable from startVertex.

The time complexity for this approach is ( O(V + E) ) where ( V ) is the number of vertices and ( E ) is the number of edges.