Skip to content

Graphs

  • Types of Graphs
  • Graph Traversal
    • Breadth first search BFS, BFS Tree
    • Depth first search DFS, DFS Tree
  • Union Find
  • Directed Acyclic Graph (DAG)
    • Topological traversal
    • Check for cycle in graph
  • On weighted graph
    • Find connected components
      • Kosaraju's algorithm, Tarjans Algorithm
    • Minimum spanning tree
      • Kruskal Algorithm, Prim algorithms, Brovuka'a Algorithm
    • Shortest path from source to all other nodes
      • Djkstra's Algorithm, Bellman ford's
    • Shortest path between all nodes to all other node
      • Floyd Warshall Algorithm, Johnson's Algorithm
    • Detect negative cycles
  • Connectivity
    • Path between two vertices
    • Bridges in a graph
    • Articulation Points
  • Traveling Salesman Problem (TSP)
  • Hamiltonian Path
  • Eulerian Graph
  • Network Flow (max flow)
    • Ford Fulkerson Algorithm