fork download
copy 
  1. # your code goes here
  2. from collections import deque
  3.  
  4. def find_reachability_bfs(graph, source):
  5.     # 'visited' keeps track of reachable nodes
  6.     visited = {node: False for node in graph}
  7.  
  8.     # Queue for BFS traversal
  9.     queue = deque([source])
  10.     visited[source] = True
  11.  
  12.     while queue:
  13.         current = queue.popleft()
  14.  
  15.         # Traverse all neighbors of the current node
  16.         for neighbor in graph[current]:
  17.             if not visited[neighbor]:
  18.                 visited[neighbor] = True
  19.                 queue.append(neighbor)
  20.  
  21.     return visited
  22.  
  23. # Example Graph (Adjacency List)
  24. graph = {
  25.     'A': ['B', 'C'],
  26.     'B': ['D'],
  27.     'C': [],
  28.     'D': [],
  29.     'E': ['F'], # 'E' and 'F' are disconnected from 'A'
  30.     'F': []
  31. }
  32.  
  33. source_node = 'A'
  34. reachability = find_reachability_bfs(graph, source_node)
  35.  
  36. # Output Results
  37. print(f"Reachability from source node '{source_node}':")
  38. for node, is_reachable in reachability.items():
  39.     print(f"Node {node}: {'Reachable' if is_reachable else 'Not Reachable'}")
Success #stdin #stdout 0.08s 14096KB
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/xpUC0k
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!