Untitled

graph = [[1], [2, 3], [1, 4, 5], [1, 6], [2], [2], [3, 7, 8], [6], [6]]


# Find distances from start vertex to all vertexes
def bfs(graph, start_vertex):
    visited = [False for x in graph]
    distances = [0 for x in graph]
    vertex_to_visit_queue = [start_vertex]

    while vertex_to_visit_queue:
        current_vertex = vertex_to_visit_queue.pop(0)
        for neighbour in graph[current_vertex]:
            if not visited[neighbour]:
                vertex_to_visit_queue.append(neighbour)
                distances[neighbour] = distances[current_vertex] + 1

        visited[current_vertex] = True

    return distances


print(bfs(graph, 0))


# Find distance from start vertex to end vertex
def dfs(graph, start_vertex, end_vertex):
    visited = [False for x in graph]
    distances = [0 for x in graph]
    vertex_to_visit_stack = [start_vertex]

    while vertex_to_visit_stack:
        current_vertex = vertex_to_visit_stack.pop()
        if current_vertex == end_vertex:
            return distances[current_vertex]
        for neighbour in graph[current_vertex]:
            if not visited[neighbour]:
                vertex_to_visit_stack.append(neighbour)
                distances[neighbour] = distances[current_vertex] + 1

        visited[current_vertex] = True

    return None


print(dfs(graph, 0, 3))