Finding path in an undirected graph

bysantosh •سبتمبر 06, 2021

0

Graph problems are an essential part of computer science and programming, particularly in areas like network analysis, social network dynamics, and pathfinding. One common problem in graph theory is determining if there is a path between two nodes in an undirected graph.

In this blog post, we’ll solve this problem step-by-step by first building an adjacency list from the input edges and then implementing a function to determine if there is a path between two nodes.

Problem Statement

Given an undirected graph represented by a list of edges and two nodes (source and destination), determine if there is a path between the source and destination nodes.

Example

Consider the following undirected graph represented as a list of edges:

const edges = [
  ['i', 'j'],
  ['k', 'i'],
  ['m', 'k'],
  ['k', 'l'],
  ['o', 'n']
];

We want to determine if there is a path from node 'j' to node 'm'. The answer is true because there exists a path: j -> i -> k -> m.

Step 1: Build the Adjacency List

An adjacency list is a common way to represent a graph, where each node points to a list of its neighbors. This representation is memory-efficient for sparse graphs (graphs with relatively few edges).

To convert the edge list to an adjacency list:

Initialize an empty adjacency list (e.g., a JavaScript object).
Loop through each edge and add each node’s neighbors to the adjacency list.
Since the graph is undirected, ensure that each edge is added bidirectionally.

Code: Building the Adjacency List


const buildGraph = (edges) => {
  const graph = {};

  for (let [a, b] of edges) {
    if (!graph[a]) graph[a] = []; // Initialize if not already present
    if (!graph[b]) graph[b] = [];
    graph[a].push(b); // Add b as a neighbor to a
    graph[b].push(a); // Add a as a neighbor to b (because undirected)
  }

  return graph;
};

// Example Usage
const edges = [
  ['i', 'j'],
  ['k', 'i'],
  ['m', 'k'],
  ['k', 'l'],
  ['o', 'n']
];

const graph = buildGraph(edges);
console.log(graph);
/*
Output:
{
  i: ['j', 'k'],
  j: ['i'],
  k: ['i', 'm', 'l'],
  m: ['k'],
  l: ['k'],
  o: ['n'],
  n: ['o']
}
*/

Step 2: Implement the Path-Finding Algorithm

Now that we have our adjacency list, we can proceed to implement the function to check if there is a path between two nodes. We’ll use Depth-First Search (DFS) for this purpose.

Depth-First Search (DFS) explores as far as possible along a branch before backtracking. For our undirected graph, DFS is ideal because it explores all possible paths, ensuring we don’t miss any potential connections.

DFS Approach

Recursive Function: Implement a recursive DFS function to explore the graph.
Base Case: If the current node is the destination, return true.
Visited Set: Maintain a visited set to avoid revisiting nodes, which could lead to infinite loops.
Explore Neighbors: Recursively explore each neighbor that has not been visited.
No Path Found: If all neighbors are explored and no path is found, return false.

Code: Path-Finding with DFS


const undirectedPath = (edges, src, dst) => {
  const graph = buildGraph(edges); // Step 1: Build the adjacency list
  return hasPath(graph, src, dst, new Set()); // Step 2: Use DFS to find the path
};

const hasPath = (graph, src, dst, visited) => {
  if (src === dst) return true; // Base case: if src is the destination
  if (visited.has(src)) return false; // Already visited, avoid cycles

  visited.add(src); // Mark the current node as visited

  for (let neighbor of graph[src]) { // Explore all neighbors
    if (hasPath(graph, neighbor, dst, visited) === true) {
      return true;
    }
  }

  return false; // If no path found
};

// Example Usage
const edges = [
  ['i', 'j'],
  ['k', 'i'],
  ['m', 'k'],
  ['k', 'l'],
  ['o', 'n']
];

console.log(undirectedPath(edges, 'j', 'm')); // Output: true
console.log(undirectedPath(edges, 'o', 'm')); // Output: false

Step-by-Step Breakdown

To understand the flow of the undirectedPath function, let’s go through an example for undirectedPath(edges, 'j', 'm'):

Build the Graph:
- The adjacency list is created from the edges.
- 'j' connects to 'i'.
- 'i' connects to 'j' and 'k'.
- 'k' connects to 'i', 'm', and 'l', and so on.
Initialize DFS:
- Start DFS from 'j' to find 'm'.
Explore from 'j':
- 'j' is not the destination. Add 'j' to the visited set.
- Explore neighbor 'i'.
Explore from 'i':
- 'i' is not the destination. Add 'i' to the visited set.
- Explore neighbors 'j' and 'k'.
- Skip 'j' since it’s already visited.
- Explore neighbor 'k'.
Explore from 'k':
- 'k' is not the destination. Add 'k' to the visited set.
- Explore neighbors 'i', 'm', and 'l'.
- Skip 'i' since it’s already visited.
- Explore neighbor 'm'.
Found Destination 'm':
- 'm' is the destination. Return true.

Conclusion

In this blog post, we explored how to solve the problem of finding a path between two nodes in an undirected graph. The solution involves two main steps:

Building the adjacency list: This converts the edge list into a more usable graph representation.
Implementing DFS: A recursive depth-first search that explores all possible paths while avoiding cycles using a visited set.

Key Takeaways

Graph Representation: Understanding different ways to represent graphs (adjacency list, adjacency matrix, edge list) is crucial.
DFS for Pathfinding: DFS is effective for exploring all possible paths in a graph and is particularly useful for problems involving connectivity.