Data Structures BFS Breadth First Search algorithm improvement written in python
The very first thing that caught my eye was the del queue[0] which is a \$O(n)\$ operation since it requires for the whole list to be moved.

There is a quick win here - use collections.deque() which has a .popleft() method operating at \$O(1)\$:

queue = deque([node])

while queue:
    node = queue.popleft()

    for i in self.graph[node]:
        if visited[i] is None:
            queue.append(i)

            visited[i] = True
            distance[i] = distance[node] + 1
            parent[i] = node


where deque is imported this way:

from collections import deque


Also note the use of while queue: instead of a less efficient and less readable while len(queue) != 0:.



There is a number of code style issues as well:


look for the PEP8 violations, in particular:


class name should start with a capital letter - Graph instead of graph

use proper documentation strings instead of regular comments before the method definitions


watch for the spaces around operators and the use of blank lines

_ (underscore) variable name is agreed to be used a throwaway variable name, e.g.:

self.graph = [[] for _ in range(n)]


instead of:

self.graph = [[] for y in range(n)]