# Clone given Graph

Given a graph with an adjacency list, we aim to clone the complete graph with edges. Cloning does creates a new memory for similar data. Let us understand this with a three-node example graph. We can solve this problem using either DFS or BFS. Let’s solve this problem using DFS. Our Graph object contains theRead More »

# Dijkstra algorithm to find the shortest path (greedy approach)

Consider having some cities, and a salesman wants to travel from one town (source) to another city (destination) with minimum travel distance. Here in the below example, we have six cities with travel distances between some of them. Below is the Dijkstra’s shortest path algorithm, which is a greedy method. Initialize distance from the sourceRead More »

# Topological sort of an acyclic directed graph

Topological sorting forms with the ordering of all its vertices topologically. A topological ordering of any edge “U–>V” in an acyclic directed graph starts with “U” then “V”. For example we can think of any processes dependency in which task ‘U’ needs to finish first to execute process ‘V’. We cannot do topological sorting onRead More »

# Breadth-first search or traversal (BFS) of a graph

Breadth-first search (BFS) is a search or traversal algorithm of a Graph Data Structure. This algorithm uses a queue to process each incoming vertex and process in LIFO order. At each vertex pops from the queue it takes all not visited adjacent vertices into queue this process happens until the queue becomes empty. Let’s seeRead More »

# Depth-first search or traversal (DFS) of a graph

Depth First Search (DFS) is a type of search or traversal algorithm for Graph data structure. This algorithm uses stack (system stack in case of recursion) to solve the traversal. Below is the DFS pictorial walk-through example of a simple 6 vertices and 7 edges graph. Let’s dive to code Depth-first search/traversal (DFS) routines. AsRead More »

# Graph data structure introduction

Graphs are most commonly using a data structure in computer applications, networks, and maps. These are introduced in early computing days. By definition a graph with “V” vertices (nodes) and “E” edges, where each edge “e” associates with one or more vertices. A graph with nodes {A, B, C, D, E} and edges {e1, e2,Read More »