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 stepbystep 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 memoryefficient 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 PathFinding 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 DepthFirst Search (DFS) for this purpose.
DepthFirst 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: PathFinding 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
StepbyStep 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'
.
 Start DFS from

Explore from
'j'
:'j'
is not the destination. Add'j'
to thevisited
set. Explore neighbor
'i'
.

Explore from
'i'
:'i'
is not the destination. Add'i'
to thevisited
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 thevisited
set. Explore neighbors
'i'
,'m'
, and'l'
.  Skip
'i'
since it’s already visited.  Explore neighbor
'm'
.

Found Destination
'm'
:'m'
is the destination. Returntrue
.
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 depthfirst 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.
Further Reading
 Graph Representation in Data Structures
 DepthFirst Search (DFS) Algorithm
 Applications of Graph Algorithms
Happy coding and keep exploring the world of graphs!