Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Graph Traversal - Depth First Search(DFS)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

Please correct the algorithm for DFS. This is sooooooo wrong.

A

Anonymous

· 2 years ago

Wrong stack representation

Why can't F go to C as its neighbor.

Please correct / issue refund.

Show 1 reply
A

Anonymous

· 3 years ago

class Graph:
    def __init__(self, V):
        self.vertices = V
        self.adjList = [[] for _ in range(V)]

    def addEdge(self, u, v):
        self.adjList[u].append(v)
        self.adjList[v].append(u)  # For an undirected graph

    def DFS(self, start):
        visited = [False] * self.vertices
        stack = []

        stack.append(start)
        visited[start] = True

        while stack:
            curr = stack.pop()
            print(curr)

            for neighbor in self.adjList[curr]:
                if not visited[neighbor]:
                    stack.append(neighbor)
                    visited[neighbor] = True

# g = Graph(7)

# g.addEdge(0, 1)
# g.addEdge(0, 2)
# g.addEdge(1, 3)
# g.addEdge(1, 4)
# g.addEdge(2, 5)
# g.addEdge(2, 6)

# Example that would go
A

Anonymous

· 3 years ago

Both Step-by-step illustrations of DFS on this page have issues.

For the first graph, containing the vertices [0, 1, 2, 3, 4], the visual representation of the stack behaves like a queue.

When vertex 0 is visited, vertices [1, 2, 3] are pushed onto the stack. On the next turn, vertex 1 is "popped" from the stack and moved to the visited list. The visual representation looks like a queue, where the item with index 0 is popped. It effectively looks like vertex 1 was removed using popleft() instead of pop().

A proper visual representation of the stack would pop vertex 3, since it is the furthest-to-the-right element in the stack. For this entire course queues and stacks have been read from left-to-right.

The graph of the tree-like structure with vertices `[A, B, C, D, E,

Reading Progress

0%

Vote for new content