🧩 TUF_graph_revision.txt

-------------------------------------------
## Graph Introduction (2 types)
- Undirected graph (no direction)
- Directed graph (has direction)

# If cycle present we call it CYCLIC GRAPH
# If cycle not present ACYCLIC GRAPH

~ if edges has some number mentioned -> it's a weighted graph!
~ by default consider weight to be 1 if not given and weight is required
-------------------------------------------

## Representation of Graph can be done in 2 ways

1) Adjacency Matrix
- If 2,3 | 1,2 | 1, 3 are given we can create a matrix out of it showing the edges as 1 and where i, j are the nodes
    1  2  3
    -------
1 | 0  1  1
2 | 1  0  1
3 | 1  1  0

2) Adjacency List
- Sometimes i, j are too large that we can't use adjacency matrix, hence we use adjacency list!
- Same thing can be represented in the form of list as well
- 2,3 | 1,2 | 1, 3

vector<int> adj[3+1]
adj[0] => {}
adj[1] => {2, 3}
adj[2] => {1, 3}
adj[3] => {1, 2}

- What if weighed given?

vector<pair<int, int>> adj[3+1] -> "WE USE PAIR<int, int> to store <vectex, weight>"
adj[0] => {}
adj[1] => { {2, 12}, {3, 43} }
adj[2] => { {1, 12}, {3, 23} }
adj[3] => { {1, 43}, {2, 23} }
-------------------------------------------

## Write code for multiple components whether it is DFS or BFS.

- Take visited array and initialise as 0
    for(int i = 0; i <= n; i++) {
        if (!visited [ i ] ) {
                    write code for either BFS or DFS
        }
    }

-------------------------------------------

# Breadth First Search (BFS)

include<iostream>
include<vector>
include<queue>

using namespace std;

# BFS! (queue is used!)
vector<int> getBFS(int vertices, vector<int> adj[]) {
    vector<int> bfs;
    queue<int> store;
    store.push(1);
    vector<int> visited(vertices, 0);
    visited[1]=1;
    while(!store.empty()) {
        int node = store.front();
        store.pop();
        bfs.push_back(node);
        for(int i: adj[node]) {
            if(!visited[i]) {
                visited[i]=1;
                store.push(i);
            }
        }
    }
    return bfs;
}

void addEdges(int u, int v, vector<int> adj[]) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void printVec(vector<int>& arr) {
    for(int i: arr) cout<<i<<" ";
}

int main() {
    int vertices = 8;
    vector<int> adj[vertices];
    addEdges(1, 2, adj);
    addEdges(2, 3, adj);
    addEdges(2, 7, adj);
    addEdges(7, 5, adj);
    addEdges(3, 5, adj);
    vector<int> bfs = getBFS(vertices, adj);
    printVec(bfs);
}

/*
GRAPH:

     1 -->  2 --> 3
            |     |
            ˘     ˘
            7 --> 5
*/

-------------------------------------------

# Depth First Search (DFS)

include<iostream>
include<vector>
include<queue>

using namespace std;

void recurse(int node, vector<int> arr[], vector<int>& visited, vector<int>& dfs) {
    dfs.push_back(node);
    visited[node]=1;
    for(int i: arr[node]) {
        if(!visited[i])
            recurse(i, arr, visited, dfs);
    }
}

vector<int> getDFS(int vertices, vector<int> arr[]) {
    vector<int> visited(vertices, 0);
    vector<int> dfs;
    for(int i=1;i<=vertices;i++) {
        if(!visited[i] && arr[i].size())
            recurse(i, arr, visited, dfs);
    }
    return dfs;
}

void addEdges(int u, int v, vector<int> adj[]) {
    adj[u].push_back(v);
    adj[v].push_back(u);
}

void printVec(vector<int>& res) {
    for(int i: res) cout<<i<<" ";
}

int main() {
    int vertices = 8;
    vector<int> adj[vertices];
    addEdges(1, 2, adj);
    addEdges(2, 3, adj);
    addEdges(2, 7, adj);
    addEdges(7, 5, adj);
    addEdges(3, 5, adj);
    vector<int> dfs = getDFS(vertices, adj);
    printVec(dfs);
}

/*
GRAPH (Undirected Graph)

     1 ---  2 --- 3     
            |     |
            |     |
            7 --- 5
*/


-------------------------------------------
# BIPARTITE GRAPH USING BFS/DFS

Q) Check if graph is Bipartite using BFS (queue) OR level order.

Q) Check if graph is Bipartite using DFS (recursion).

-------------------------------------------
## DETECT CYCLE

#DFS (using isVisited and dfs array)
Q) Detect Cycle in a directed Graph!
* LOGIC: As we will be backtracking at some point if cycle is not there, we can have another array apart from visited
* So as soon as we will backtrack we will set 0 to the array, but visited will still be 1, as no need coming to there as there is no way after that!
* Hence these 2 array approach works with DFS for detecting cycle in a directed graph!

#BFS (using Kahn's Algorithm)
Q) Detect Cycle in a directed Graph!
- In Kahns algo we can form topological sort only if there is no cycle. While forming the sequence through indegree, all the indegree go back to 0 at last, if not means cycle exists
* - We already know how to do Topological Sorting using bfs
* - And in that we find indegree and then form the topological sort
* - hence, while completeting indegree and forming the sort, we can check if all indegree are returned back to 0, which they should in case of DAG
* - But if all indegree aren't changed back to 0 that means there is some cycle formed
* - because in scratch try!- for cycle there won't be any more 0 there and hence it will be bfs will stop!

-------------------------------------------
## TOPOLOGICAL SORT

#DFS
Q) Topological Sorting (It's not sorting! But u,v where u comes before v sorting)
-> We just need to do DFS and use a stack
 * - Why stack? In stack at bottom will be the item which has no outgoing edges
 * - And as we go on top will have nodes which are having more outgoing edges
 * - Hence, at last we can just pop them out and print it
 * - So Topological sorting is basically ( DFS + STACK + VISITED_ARRAY)

#BFS (using Kahn's Algorithm)
Q) Topological Sorting (It's not sorting! But u,v where u comes before v sorting)
- Idea is: the node with least indegree will be kept first!
* - First we need to find all the indegrees
* - Then pick those which have 0 indegrees (will be there as it's DAG)
* - Now, just do BFS and keep inserting node whose indegree turn to 0...
* - Hence we will get topological sort in the result
* 
* NOTE: During BFS we will keep reducing the indegree of the connected node so we can push the new zero degree node to the queue
-------------------------------------------
## MINIMUM DISTANCE FROM A NODE

 #BFS
 Q) Minimum distance in a undirected graph from a source (with 1 wt. of each edge)
 * LOGIC: As we know bfs goes level by level, hence we can make use of it and increment size as we move forward
 * - We will push the node again in queue if the lentth is updated to any smaller value
 * - Or else if length is already small, we won't push it in queue
 * NOTE: Make sure to keep the length initially to INT_MAX so those can be updated

 #BFS
 Q) Minimum distance in a weighted DAG (here edges will have weight and direction)
 * ->Similar to 1) undirected_graph_with_1_wight_bfs, with minor change
 * - Here adjacency list will not have int, rather pair<int, int>
 * - Why? As the edges are wighted, hence from for edge 1 connected to 0 with edge weight as 12 we will show as [0] = {{1, 12}}
 * - Hence, while checking the distance and pushing in queue we will check if it's yielding min distance
 * - If yes then update and insert it in queue (so that other connected nodes to it can also be updated)
 -------------------------------------------

 ## Dijkstras Algorithm
 * LOGIC: In BFS we used to push the all nodes in next level to the queue
 * - But in that case it would push even the node with largest edge weight to the queue
 * - Whereas in Dikstras, it's similar to BFS, but here we will use priority queue
 * - WHY? so that we can initially discover those nodes which has shortest length from source 
 * - From those nodes we can update the shortest length to other nodes (RELAXATION PROCESS)
 * - Hence, as we keep reaching the new nodes(picking node from priority queue means the length of that node is set to smallest now)
 -------------------------------------------

 ## Minimum Spanning Tree
- A spanning tree is a tree where all vertices are connected with minimum number of edges
- For V vertices, V-1 number are minimum edges required.
- “MINIMUM“ denotes that those edges must have smallest sum of weight possible
- Prims & Kruskals are used for finding Minimum Spanning Tree

-------------------------------------------

## PRIMS ALGORITHM (One of the algo to form Minimum spanning Tree, other is Kruskals)
* LOGIC: First thing to understand is what is Minimum spanning Tree
* - Second thing is the Prims Algorithm
* 
* Prims Algo says that to find a min spanning tree
* - Pick the min edge and go through it, now at new node, again see what all edges are present
* - Now among both the nodes, check which is minimum edge wt. and push it (Make sure not to push visited node's edge)
* - At last all node will be covered. Just by taking minimum edges each time.
* 
* NOTE: To keep the bucket of edges, use min Heap! as it will only take O(logN) for all operations

-------------------------------------------

## Kruskals ALGORITHM (Algo to form minimum spanning tree)- (Pre-requisite - disjoint sets (to check cycle))
* LOGIC: Things to understand
* 1) Minimum spanning tree - V vertices,V-1 edges, sum of min edges
* 2) Keep picking minimum edges, but cycle may form
* 3) To avoid cycle make use of Disjoint sets
* 4) Rank and compression is optimized way of disjoint set O(4Alpha) ~ O(4)

NOTE: Check disjoint_set to understand Rank and compression 

-------------------------------------------

## Bridges, Critical Connections in a graph (Hard problem, yet simple- just understand approach)
* LOGIC: Problem is simple, it's important to understand the approach
* - We are required to find the bridge, if broken, no. of components will increase
* 
* - Now what we can do is assign cost to each node and increase as we go to next node
* - Once reached visited node, we can return the cost from there
* - And see if the current node has cost more than that or less than that
* 
* - If cost more than that (the next node) that means the path has some alternative and breaking the bridge will create no effect to no. of components
* - But if cost less than that, that means IT'S A BRIDGE !!
* 
* - Hence we need to keep record of cost array as well as visited array
* NOTE: Make sure not to go back to node from where you are coming, just return the cost to it so it can compare with it's current value

-------------------------------------------

## Articulation Point, Node which is single point failure (Similar to other problem!)
* LOGIC: Maintain visited array first to check which nodes are visited
* - We will do a DFS Traversal here
* - Keep updating the time at which the node was seen
* - Also if node encounters another node which has lower time of seen
* - It will acquire it and return back to the node from where it came
* - So that previous node can know that even if they are removed, the other graph can still reach the previous nodes hence it's not an articulation point
* - The point where the next node returns lowerstTime same or more -> that means that node is articulation pt, as next node can reach the prvious part of the graph!

-------------------------------------------