Welcome To Sora Park

Breadth-first search (BFS)

BFS is a traversing algorithm that starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory is needed to keep track of the child nodes that were encountered but not yet explored.

The traversing process is as follows:

Pseudocode

BFS(G, root) is
	let Q be a queue
    label root as explored
    Q.enqueue(root) // insert a tree root in queue until every neighbour vertices are marked
    while Q is not empty do:
    	v := Q.dequeue() // remove a to-be-visited vertex from queue
        if v is the goal then
        	return v
        for all edges from v to w in G.adjacentEdges(v) do:
        	if w is not labelled as explored then
            	label w as explored
                Q.enqueue(w) // store w in Q if it's not visited
        end for
    end while
end

Depth-first search (DFS)

DFS is a traversing algorithm that starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.

The traversing process is as follows:

Pseudocode

DFS(G,v) // v is the vertex where the search starts
	Stack S := {}; // start with an empty stack
    for each vertex u, set visited[u] := false
    	push S, v;
        while S is not empty do:
        	u := pop S;
            if u is not visited then
            	visited[u] := true;
                for each unvisited neighbout w of u
                	push S, w;
                end for
         end while
     end for
end

Example

The number of vertices: 4

The number of edges: 5

Start node: 1

#include <iostream>
#include <queue>

#define MAX_VAL 1001

int N, M, V;
int mat[MAX_VAL][MAX_VAL];
bool visited[MAX_VAL];

using namespace std;
void dfs(int v)
{
    printf("%d, ", v);
    visited[v] = true;
    for (int i = 1; i <= N; i++)
    {
        if (visited[i] || mat[v][i] == 0)
            continue;
        dfs(i);
    }
}

void bfs(int v)
{
    queue<int> q;
    q.push(v);
    visited[v] = true;
    while (!q.empty())
    {
        v = q.front();
        printf("%d, ", q.front());
        q.pop();
        for (int i = 1; i <= N; i++)
        {
            if (visited[i] || mat[v][i] == 0)
                continue;
            q.push(i);
            visited[i] = true;
        }
    }
}

int main()
{
    int x, y;
    cin >> N >> M >> V;
    for (int i = 0; i < M; i++)
    {
        cin >> x >> y;
        mat[x][y] = mat[y][x] = 1;
    }
    memset(visited, false, sizeof(visited));
    dfs(V);
    prinft("\n");
    memset(visited, false, sizeof(visited));
    bfs(V);
}

Complexity

• |V| is the number of vertices
• |E| is the number of edges

Does a function call itself? It's called recursive.

If the function is computed by a loop or repetition, the procedure is called iterative.

Often an iterative approach for the evaluation of a recursively defined sequence requires much less computation than a procedure using recursion.

Fibonacci exemplifies the difference between recursion and iteration.

# Fibonacci Numbers

Fibonacci numbers form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

The sequence starts 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

# Recursive Fibonacci

int test(int n)
{
    if (n > 1)
    {
        return test(n - 1) + test(n - 2);
    }
    else
    {
        return n;
    }
}

# Iterative Fibonacci

int test(int n)
{
    if (n > 0)
    {
        int x = 0, y = 1, z;
        for (int i = 1; i < n; i++)
        {
            z = (x + y);
            x = y;
            y = z;
        }
        return y;
    }
    return 0;
}

void test(int input)
{
    if (input > 0)
    {
        printf("%d, ", input);
        test(input - 1);
        printf("%d, ", input);
    }
}

The test function will give the following output back once called:

"3, 2, 1, 1, 2, 3, "

The first print function completes printing out the given input value three times before the second one is called.

This is how the recursive algorithm works!

Recursive algorithms solve a problem by reducing it to an instance of the same problem with smaller input.

Here is a recursive algorithm for computing n factorial (n!):

int test(int input)
{
    printf("%d, ", input);
    if (input == 0)
    {
        return 1;
    }
    else
    {
        return input * test(input - 1);
    }
}

The output is as follows:

"3, 2, 1, 0, "

# Recursive function for exponentiation

The below definition would be very helpful to solve the problem!

a^(n+1) = a * a^n for n > 0 and the initial condition a^0 = 1.

To find a^n, successively use the recursive step to reduce the exponent until it becomes zero.

int test(int base, int input)
{
    if (input > 0)
    {
        test(base, input - 1);
    }

    ans = (input == 0 ? 1 : base * ans);
    printf("%d, ", ans);

    return ans;
}

The output of the function is "1, 2, 4, 8, ".

If someone doesn't want to see the output in the terminal, the below method would be more explicit to understand how the algorithm works:

int test(int base, int input)
{
	if (input == 0)
    {
    	return 1;
    }
    else
    {
    	return base * test(base, input - 1);
    }
}

# Recursive modular exponentiation

The method is based on the fact below:

b^2 mod m = (b * b^(n-1) mod m)) mod m and the initial condition b^0 mod m = 1

However, there is a much more efficient recursive algorithm based on the observation that

In case that n is even, b^n mod m = (b^(n/2) mod m)^2 mod m
In case that n is odd, b^n mod m = ((b^(floor(n/2)) mod m)^2 mod m * b mod m) mod m

int test(int b, int n, int m)
{
    if (n == 0)
    {
        return 1;
    }
    else if (n % 2 == 0)
    {
        ans = pow(test(b, n / 2, m), 2);
        return ans % m;
    }
    else
    {
        ans = pow(test(b, floor(n / 2), m), 2);
        return (ans % m * b % m) % m;
    }
}

# Recursive linear search algorithm

This algorithm is designed to search for the first occurrence of x in the sequence.

int test(int i, int x)
{
    if (arr[i] == x)
    {
        return i;
    }
    else if (i == arr.size() - 1)
    {
        return -1;
    }
    else
    {
        return test(i + 1, x);
    }
}

# Recursive binary search algorithm

This approach is to find the location of x in the sequence of integers in increasing order.

To perform a binary search, it begins by comparing x with the middle term,

a[floor(n+1) / 2]

int test(int i, int j, int x)
{
    m = floor((i + j) / 2);
    if (arr[m] == x)
    {
        return m;
    }
    else if (x < arr[m] && i < m)
    {
        return test(i, m - 1, x);
    }
    else if (x > arr[m] && j > m)
    {
        return test(m + 1, j, x);
    }
    else
    {
        return -1;
    }
}