fork download
copy 
  1. # your code goes here
  2. # your code goes here
  3. from collections import deque
  4.  
  5. def find_reachability_bfs(graph, source):
  6.     # 'visited' keeps track of reachable nodes
  7.     visited = {node: False for node in graph}
  8.  
  9.     # Queue for BFS traversal
  10.     queue = deque([source])
  11.     visited[source] = True
  12.  
  13.     while queue:
  14.         current = queue.popleft()
  15.  
  16.         # Traverse all neighbors of the current node
  17.         for neighbor in graph[current]:
  18.             if not visited[neighbor]:
  19.                 visited[neighbor] = True
  20.                 queue.append(neighbor)
  21.  
  22.     return visited
  23.  
  24. # Example Graph (Adjacency List)
  25. graph = {
  26.     'A': ['B', 'C'],
  27.     'B': ['D'],
  28.     'C': [],
  29.     'D': [],
  30.     'E': ['F'], # 'E' and 'F' are disconnected from 'A'
  31.     'F': []
  32. }
  33.  
  34. source_node = 'A'
  35. reachability = find_reachability_bfs(graph, source_node)
  36.  
  37. # Output Results
  38. print(f"Reachability from source node '{source_node}':")
  39. for node, is_reachable in reachability.items():
  40.     print(f"Node {node}: {'Reachable' if is_reachable else 'Not Reachable'}")
Success #stdin #stdout 0.07s 14020KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Reachability from source node 'A':
Node A: Reachable
Node B: Reachable
Node C: Reachable
Node D: Reachable
Node E: Not Reachable
Node F: Not Reachable
https://ideone.com/0x3KZH
language:
Python 3 (python  3.12)
created:
4 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!