CT Week 11

📚

DFS and Recursive Procedure Call

Depth First Search (DFS)

Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

How DFS Works

DFS uses a stack data structure, either implicitly through recursion or explicitly. The steps are:

1. Start at the root node.
2. Mark the current node as visited and print it.
3. Traverse all the adjacent and unmarked nodes. Push each adjacent node into a stack.
4. Repeat the process until the stack is empty.

Pseudocode for DFS

function DFS(graph, start):
    let S be a stack
    S.push(start)
    while S is not empty:
        vertex = S.pop()
        if vertex is not labeled as discovered:
            label vertex as discovered
            for all edges from vertex to neighbor in graph:
                S.push(neighbor)
    

Recursion

Recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. A recursive function calls itself to solve these smaller instances.

How Recursion Works

A recursive function has two main parts:

• Base Case: The condition under which the recursion ends.
• Recursive Case: The part of the function where the function calls itself.

Pseudocode for a Recursive Function

function recursiveFunction(parameters):
    if base case condition:
        return base case value
    else:
        return recursiveFunction(modified parameters)
    

Procedure Call

A procedure call is a statement in a program that causes a procedure to be executed. In the context of recursion, a procedure call is when a function calls itself.

Procedure for Recursion

The procedure for recursion involves:

1. Defining the base case to stop the recursion.
2. Defining the recursive case where the function calls itself with modified parameters.
3. Ensuring that each recursive call progresses towards the base case.

DFS Using Recursion

DFS can also be implemented using recursion. Here is the pseudocode for DFS using a recursive approach:

function DFS(graph, vertex, visited):
    visited[vertex] = true
    for neighbor in graph[vertex]:
        if not visited[neighbor]:
            DFS(graph, neighbor, visited)
    

In this approach, we use a recursive function to visit all the vertices of the graph. The function marks the current vertex as visited and then recursively visits all the unvisited neighbors.

This PDF contains a summary covering weeks 1 to 11.

PA

GA