Find the shortest path in an unweighted graph

find_shortest_path_unweight.py

from collections import deque
# graph is represented by adjacency list: List[List[int]]
# s: start vertex
# d: destination vertex
# based on BFS
def find_shortest_path(graph, s, d):
    # pred[i] stores predecessor of i in the path
    pred = [-1] * len(graph)
    # set is used to mark visited vertices
    visited = set()
    # create a queue for BFS
    queue = deque()
    # Mark the start vertex as visited and enqueue it
    visited.add(s)
    queue.appendleft(s)

    while queue:
        current_vertex = queue.pop()
        # Get all adjacent vertices of current_vertex
        # If a adjacent has not been visited, then mark it
        # visited and enqueue it
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.appendleft(v)
                # record the predecessor
                pred[v] = current_vertex
                # reach to the destination
                if v == d:
                    break

    # no path to d
    if pred[d] == -1:
        return []
    # retrieve the path
    path = [d]
    current = d
    while pred[current] != -1:
        current = pred[current]
        path.append(current)

    return path[::-1]