Tag: DFS

Flood Fill Algorithm

Flood fill (also known as seed fill) is an algorithm that determines the area connected to a given node in a multi-dimensional array.

Find all occurrences of given string in a character matrix

Given a M x N matrix of characters, find all occurrences of a given string in the matrix. We are allowed to search the string in all eight possible directions i.e. North, West, South, East, North-East, North-West, South-East, South-West. Note that there should not be any cycles in the output path.

Check if given digraph is a DAG (Directed Acyclic Graph) or not

Given an directed graph, check if it is a DAG (Directed Acyclic Graph) or not. A DAG is a digraph (directed graph) that contains no cycles.   Below graph contains a cycle A-B-D-A, so it is not DAG. If we remove edge 3-0 from it, it will become a DAG.

2-Vertex Connectivity in the graph

Given a undirected connected graph, check if the graph is 2-vertex connected or not. A connected graph G is said to be 2-vertex-connected (or 2-connected) if it has more than 2 vertices and remains connected on removal of any vertices. Any such vertex whose removal will disconnected the graph is called Articulation point.