Find top-k rated nodes via traversal

You are given a finite graph (directed or undirected) with n nodes and m edges. Each node u has an integer rating r[u]. Given a starting node s and an integer k, return the top k distinct nodes (excluding s only if specified) reachable from s by traversing edges. Break ties by smaller node ID. The graph may contain cycles. Design and implement an algorithm that: (a) visits each reachable node at most once (e.g., via BFS/DFS), (b) maintains the current top k efficiently during traversal, and (c) outputs nodes in descending rating order. Analyze time and space complexity, justify your data-structure choices (e.g., visited set and a size-k heap), and discuss how your solution changes if k is close to the number of reachable nodes, if ratings can change during traversal, or if the graph is too large to fit in memory.