search

HarshCasper / NeoAlgo

Bringing all Data Structures and Algorithms under one Roof âš¡
MIT License
876 stars 1.05k forks source link

Addition to Graph Theory Problems/WoC #1576

Closed Sidhant-Gupta closed 3 years ago

Sidhant-Gupta commented 3 years ago

💥 Proposal- Graph Theory standard problems.

I will implement the following algorithms in C++ with a proper discussion of their time complexites.

  1. Bellman Fords algorithm- Shortest path problem (even with negative edges)
  2. Detect Negative Cycle in a Graph.
  3. Ford Fulkerson Algorithm-Max flow problem
  4. Dinic's Algorithm- Max Flow problem
  5. Find the number of islands in the graph.
  6. Graph Coloring- Greedy

For the shortest path problem, right now only Dijkstra is implemented and it does not give correct results when negative edges are present. So I will implement the standard Bellman-Ford algorithm.

Max Flow Problem- The aim of this problem is to generate the maximum amount of flow that a network would allow from source to sink. I will discuss two standard algorithms to solve this problem.

Graph Coloring - Color a graph with min number of colors such that no two adjacent vertices have same color. Although this is a NP-Complete problem but our algo will guarantee an upper bound on the number of colors. The algorithm never uses more than d+1 colors where d is the maximum degree of a vertex in the given graph.

Have you read the [Contributing Guidelines on Pull Requests]

Yes, I have read.

charlie219 commented 3 years ago

@shraddhavp @iamrajiv @HarshCasper I would like to take the following algos in Python