Everyday here I add some notes on what I learnt, what needs to be done and what to revise.

For Graphs, I am using Striver’s A2Z list, as it contains more problems sorted by easy-hard.

  1. Traversal Algorithms: BFS (For Level-Order Traversal), DFS (To go in-depth & to detect cycle).

  2. Graphs can be stored in many ways using Adjacency Matrix, Adjacency Lists (Efficient, useful & easy) https://www.geeksforgeeks.org/graph-and-its-representations/. And using edge list to store from-node and to-node in an array of size 2.

  3. To detect a cycle, traverse the graph and keep track of the path where came from (maybe using a list or set) and check if the node exist in the path.

  4. Finding Distinct Components: Finding the count of graphs which are connected (https://leetcode.com/problems/number-of-provinces/). For this, use a visited[] to know if we already visited, then go to each node call dfs to it’s connected nodes, until all the connected nodes are visited the dfs call will not end. Once it ends, increment the count and while visiting any node, mark it as visited.

  5. Check if Undirected Graph has Cycle: https://www.youtube.com/watch?v=BPlrALf1LDU&feature=youtu.be

  6. Topological Sort: using DFS traversal. Start from 0, and go until the end of the node, and start putting those elements to an array, and mark them as visited. Loop through all the nodes and check if they’re visited skip, else use DFS. And at the end reverse the result array.

  7. Bipartite Graph: https://leetcode.com/problems/is-graph-bipartite/solutions/6215287/javascript-bfs-solution-with-explanation-7bev/.

    Bipartite (in simple terms) - color the node with one color and for neighbor use different color. (use 2 colors) If any node that has same color to the neighbor this means the graph is not bipartite.

  8. Cloning a Graph: https://leetcode.com/problems/clone-graph/solutions/6220222/javascript-bfs-solution-using-hashmap-by-3mp0/.

    Use hashmap to store the old node to new node. And get the new nodes using old node for the neighbors.

  9. Kosaraju’s Algorithm:

    1. Using DFS to travel till the end of the graph, and put the node’s into a stack and keep track of visited nodes. This is called storing the nodes ending time sorted order.
    2. Then reverse the graph, because we don't want to accidentally travel into another component.
    3. Pop from the stack, traverse the graph using DFS, increment the counter if the node is not visited. https://takeuforward.org/graph/strongly-connected-components-kosarajus-algorithm-g-54/

  10. Dijkstra’s Algorithm: https://www.youtube.com/watch?v=V6H1qAeB-l4

  11. Eventual Safe States: https://leetcode.com/problems/find-eventual-safe-states/solutions/6261960/topological-sort-javascript-solution-wit-3tmi/

  12. TODO: Bellman Ford, Floyd Warshal, Union-Find (Disjoint Sets).