Graph Algorithms:

Graph Algorithms:

Introduction, DFS and BFS:

1. Graph and its representations
2. Breadth First Traversal for a Graph
3. Depth First Traversal for a Graph
4. Applications of Depth First Search
5. Detect Cycle in a Directed Graph

 Adobe, Amazon, BankBazaar, Flipkart, Microsoft, Oracle, Rockstand, Samsung

1. Detect Cycle in a an Undirected Graph
2. Detect cycle in an undirected graph
3. Longest Path in a Directed Acyclic Graph
4. Topological Sorting
5. Check whether a given graph is Bipartite or not
6. Snake and Ladder Problem
7. Biconnected Components
8. Check if a given graph is tree or not

Minimum Spanning Tree:

1. Prim’s Minimum Spanning Tree (MST))
2. Applications of Minimum Spanning Tree Problem
3. Prim’s MST for Adjacency List Representation
4. Kruskal’s Minimum Spanning Tree Algorithm
5. Boruvka’s algorithm for Minimum Spanning Tree

Shortest Paths:

1. Dijkstra’s shortest path algorithm
2. Dijkstra’s Algorithm for Adjacency List Representation
3. Bellman–Ford Algorithm
4. Floyd Warshall Algorithm
5. Johnson’s algorithm for All-pairs shortest paths
6. Shortest Path in Directed Acyclic Graph
7. Some interesting shortest path questions
8. Shortest path with exactly k edges in a directed and weighted graph

Connectivity:

1. Find if there is a path between two vertices in a directed graph
2. Connectivity in a directed graph
3. Articulation Points (or Cut Vertices) in a Graph
4. Biconnected graph
5. Bridges in a graph
6. Eulerian path and circuit
7. Fleury’s Algorithm for printing Eulerian Path or Circuit
8. Strongly Connected Components
9. Transitive closure of a graph
10. Find the number of islands
11. Count all possible walks from a source to a destination with exactly k edges
12. Euler Circuit in a Directed Graph
13. Biconnected Components
14. Tarjan’s Algorithm to find Strongly Connected Components

Hard Problems:

1. Graph Coloring (Introduction and Applications)
2. Greedy Algorithm for Graph Coloring
3. Travelling Salesman Problem (Naive and Dynamic Programming)
4. Travelling Salesman Problem (Approximate using MST)
5. Hamiltonian Cycle
6. Vertex Cover Problem (Introduction and Approximate Algorithm)
7. K Centers Problem (Greedy Approximate Algorithm)

Maximum Flow:

1. Ford-Fulkerson Algorithm for Maximum Flow Problem
2. Find maximum number of edge disjoint paths between two vertices
3. Find minimum s-t cut in a flow network
4. Maximum Bipartite Matching
5. Channel Assignment Problem

Misc:

1. Find if the strings can be chained to form a circle
2. Given a sorted dictionary of an alien language, find order of characters
3. Karger’s algorithm for Minimum Cut
4. Karger’s algorithm for Minimum Cut | Set 2 (Analysis and Applications)
5. Hopcroft–Karp Algorithm for Maximum Matching | Set 1 (Introduction)
6. Hopcroft–Karp Algorithm for Maximum Matching | Set 2 (Implementation)
7. Length of shortest chain to reach a target word
8. Find same contacts in a list of contacts

All Algorithms on Graph

Quiz on Graph

Quiz on Graph Traversals

Quiz on Graph Shortest Paths

Quiz on Graph Minimum Spanning Tree

Coding Practice on Graph

Facebook.java
KthNonRepeatingString.java
MedianOfSortedArrays.java
PermutationsOfString.java
RegionMatchesString.java
RemoveCharacters.java
SmallestStringWindowProblem.java
SortByFrequency.java
SortUsingLastNames.java
SpecialString.java
String_comparsion_Example.java
String_replace_Example.java