CODEWITHSUNDEEP
pythonalgorithmtime-complexitybreadth-first-search
learnermissed
learnermissed

Reputation: 11

Graph shortest-path with storing checked vertexes

I know that time complexity of shortest path via BFS is O(V+E). But I have found one of algorithm's implementations on Python which looks like this.

def search(name):
   search_queue = deque()
   search_queue += graph[name]  # graph is a dict<string: list of strings>

   searched = []
   while search_queue:
      person = search_queue.popleft()
      if person not in searched:
         if some_checking(person):
            return True
         else:
            search_queue += graph[person]
            searched.append(person)

   return False

In the outer loop we traverse through each vertex in the graph and each iteration we check whether the vertex has been already visited. Searching will take O(N) operations since searched is a list. Am I right that time complexity is O(V^2) in this implementation?

Upvotes: 0

Views: 84

Answers (1)

Marcelo Fornet
Marcelo Fornet

Reputation: 583

Yes, you are correct. Searching if the node was already visited can take up to O(V) and it is done O(V) times. This code is O(V^2).

It can be easily improved by changing the data structure used to store visited nodes. Changing from list to set, will make this code works in O(V + E).

Upvotes: 2

Related Questions