CODEWITHSUNDEEP
pythonalgorithmgraph
theusual
theusual

Reputation: 791

Python (DFS): Please explain this clearly to me: stack.extend(graph[vertex] - visited)

I am new to Python and decided to practice algorithms to gain a strong foundation. I am having difficulty understanding this particular line in the code that implements DFS: stack.extend(graph[vertex] - visited). Does it mean that graph[vertex] contains all the vertices present in the graph and this line removes the most recently visited vertex, and returns the remaining unvisited list of vertices in the graph? Please find source of code here under connected component. Thanks!!

Upvotes: 0

Views: 529

Answers (1)

mysl
mysl

Reputation: 1053

I'll paste in the code in your link for all to see:

def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

What's happening in this code:

With the given vertex called start, we are adding all of its adjacent vertices, represented by graph[vertex], in order to check if we have already traveled to that vertex. If not, we need to add that vertex to the set called visited and extend stack with all of its adjacent vertices. Next, we pop an element from the now-extended stack and go through the same process of checking until there are no more elements remaining.

Answer to the question:

I suspect that the - visited portion of stack.extend(graph[vertex] - visited) might have thrown you off. Here, - visited does not affect the functionality of the code but it helps in optimizing the code. This is only to prevent double-checking of the vertices that we have already visited, thus subtracting visited from graph[vertex]. Lastly, I'd note that graph should be a dictionary of sets (not lists) for the subtraction to work without throwing an error.

Upvotes: 1

Related Questions