Reverse the Directed Graph
Objective: Given a directed graph, write an algorithm to reverse the graph. Example: Approach: Create a new graph with the same number of vertices. Traverse the given graph. Here we are using the adjacency...
Category: Graphs
Determine the order of Tests when tests have dependencies on each other
Objective: You are working on a project where QA team has automated set of test cases for the project, but these test cases have to be executed in a specific order since test cases...
Implement Graph Using Map – Java
Earlier, we have seen Graph and its representations. A graph can be represented using adjacency list and adjacency matrix. So far we have seen the traditional implementation of the Graph. In this article, we...
Count number of subgraphs in a given graph
Objective: Given a Graph, write a program to count all the subgraphs. Example: Approach: Use Depth-First Search Start the DFS from any random vertex. Once DFS is completed check if all the vertices are...
Check if given an edge is a bridge in the graph
Objective – Given a graph and an edge, write a program to check if the edge is a bridge. Bridge in Graph: An edge is called a bridge if connects two subgraphs and removing...
Max Flow Problem – Ford-Fulkerson Algorithm
Objective: Given a directed graph that represents a flow network involving source(S) vertex and Sink (T) vertex. Each edge in the graph has an individual capacity which is the maximum flow that edge allows....
Find the nearest building which has bike | Find nearest specific vertex from source in a graph.
Objective: Given a matrix (NxN) which represents the buildings in community. You are in a building and you need a bike to travel. There are few buildings in community which has bikes which you...
Max Flow Problem – Introduction
Max Flow Problem- Maximum flow problems find a feasible flow through a single-source, single-sink flow network that is maximum. This problem is useful for solving complex network flow problems such as the circulation problem. The maximum value...
Dijkstra Algorithm Implementation – TreeSet and Pair Class
Earlier we have seen what Dijkstra algorithm is is and how it works. In this article we will see its implementation using adjacency list and TreeSet. Example: Implementation – Adjacency List and Priority Queue...
Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Priority Queue – Java Implementation
Earlier we have seen what Dijkstra’s algorithm is and how it works. In this article we will see its implementation using adjacency list and Priority Queue. Prerequisites: Adjacency List Priority Queue Dijkstra’s Algorithm basics...
Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency List and Min Heap – Java Implementation
Earlier we have seen the basics of Dijkstra algorithm. In this article we will see its implementation using adjacency list and Min Heap. We strongly recommend reading the following articles Dijkstra algorithm and how...
Dijkstra’s – Shortest Path Algorithm (SPT) – Adjacency Matrix – Java Implementation
Earlier we have seen what Dijkstra’s algorithm is and how it works. In this article we will see its implementation using adjacency matrix. We strongly recommend reading – Dijkstra algorithm and how it works....
Djkstra’s – Shortest Path Algorithm (SPT)
What is Dijkstra’s algorithm? Dijkstra algorithm is a greedy algorithm. It finds a shortest path tree for a weighted undirected graph. This means it finds a shortest paths between nodes in a graph, which may represent, for example, road networks For a given...
Kruskal’s Algorithm – Minimum Spanning Tree (MST) – Complete Java Implementation
What is Kruskal Algorithm? Kruskal’s algorithm for finding the Minimum Spanning Tree(MST), which finds an edge of the least possible weight that connects any two trees in the forest It is a greedy algorithm. It...
Introduction to Minimum Spanning Tree (MST)
What is a Spanning Tree? In an undirected and connected graph G=(V,E), a spanning tree is a subgraph that is a tree which includes all of the vertices of G, with minimum possible number of edges. A graph...