Graph Algorithms

Implementations of concepts and algorithms pertaining to CS graph theory.

Representation

• Adjacency matrix
• Adjacency list

Traversal

• Recursive DFS
• Iterative DFS
• BFS

Graph Cycle

• Detect cycle in a directed Graph
• Detect cycle in an undirected graph
• Detect cycle in a directed graph using colors

Topological Sort

• Topological sorting of a DAG

Minimum Spanning Tree

• Prim’s MST algorithm for matrix
• Prim’s MST for adjacency list
• Kruskal’s MST algorithm

Shortest Path

• Dijkstra’s for matrix representation
• Dijkstra’s for adjacency list
• Dijkstra’s using set in STL
• Bellman–Ford Algorithm
• Floyd Warshall Algorithm

Backtracking

• Rat in a maze I
• Rat in a maze II
• N-queen problem
• m-coloring problem
• Hamiltonian cycle
• Path of length > k from source

Connectivity

• Path between two vertices in a directed graph
• Connectivity in a directed graph
• Find the number of islands
• Transitive closure of a directed graph