How to do random BFS traversal in networkx?

I want to implement a BFS traversal algorithm on large graphs in a random order (has to be as fast as a normal BFS traversal).

Here is the code snippet that I have:

def perform_random_bfs(self, g, source):
    visited = set()
    queue = [source]
    random_dfs_list = [source]
    visited.add(source)
    while len(queue):
        curr = queue.pop(0)
        childs = []
        for child in g.neighbors(curr):
            if child not in visited:
                visited.add(child)
                childs.append(child)
                queue.append(child)
        random.shuffle(childs)
        [random_dfs_list.append(child) for child in childs]
    return random_dfs_list

Any ideas on speeding it up? I think random.shuffle is the bottleneck.