**Knight Tour Problem** : Given a chess board of size n x n, initial position of knight and final position of knight. We need to find the minimum number of steps required to reach final position, If it is impossible to reach final position then return -1. Knight moves according to following rules and is not allowed to leave chess board. Consider the diagram below [Read more…]

## Spanning Tree

In the mathematical field of graph theory, a spanning tree T of a connected, undirected graph G is a tree that includes all of the vertices and some or all of the edges of G.

## Defination

A tree is a connected undirected graph with no cycles. It is a spanning tree of a graph G if it spans G (that is, it includes every vertex of G) and is a subgraph of G (every edge in the tree belongs to G). A spanning tree of a connected graph G can also be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices.

## BFS (Breath First Search)

In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search.

## Algorithm

The algorithm uses a queue data structure to store intermediate results as it traverses the graph, as follows:

1) Enqueue the root node

2) Dequeue a node and examine it

[Read more…]

## DFS (Depth First Search)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.

## Properties of DFS

The time and space analysis of DFS differs according to its application area. In theoretical computer science, DFS is typically used to traverse an entire graph, and takes time O(|E|), linear in the size of the graph. In these applications it also uses space O(|V|) in the worst case to store the stack of vertices on the current search path as well as the set of already-visited vertices. Thus, in this setting, the time and space bounds are the same as for breadth-first search and the choice of which of these two algorithms to use depends less on their complexity and more on the different properties of the vertex orderings the two algorithms produce.

[Read more…]