Distance Between Two Nodes 🎯

Welcome to the fascinating world of Data Structures and Algorithms! Today, we're diving into one of the most essential concepts - the Distance Between Two Nodes. This lesson is designed to be beginner-friendly, but don't worry, we'll also provide enough depth for intermediate learners.

What are Nodes and Edges? 📝

Before we jump into the distance, let's quickly understand what nodes and edges are.

Nodes: These are the individual data items in a network, such as a graph. In the context of a linked list, nodes are the individual data elements.
Edges: These are the connections between nodes. In a graph, edges represent the relationships between different nodes, while in a linked list, edges are the links between nodes.

Understanding Graphs 🎯

For calculating the distance between two nodes, we'll be working with a type of data structure called a Graph. A graph is a collection of nodes (also called vertices) and edges (also called lines or arcs) that represent connections between those nodes.

In a graph, nodes can be connected in two ways:

Undirected Graph: The edges don't have a direction. For example, if node A is connected to node B, then node B is also connected to node A.
Directed Graph: The edges have a direction. If node A is connected to node B, it means that there is a relationship from node A to node B, but not necessarily from node B to node A.

Breadth-First Search (BFS) 💡

To find the shortest path between two nodes in an unweighted graph (a graph where edges don't have a weight or length), we'll use a technique called Breadth-First Search (BFS). BFS explores all the nodes at a given depth before moving on to the next level of nodes.

Here's a step-by-step process of BFS:

Start from the source node (the node we start our search from).
Mark the source node as visited.
Add the source node to a queue.
While the queue is not empty: a. Dequeue (remove) the first node from the queue. b. Visit the dequeued node (print its value). c. For each unvisited neighbor of the dequeued node, do the following: i. Mark the neighbor as visited. ii. Add the neighbor to the queue.

Code Example - Breadth-First Search 💡

Let's implement BFS in Python to find the shortest path between two nodes in an undirected graph:

python

# Define the graph as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

def bfs(graph, start, goal):
    visited, queue = set(), [start]
    while queue:
        current = queue.pop(0)
        if current == goal:
            print(f"Shortest path found: {[goal] + path[goal]}")
            return
        for neighbor in graph[current] - visited:
            visited.add(neighbor)
            queue.append(neighbor)
    print(f"No path found between {start} and {goal}.")

# Example usage
path = {}
bfs(graph, 'A', 'F')  # Output: Shortest path found: ['A', 'C', 'F']

In this example, we start at node 'A' and want to find the shortest path to node 'F'. The output shows that the shortest path is ['A', 'C', 'F'].

Distance Between Two Nodes 🎯

Distance Between Two Nodes 🎯

What are Nodes and Edges? 📝

Understanding Graphs 🎯

Breadth-First Search (BFS) 💡

Code Example - Breadth-First Search 💡

Quiz Time 💡