lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

pythonIntroAlgorithms2Chapter3Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter4Title

def dfs(graph, start, visited=[]):
    if start not in visited:
        visited.append(start)

        for next in graph[start]:
            dfs(graph, next, visited)

    return visited


graph = {'A': ['B', 'C'],
         'B': ['A', 'D', 'E'],
         'C': ['A', 'F'],
         'D': ['B'],
         'E': ['B', 'F'],
         'F': ['C', 'E']}

print(dfs(graph, 'A'))

# Depth First Search (DFS) Implementation

## 1. Using Stack

- DFS uses a stack to keep track of nodes that have been visited. Recursive calls can inherently implement the stack.

```python title="Example using Stack"
def dfs(graph, start, visited=[]):
    if start not in visited:
        visited.append(start)

        for next in graph[start]:
            if next not in visited:
                dfs(graph, next, visited)

    return visited
```

<br />

## 2. Recursive Search

- From the current node, look for adjacent nodes that haven't been visited and continue the search.

```python title="Example of Recursive Search"
for next in graph[start]:
    if next not in visited:
        dfs(graph, next, visited)
```

<br />

## Time Complexity

1. `Time Complexity`: (O(V + E))

   - Here, `V` is the number of vertices, and `E` is the number of edges. Each vertex is visited once, and each edge is checked twice (in both directions).

2. `Efficiency in Acyclic Graphs`: DFS is effective for visiting all nodes in acyclic graphs.

3. `Caution in Cyclic Graphs`: In graphs with cyclic paths, there's a risk of falling into an infinite loop, so additional mechanisms might be needed to prevent this.