dfs python code using stack

dfs python code using stack

Here is an example of a DFS (Depth-First Search) algorithm implemented in Python using a stack:

class Graph:
def init(self, vertices):
self.V = vertices
self.graph = [[0 for i in range(vertices)]
[for j in range(vertices)]]
Function to print the traversal
def print_graph(self):
for i in range(self.V):
for j in range(self.V):
print(self.graph[i][j], end=' ')
print()
Function for DFS traversal
def DFS(self, s):
visited = [False] * self.V
stack = []
stack.append(s)
visited[s] = True
while stack:
v = stack.pop()
print(v, end=' ')
for i in range(self.V):
if self.graph[v][i] == 1 and visited[i] == False:
stack.append(i)
visited[i] = True
print()
Driver code
g = Graph(4)
g.graph = [[1, 1, 0, 1],
[1, 1, 1, 1],
[0, 1, 1, 0],
[1, 1, 0, 1]]
print("Depth-First Traversal is: ")
g.DFS(0)

Explanation:

This code represents a graph using an adjacency matrix. The Graph class initializes the graph with a specified number of vertices (V) and sets up the adjacency matrix to represent the edges between vertices.

The DFS method implements the depth-first search algorithm, starting from a given vertex s. It uses a stack data structure to keep track of visited vertices.

Here's how it works:

In this example code, we create a graph with four vertices (0 to 3) and edges represented by the adjacency matrix. The DFS method starts from vertex 0 and traverses the graph depth-first, printing the visited vertices as it goes.

Python depth first search example

I'm happy to help with a Python Depth-First Search (DFS) example. Here's an explanation and code:

What is Depth-First Search (DFS)?

Depth-First Search is a graph traversal algorithm that starts at the root node (the first vertex in the graph) and explores the graph as deeply as possible before backtracking. The process continues until all vertices have been visited or a predetermined stopping condition is met.

In other words, DFS traverses the graph by visiting a node, then exploring all of its neighbors, and so on, without returning to previous nodes until it has explored all reachable nodes.

Python Implementation:

Here's an example implementation in Python:

class Graph:
def init(self):
self.graph = {}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
if v not in self.graph:
self.graph[v] = []
self.graph[u].append(v)
def dfs(self, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(f"Visiting node {start}")
for neighbor in self.graph.get(start, []):
if neighbor not in visited:
self.dfs(neighbor, visited)
Example usage
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "E")
g.dfs("A")  # Output: Visiting node A, Visiting node B, Visiting node D, Visiting node C, Visiting node E

In this example:

The DFS algorithm works by:

Why DFS is useful:

DFS has many applications in computer science and real-life scenarios:

Conclusion:

This Python example illustrates the concept of Depth-First Search and its implementation using recursion. By understanding how DFS works, you can apply this algorithmic technique to various graph-related problems in your programming endeavors.

If you have any questions or need further clarification, feel free to ask!