Random Walk Sampling Node

Problem

Simulate a simple random walk on an undirected graph and return the visited sequence.

Start at start, and at each step move to a uniformly random neighbor chosen from the sorted neighbor list using the seeded generator. If the current node has no neighbors the walk stops. Return the visited nodes including the start. edges is a list of [u, v] pairs.

Hint

Sorting the neighbor list before choosing keeps results stable across Python versions.

Test cases

case 1

in: [4,[[0,1],[1,2],[2,3]],0,4,42]

expected: [0,1,0,1,0]

case 2

in: [3,[[0,1],[1,2],[2,0]],1,5,7]

expected: [1,2,0,2,0,1]

case 3

in: [2,[],1,3,1]

expected: [1]

Starter codePython

import random
def random_walk_sampling_node(n, edges, start, steps, seed):
    # Your code here
    pass

3 test cases · run your code against them in the editor