breadth first search shortest reach

                                            
def bfs(n, m, edges, s):
    
    g = [[] for i in range(n+1)]
    for x, y in edges:
        g[x].append(y)
        g[y].append(x)
        
    visited = [False] * (n+1)
    visited[s] = True
    distances = [-1] * (n+1)
    distances[s] = 0
    q = deque([(s, 0)])
    
    while q:
        
        u, w = q.popleft()
        for v in g[u]:
            
            if visited[v] == False:
                distances[v] = w+6
                visited[v] = True
                q.append((v, w+6))
                
    distances.remove(0)
    
    return distances[1:]
    
    
print(bfs(4, 2, [[1, 2], [1, 3]], 1)) # 6 6 -1
print(bfs(3, 1, [[2, 3]], 2)) # -1 6

To solve this coding challenge, we will employ the Breadth-First Search (BFS) algorithm. This approach is ideal for finding the shortest path in an unweighted graph, which aligns perfectly with the problem constraints since all edges weigh the same (6 units). Below is a detailed explanation of how we can solve this challenge.

Explanation

Overview

In this problem, you are required to:

Represent an undirected graph using the given edges.
Perform BFS starting from the given node to calculate the shortest distance to all other nodes.
Return a distance list where each entry represents the shortest distance from the start node to other nodes, and -1 if a node is unreachable.

Steps to Solve the Problem

Graph Representation : We'll use an adjacency list to represent the graph. Each node will have a list of connected nodes.
Initialize BFS Variables : We'll need a queue to keep track of the nodes to be visited, an array to keep track of the distances, and a boolean array to mark nodes as visited.
BFS Traversal : We'll start the traversal from the given start node and follow these steps:

Dequeue a node.
For each adjacent node, if it hasn’t been visited, mark it as visited, update its distance, and enqueue it.

Result Preparation : After completing the BFS, prepare the result array by excluding the distance to the starting node itself.

Step-by-Step Explanation

Graph Representation :

We'll create a graph using an adjacency list by iterating over the list of edges. Each edge connects two nodes, and since the graph is undirected, both nodes should reference each other.

Initializations :

distances

: Array to store distances initialized to -1 (indicating unreachable nodes).
queue

: A queue to handle the BFS front.
visited

: Array to mark nodes as visited, initialized to False for all nodes.

BFS Execution :

Start by marking the source node as visited with a distance of 0 and enqueue it.
For each node dequeued, examine its neighbors:

If a neighbor node hasn’t been visited, mark it as visited, set its distance to the current node’s distance plus the edge weight (6), and enqueue the neighbor node.

Result Formation :

After BFS, distances to the start node will be 0. Remove this entry and return the distances of other nodes.

Detailed Steps in Pseudocode

                                            
# Function to perform BFS and find the shortest paths
FUNCTION bfs(num_nodes, num_edges, edges, start_node):
    # Initialize the graph as an adjacency list
    graph = CREATE_LIST(num_nodes + 1, empty_list)
    
    # Populate the graph with given edges
    FOR each edge in edges:
        node1 = edge[0]
        node2 = edge[1]
        ADD node2 to graph[node1]
        ADD node1 to graph[node2]
    
    # Initialize distances and visited arrays
    distances = CREATE_LIST(num_nodes + 1, -1)
    visited = CREATE_LIST(num_nodes + 1, False)
    
    # BFS setup
    distances[start_node] = 0  # Starting node has distance 0
    queue = EMPTY_QUEUE()
    ENQUEUE queue, start_node
    
    # Perform BFS
    WHILE queue is not empty:
        current_node = DEQUEUE(queue)
        FOR each neighbor in graph[current_node]:
            IF NOT visited[neighbor]:
                visited[neighbor] = True
                distances[neighbor] = distances[current_node] + 6
                ENQUEUE queue, neighbor
    
    # Form result array excluding the start node
    result = EMPTY_LIST()
    FOR node IN RANGE(1, num_nodes + 1):
        IF node IS NOT start_node:
            APPEND result, distances[node]
    
    RETURN result

# Example Usage and Test Cases
PRINT bfs(4, 2, [[1, 2], [1, 3]], 1)  # Output: [6, 6, -1]
PRINT bfs(3, 1, [[2, 3]], 2)           # Output: [-1, 6]

Explanation of Pseudocode Comments

Graph Initialization : This starts by creating an adjacency list for the graph, capturing the connectivity between nodes.
Distance and Visited Arrays : These help in tracking whether a node has been visited and the shortest distances computed from the start node.
BFS Loop : This loop processes each node, exploring its neighbors, marking them as visited if they haven't been already, updating their shortest distances, and enqueuing them for further processing.
Result Preparation : This collects and returns distances for all nodes except the starting node, ensuring a streamlined output format.

This detailed approach ensures all the problem constraints and requirements are met effectively, utilizing the BFS algorithm for optimal performance in traversing and measuring distances in an unweighted graph scenario.