Topological Sort Algorithm for DAG
Given a Directed Acyclic Graph (DAG), print it in topological order using topological sort algorithm. If the DAG has more than one topological ordering, output any of them.
Tag: Must Know
Types of edges involved in DFS and relation between them
This post describes the types of edges involved in Depth–first search (DFS) of a tree and directed & undirected graphs and establish the relation between them.
Arrival and departure time of vertices in DFS
The arrival time is the time at which the vertex was explored for the first time in the DFS, and departure time is the time at which we have explored all the neighbors of the vertex, and we are ready to backtrack.
Depth First Search (DFS) – Iterative and Recursive Implementation
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 for a graph) and explore as far as possible along each branch before backtracking.
Breadth-First Search (BFS) – Iterative and Recursive Implementation
Breadth–first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first before moving to the next-level neighbors.
Graph Implementation in C++ (without using STL)
Given an undirected or a directed graph, implement the graph data structure in C++ without using STL. Implement for both weighted and unweighted graphs using the adjacency list representation.
Graph Implementation in Java using Collections
In this post, we will see graph implementation in Java using Collections for weighted and unweighted, graph and digraph.
Graph Implementation in C++ using STL
Given an undirected or a directed graph, implement a graph data structure in C++ using STL. Implement for both weighted and unweighted graphs using the adjacency list representation of the graph.
Implement Graph Data Structure in C
This post will cover graph data structure implementation in C using an adjacency list. The post will cover both weighted and unweighted implementation of directed and undirected graphs.
Terminology and Representations of Graphs
This post discusses the basic definitions in terminologies associated with graphs and covers the adjacency list and adjacency matrix representations of the graph data structure.
In-place vs out-of-place algorithms
All algorithms can be classified into in-place and out-of-place algorithms based on the amount of extra space used by them. In this quick article, we’ll explore the difference between the two.
Introduction to Dynamic Programming
Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map, etc.).