Depth First Search (DFS):

Mehmet Akif Cifci
2 min readFeb 14, 2023

--

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It works by visiting a vertex (or node) and recursively visiting its adjacent unvisited vertices. The algorithm continues until all the vertices have been visited.

There are two common ways to implement DFS: using recursion or using a stack. The recursive approach is more intuitive and is often easier to implement, while the stack-based approach can be more efficient and is sometimes preferred for very large graphs. Depth-first search is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Here’s the Python code:

class Node:
def __init__(self, name):
self.name = name
self.adjacent = []
self.visited = False

# Recursive DFS function
def dfs(node):
node.visited = True
print(node.name)

for neighbor in node.adjacent:
if not neighbor.visited:
dfs(neighbor)

# Create a graph
node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
node5 = Node("E")
node6 = Node("F")
node7 = Node("G")


node1.adjacent.append(node2)
node1.adjacent.append(node3)
node2.adjacent.append(node4)
node2.adjacent.append(node5)
node3.adjacent.append(node6)
node3.adjacent.append(node7)

# Run DFS
dfs(node1)

The code defines a Node class to represent vertices in the graph, with a visited flag and a list of adjacent nodes. The dfs function takes a starting node as input and recursively visits its unvisited neighbors, marking them as visited and printing their names.

The code then creates a small graph with seven nodes and six edges, and runs the dfs function on the first node. The output should be the names of the nodes visited in depth-first order, which in this case should be "A", "B", "D", "E", "C", "F", and "G".

Note that this implementation assumes that the graph is connected, meaning that every node can be reached from any other node. If the graph is not connected, you may need to modify the code to start the DFS from every unvisited node in the graph.

--

--

Mehmet Akif Cifci
Mehmet Akif Cifci

Written by Mehmet Akif Cifci

Mehmet Akif Cifci holds the position of associate professor in the field of computer science in Austria.

No responses yet