Depth-First search (DFS) using Python

Depth-first search (DFS) is a graph traversal algorithm that starts at the root node and explores as far as possible along each branch before backtracking. It uses a stack to store the nodes that need to be explored, and processes the nodes in the order they were added to the stack. DFS is commonly used to explore the entire structure of a graph and to detect cycles in a graph.

Here is the code for a function that performs DFS on a graph represented as an adjacency list in Python:

def dfs(graph, start):
  # Initialize the stack with the start node
  stack = [start]
  # Initialize a set to store the visited nodes
  visited = set()
  
  # Iterate over the stack until it is empty
  while stack:
    # Get the next node from the stack
    node = stack.pop()
    # If the node has not been visited, visit it and add it to the visited set
    if node not in visited:
      visited.add(node)
      # Add the neighbors of the node to the stack
      stack.extend(graph[node])
  
  # Return the set of visited nodes
  return visited

# Test the function with a sample graph
graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
}
start = 'A'
print(dfs(graph, start))  # Output: {'A', 'C', 'F', 'E', 'B', 'D'}

This implementation of DFS has a time complexity of O(V+E), where V is the number of nodes and E is the number of edges in the graph. It is a simple and efficient algorithm for traversing the nodes of a graph, but it may not always find the shortest path between two nodes if the graph is weighted.