Skip to content

Latest commit

 

History

History
45 lines (32 loc) · 812 Bytes

File metadata and controls

45 lines (32 loc) · 812 Bytes

Graphs Representations:

  • Adjacency Matrix / Grid
  • Adjacency List / list

Graphs Algorithms

1) Searching Graphs

  • DFS -> Connected Components, Coloring components ✔️
  • BFS ✔️

2) Shortest Path Problem

  • BFS ✔️
  • Dijkstra's
  • Bellman-ford

3) Negative Cycle

  • Bellman-Ford
  • Floyd-Warshall ✔️

4) Stronly Connected components

  • Tarjan's Algo
  • Kosaraju's Algo

5) Traveling Salesman Problem

  • Held-Karp
  • Branch and bound
  • and many approxiation algorithms

6) Bridges ✔️

  • DFS No of Components ✔️

7) Articulation points

8) Minimum Spanning Tree

  • Krushal's
  • Prim's

9) Maximum Flow Networks

  • Ford-Fulkersor
  • Edmond-karp
  • Dinic's Algorithms

10) Kahn's Topological Sorting ✔️