
- Works for weighted graph.
- This is a **single-source shortest path** algorithm i.e. we are given a starting vertex, to all other vertices, and output the shortest path themselves.
- Can use for both directed and undirected graphs.
- Greedy Algorithm.
- Dijkstra doesn’t work for graphs with negative weight edges.

Dijkstra's Algorithm is based on the **principle of relaxation**, in which more accurate values gradually replace an approximation to the correct distance until the shortest distance is reached.

### Algorithm :

1. Initialize dist array, an array of distances from the source node *s* to each node in the graph, initialized the following way: dist(s) = 0; and for all other nodes v, dist(*v*) = ∞.
2. Then initialize a set s with pair 0 i.e. distance of source from source , and source.
3. Then while set s is not empty :
    1. Get the first element from set and remove it from set.
    2. Now iterate over the neighbours of that node.
    3. Check if distance till now and current edge length is less than dist[nbr].
    4. if yes then remove that element and enter new one with updated value i.e. distance till now + current edge length. Else do nothing.
4. dist array gets updated with shorted path from source to all the respective elements.

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<pair<int, int>> *l;

 public:
  Graph(int v) {
    V = v;
	  l = new list<pair<int, int>>[v];
  }

  void addEdge(int u, int v, int wt, bool undir = true) {
    l[u].push_back({wt, v});
    if (undir) l[v].push_back({wt, u});
  }

  int dijkstra(int src, int dest) {
    // data structures
    vector<int> dist(V, INT_MAX);
    set<pair<int, int>> s;

    // 1. Init
    dist[src] = 0;
    s.insert({0, src});  // dist, src

    while (!s.empty()) {
      auto it = s.begin();

      int node = it->second;
      int distTillNow = it->first;
      s.erase(it);  // pop

      // iterate over the neighbours of node
      for (auto nbrPair : l[node]) {
        int nbr = nbrPair.second;
        int currentEdgeLen = nbrPair.first;

        if (distTillNow + currentEdgeLen < dist[nbr]) {
          // remove if such a pair already exists
          auto f = s.find({dist[nbr], nbr});
          if (f != s.end()) s.erase(f);

          // insert updated value
          dist[nbr] = distTillNow + currentEdgeLen;
          s.insert({dist[nbr], nbr});
        }
      }
    }

    // single source shortest distance to all other nodes
    for (int i = 0; i < V; i++) {
      cout << "Node " << i << " Dist " << dist[i] << endl;
    }

    return dist[dest];
  }
  
};

int main() {
  Graph g(5);
  g.addEdge(0, 1, 1);
  g.addEdge(1, 2, 2);
  g.addEdge(0, 2, 4);
  g.addEdge(0, 3, 7);
  g.addEdge(3, 2, 2);
  g.addEdge(3, 4, 3);

  cout << g.dijkstra(0, 4);
  return 0;
}
```

[https://cp-algorithms.com/graph/dijkstra.html](https://cp-algorithms.com/graph/dijkstra.html)

Dijkstra's Algorithm


A **spanning tree** of a graph consists of all nodes of the graph and some of the edges of the graph so that there is a path between any two nodes. Like trees in general, spanning trees are connected and acyclic. Usually there are several ways to construct a spanning tree.

Properties of Minimum Spanning Tree :

- A minimum spanning tree of a graph is unique, if the weight of all the edges are distinct. Otherwise, there may be multiple minimum spanning trees. (Specific algorithms typically output one of the possible minimum spanning trees).
- Minimum spanning tree is also the tree with minimum product of weights of edges. (It can be easily proved by replacing the weights of all edges with their logarithms)
- In a minimum spanning tree of a graph, the maximum weight of an edge is the minimum possible from all possible spanning trees of that graph. (This follows from the validity of Kruskal's algorithm).
- The maximum spanning tree (spanning tree with the sum of weights of edges being maximum) of a graph can be obtained similarly to that of the minimum spanning tree, by changing the signs of the weights of all the edges to their opposite and then applying any of the minimum spanning tree algorithm.

![9o8mldss.bmp](/minimum-spanning-tree/9o8mldss.bmp)

A **minimum spanning tree** is a spanning tree whose weight is as small as possible.

A MST has V-1 edges.

### Real Life Application :

- Building road networks for different cities.

## Alortihms for finding Minimum Spanning Tree :

- Prism’s Algorithm
- Kruskal’s Algorithm

<div id="prims-algorithm"></div>

## Prim’s Algorithm :

The minimum spanning tree is built gradually by adding edges one at a time. At first the spanning tree consists only of a single vertex (chosen arbitrarily). Then the minimum weight edge outgoing from this vertex is selected and added to the spanning tree. After that the spanning tree already consists of two vertices. Now select and add the edge with the minimum weight that has one end in an already selected vertex (i.e. a vertex that is already part of the spanning tree), and the other end in an unselected vertex. And so on, i.e. every time we select and add the edge with minimal weight that connects one selected vertex with one unselected vertex. The process is repeated until the spanning tree contains all vertices (or equivalently until we have n−1 edges).

![Untitled](/minimum-spanning-tree/Untitled.png)

```cpp
class Graph {
  int V;
  vector<pair<int, int>> *l;

public:
  Graph(int n) {
    V = n;
    l = new vector<pair<int, int>>[n];
  }
  
  void addEdge (int x, int y, int w) {
    l[x].push_back({y, w});
    l[y].push_back({x, w});
  }
  
  int prim_mst () {
    // Init a Min Heap
    // this looks complex but its just opposite of priority_queue<pair<int, int>> Q
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
  	
    // visited array to get weather a node has been visited or not
    bool *visited = new bool[V]{0};
    int ans = 0;
  	
    // begin
    Q.push({0, 0}); // weight, node

    while (!Q.empty()) {
      // pick out the edge with min weight
      auto best = Q.top();
      Q.pop();
  		
      int to = best.second;
      int weight = best.first;
  		
      if (visited[to]) {
        // discard the edge, and continue
        continue;
      }
  		
      // otherwise take the current edge
      ans += weight;
      visited[to] = 1;
  		
      // add the new edges in the queue
      for (auto x : l[to]) {
        if (visited[x.first] == 0) {
          Q.push({x.second, x.first});
        }
      }
    }
  }
};
```

<div id="kruskals-algorithm"></div>

## Kruskal’s Algorithm :

Kruskal's algorithm initially places all the nodes of the original graph isolated from each other, to form a forest of single node trees, and then gradually merges these trees, combining at each iteration any two of all the trees with some edge of the original graph. Before the execution of the algorithm, **all edges are sorted by weight** (in non-decreasing order). Then begins the process of unification: pick all edges from the first to the last (in sorted order), and if the ends of the currently picked edge belong to different subtrees, these subtrees are combined, and the edge is added to the answer. After iterating through all the edges, all the vertices will belong to the same sub-tree, and we will get the answer.

Algorithm :

1. Sort edges by their weights.
2. Iterate to sorted edges one-by-one.
3. Pick an edge add it to our MST if it doesnot form a cycle and belongs to a differrent set.

```cpp
// dsu finding a cycle
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  vector<pair<int, int>> l;

public:
  Graph (int n) {
    V = n;
  }

  void addEdge(int x, int y) {
    l.push_back({x, y});
  }

  //Find Function (optimized)
  int find (int i, vector<int> &parent) {
    if (parent[i] == -1) return i;
    else return parent[i] = find (parent[i], parent);
  }

  //Union Function (optimized)
  void unite (int s1, int s2, vector<int> &parent, vector<int> &rank) {
    if (rank[s1] > rank[s2]) {
      parent[s2] = s1;
      rank[s1] += rank[s2];
    } else {
      parent[s1] = s2;
      rank[s2] += rank[s1];
    }
  }

  //contain cycle
  bool containCycle () {
    vector<int> parent(V, -1);
    vector<int> rank(V, 1);

    for (auto edge : l) {
      int s1 = find (edge.first, parent);
      int s2 = find (edge.second, parent);

      if (s1 == s2) return true;
      else unite(s1, s2, parent, rank);
    }
		
    return false;
  }
};

int main() {
  Graph g(3);
  g.addEdge(0, 1);
  g.addEdge(0, 2);

  cout << g.containCycle(parent);
  return 0;
}
```

<div id="difference"></div>

## Difference between Prim’s and Kruskal Algorithm :

![Untitled](/minimum-spanning-tree/Untitled%201.png)

[https://cp-algorithms.com/graph/mst_prim.html](https://cp-algorithms.com/graph/mst_prim.html)

[https://cp-algorithms.com/graph/mst_kruskal.html](https://cp-algorithms.com/graph/mst_kruskal.html)

Minimum Spanning Tree

Prim's Algorithm

Kurskal's Algorithm

Difference between Prism's and Kruskal's Algoritms


- Only for undirected graphs.

Also called a **union–find data structure** or **merge–find set**, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union),  and it will be able to tell in which set a specific element is and finding a representative member of a set. The last operation allows to find out efficiently if any two elements are in the same or different sets.

The data structure allows you to do each of these operations in almost O(1) time on average.

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<pair<int, int>> l;

 public:
  Graph(int V) { this->V = V; }

  void addEdge(int u, int v) { l.push_back(make_pair(u, v)); }

  // Find
  int findSet(int i, int parent[]) {
    // base case
    if (parent[i] == -1) return i;
    return findSet(parent[i], parent);
  }

  // Union
  void unionSet(int x, int y, int parent[]) {
    int s1 = findSet(x, parent);
    int s2 = findSet(y, parent);

    if (s1 != s2) parent[s1] = s2;
  }

  bool containsCycle() {
    // DSU logic to check if graph contains cycle or not
    int *parent = new int[V];
    for (int i = 0; i < V; i++) {
      parent[i] = -1;
    }

    // interate over the edge list
    for (auto edge : l) {
      int i = edge.first;
      int j = edge.second;

      int s1 = findSet(i, parent);
      int s2 = findSet(j, parent);

      if (s1 != s2)
        unionSet(s1, s2, parent);
      else {
        cout << "Same parents " << s1 << " and " << s2 << "\n";
        return true;
      }
    }

    delete[] parent;
    return false;
  }
};

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(1, 2);
  g.addEdge(2, 3);
  g.addEdge(3, 0);

  cout << g.containsCycle();
  return 0;
}

//Output
//Same parents 3 and 3
//1
```

![autodraw 12_24_2021.png](/disjoint-set-union/autodraw_12_24_2021.png)

## Optimization :

1. Path Compression Optimization in DSU (Find Fn).
2. Union by Rank (Union Fn).

<div id="path-compression-optimization"></div>

## Path Compression Optimization :

![Untitled](/disjoint-set-union/Untitled.png)

This optimization is designed for speeding up **`findSet`**.

```cpp
int findSet(int i, int parent[]) {  // Time = O(n)
    // base case
    if (parent[i] == -1) return i;
    // path compression optimisation
    return parent[i] = findSet(parent[i], parent);
  }
```

<div id="union-by-rank"></div>

## Union By Rank (Balance optimization):

![Untitled](/disjoint-set-union/Untitled%201.png)

```cpp
// dsu finding a cycle
#include <bits/stdc++.h>
using namespace std;

class Graph {
	int V;
	vector<pair<int, int>> l;

public:
	Graph (int n) {
		V = n;
	}

	void addEdge(int x, int y) {
		l.push_back({x, y});
	}

	//Find Function (optimized)
	int find (int i, vector<int> &parent) {
		if (parent[i] == -1) return i;
		else return parent[i] = find (parent[i], parent);
	}

	//Union Function (optimized)
	void unite (int s1, int s2, vector<int> &parent, vector<int> &rank) {
		if (rank[s1] > rank[s2]) {
			parent[s2] = s1;
			rank[s1] += rank[s2];
		} else {
			parent[s1] = s2;
			rank[s2] += rank[s1];
		}
	}

	//contain cycle
	bool containCycle () {
		vector<int> parent(V, -1);
		vector<int> rank(V, 1);

		for (auto edge : l) {
			int s1 = find (edge.first, parent);
			int s2 = find (edge.second, parent);

			if (s1 == s2) return true;
			else unite(s1, s2, parent, rank);
		}
		
		return false;
	}
};

int main() {
	Graph g(3);
	g.addEdge(0, 1);
	g.addEdge(0, 2);
	
	cout << g.containCycle(parent); // 0
	return 0;
}
```

Disjoint Set Union

Path compression Optimization

Union by rank optimization

Disjoint Set Union (DSU)


## Topological Sorting :

Topological sorting for Directed Acyclic Graph (DAG) is a linear odering of vertices such that for every directed edge (u,v) vertex u come before v in the odering. Topological sorting for a graph is not possible if the graph is not a DAG.

For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another.

Applications of Topological Sorting :

- **Scheduling jobs** from the given dependencies among jobs.
- Operation System **deadlock detection**.
- **Dependency resolution:** Suppose, **A** class extends **B** class. Then **B** has a dependency on **A**, and **A** must be compiled before **B**.
- **Critical path analysis** is a project management technique. It is used to find the minimum time a project can take and the dependencies of each activity on others.
- Determining the order of compilation tasks to perform in make files, data serialization, and resolving symbol dependencies in linkers.

Visualize [here](https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html).

<div id="using-bfs"></div>

## Topological sorting using BFS (Kahn’s Algorithm) :

in_degree - No. of edges towards the node.

Algorithm steps:

1. Compute in-degree (number of incoming edges) for each of the vertex present in the DAG and initialize the count of visited nodes as 0.
2. Pick all the vertices with in-degree as 0 and add them into a queue
3. Remove a vertex from the queue (Dequeue operation) and then :
    1. Increment count of visited nodes by 1.
    2. Decrease in-degree by 1 for all its neighbouring nodes.
    3. If in-degree of a neighbouring nodes is reduced to zero, then add it to the queue.
4. Repeat Step 3 until the queue is empty.
5. If count of visited nodes is **not** equal to the number of nodes in the graph then the topological sort is not possible for the given graph.

![Untitled](/topological-sorting-in-dags/Untitled.png)

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;

 public:
  Graph(int v) {
    V = v;
    l = new list<int>[V];
  }

  void addEdge(int i, int j, bool undir = false) {
    l[i].push_back(j);
    if (undir) l[j].push_back(i);
  }

  void topologicalSort() {
    vector<int> indegree(V, 0);

    // Iterate over all the edges to find the right indegree
    for (int i = 0; i < V; i++) {
      for (auto nbr : l[i]) indegree[nbr]++;
    }

    // bfs
    queue<int> q;

    // init the q with nodes having 0 indegree
    for (int i = 0; i < V; i++) {
      if (indegree[i] == 0) q.push(i);
    }

    // start popping
    while (!q.empty()) {
      int node = q.front();
      cout << node << " ";
      q.pop();

      // iterate over the nbrs of this node and reduce their indegree by 1
      for (auto nbr : l[node]) {
        indegree[nbr]--;
        if (indegree[nbr] == 0) q.push(nbr);
      }
    }
  }
};

int main() {
  Graph g(5);
  g.addEdge(0, 1);
  g.addEdge(0, 3);
  g.addEdge(1, 3);
  g.addEdge(1, 2);
  g.addEdge(3, 2);
  g.addEdge(2, 4);

  g.topologicalSort();  //0 1 3 2 4

  return 0;
}
```

<div id="using-dfs"></div>

## Topological sorting using DFS :

Alogrithm steps :

1. Create the graph by calling addEdge(a,b).
2. Call the dfsTopologicalSort( )
    1. Create a stack and a boolean array named as visited[ ];
    2. Mark all the vertices as not visited i.e. initialize visitedwith 'false' value.
    3. Call the recursive helper function dfs() to store Topological Sort starting from all vertices one by one.
3. Inside dfs function :
    1. Mark the current node as visited.
    2. Recur for all the vertices adjacent to this vertex.
    3. Push current vertex to stack which stores result.
4. Atlast after return from the helper function, print contents of stack.

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;

 public:
  Graph(int v) {
    V = v;
    l = new list<int>[V];
  }

  void addEdge(int i, int j, bool undir = false) {
    l[i].push_back(j);
    if (undir) l[j].push_back(i);
  }

  void dfs(int node, vector<bool> &visited, list<int> &ordering) {
    visited[node] = true;

    for (int nbr : l[node]) {
      if (!visited[nbr]) dfs(nbr, visited, ordering);
    }
    // at this point we are backtracking
    ordering.push_front(node);
    return;
  }

  void dfsTopologicalSort() {
    vector<bool> visited(V, false);
    list<int> ordering;

    // call dfs from node if not visited
    for (int i = 0; i < V; i++) {
      if (!visited[i]) dfs(i, visited, ordering);
    }

    for (auto a : ordering) {
      cout << a << " ";
    }
  }
};

int main() {
  Graph g(5);
  g.addEdge(0, 1);
  g.addEdge(0, 3);
  g.addEdge(1, 3);
  g.addEdge(1, 2);
  g.addEdge(3, 2);
  g.addEdge(2, 4);

  g.dfsTopologicalSort();  // 0 1 3 2 4

  return 0;
}
```

Topological Sorting

Using BFS(Kahn's Algorithm)

Using DFS

Topological Sorting in DAGs


Every *graph* without a cycle is a *Tree*. If a graph contains a cycle then we have a way to visit node more than one time.

![Untitled](/cycle-detection-in-graphs/Untitled.png)

<div id="undirected-graph"></div>

## Cycle Detection in Undirected Graphs :

An Undirected Graph contains a cycle if next node is already visited and next node is not parent node of current node.

Using Depth-First Search (DFS) :

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;

 public:
  Graph(int v) {
    V = v;
    l = new list<int>[V];
  }

  void addEdge(int i, int j, bool undir = true) {
    l[i].push_back(j);
    if (undir) l[j].push_back(i);
  }

  bool dfs(int node, vector<bool> &visited, int parent) {
    // mark that node visited
    visited[node] = true;
    for (auto nbr : l[node]) {
      if (!visited[nbr]) {
        bool foundACycle = dfs(nbr, visited, node);
        if (foundACycle) return true;
      } else if (nbr != parent)
        return true;
    }
    return false;
  }

  bool contains_cycle() {
    // graph is a single component
    vector<bool> visited(V, false);
    return dfs(0, visited, -1);
  }
};

int main() {
  Graph g(6);
  g.addEdge(0, 1);
  g.addEdge(0, 4);
  g.addEdge(2, 1);
  g.addEdge(3, 4);
  g.addEdge(4, 5);
  g.addEdge(2, 3);
  g.addEdge(3, 5);
  cout << g.contains_cycle();  // 1
  return 0;
}
```

<div id="directed-graph"></div>

## Cycle Detection in Directed Graph :

In Directed Graph we store both visited nodes and nodes of current path (using stack). If next node is visited and also in current path then the graph contains a cycle.

![Untitled](/cycle-detection-in-graphs/Untitled%202.gif)

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;

 public:
  Graph(int v) {
    V = v;
    l = new list<int>[V];
  }

  void addEdge(int i, int j, bool undir = false) {
    l[i].push_back(j);
    if (undir) l[j].push_back(i);
  }

  bool dfs(int node, vector<bool> &visited, vector<bool> &stack) {
    // return true if backedge is found, else return false
    // arrive at node
    visited[node] = true;
    stack[node] = true;

    for (int nbr : l[node]) {
      if (stack[nbr])
        return true;
      else if (!visited[nbr]) {
        bool nbrFoundACycle = dfs(nbr, visited, stack);
        if (nbrFoundACycle) return true;
      }
    }

    // going back
    stack[node] = false;
    return false;
  }

  bool contains_cycle() {
    vector<bool> visited(V, false);
    vector<bool> stack(V, false);

    for (int i = 0; i < V; i++) {
      int source = i;
      if (!visited[source]) {
        if (dfs(source, visited, stack)) return true;
      }
    }
    return false;
  }
};

int main() {
  Graph g1(3);
  g1.addEdge(0, 1);
  g1.addEdge(1, 2);
  g1.addEdge(2, 0);
  cout << g1.contains_cycle() << "\n";  //1

  Graph g2(3);
  g2.addEdge(0, 1);
  g2.addEdge(1, 2);
  cout << g2.contains_cycle() << "\n";  //0

  return 0;
}
```

<div id="bipartite-graph"></div>

## Bipartite Graph :

![Untitled](/cycle-detection-in-graphs/Untitled%203.png)

Bipartite graphs may be characterized in several different ways:

- A graph is bipartite if and only if it does not contain an odd cycle.
- A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).
- Any bipartite graph consisting of n vertices can have at most n^{2}/4 edges.
- The spectrum of a graph is symmetric if and only if it is a bipartite graph.

![Untitled](/cycle-detection-in-graphs/Untitled%204.png)

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;

 public:
  Graph(int v) {
    V = v;
    l = new list<int>[V];
  }

  void addEdge(int i, int j, bool undir = true) {
    l[i].push_back(j);
    if (undir) l[j].push_back(i);
  }

  bool dfsHelper(int node, int *visited, int parent, int color) {
    visited[node] = color;

    for (auto nbr : l[node]) {
      if (visited[nbr] == 0) {
        int subProblem = dfsHelper(nbr, visited, node, 3 - color);
        if (!subProblem) return false;
      } else if (nbr != parent and color == visited[nbr]) {
        return false;
      }
    }
    return true;
  }

  bool isBipartite() {
    int visited[V] = {0};
    int color = 1;
    return dfsHelper(0, visited, -1, color);
  }
};

int main() {
  // by coloring nodes at each step
  // if current node has color 1
  // then adjacent on should have color 2
  Graph g1(3);
  g1.addEdge(0, 1);
  g1.addEdge(1, 2);
  g1.addEdge(2, 0);
  cout << g1.isBipartite() << "\n";  //0

  Graph g2(4);
  g2.addEdge(0, 1);
  g2.addEdge(1, 2);
  g2.addEdge(2, 3);
  g2.addEdge(3, 0);
  cout << g2.isBipartite() << "\n";  //1

  return 0;
}
```

Cycle Detection in Graphs

Undirected Graph

Directed Graph

Bipartite Graph


Content of this post are notes taken from [this freecodecamp video](https://www.youtube.com/watch?v=HXV3zeQKqGY).

![Untitled](/mysql-queries-basics/Untitled.png)

![Untitled](/mysql-queries-basics/Untitled%201.png)

![Untitled](/mysql-queries-basics/Untitled%202.png)

![Untitled](/mysql-queries-basics/Untitled%203.png)

![Untitled](/mysql-queries-basics/Untitled%204.png)

![Untitled](/mysql-queries-basics/Untitled%205.png)

![Untitled](/mysql-queries-basics/Untitled%206.png)

![Untitled](/mysql-queries-basics/Untitled%207.png)

![Untitled](/mysql-queries-basics/Untitled%208.png)

![Untitled](/mysql-queries-basics/Untitled%209.png)

![Untitled](/mysql-queries-basics/Untitled%2010.png)

![Untitled](/mysql-queries-basics/Untitled%2011.png)

<div id="tables-and-keys-in-rdbms"></div>

## Tables and Keys in RDBMS

- It have rows and columns.
- We have a **primary key** which helps in uniquely identifying a specific row in database.

<table>
  <tr>
    <th>Student id (p)</th>
    <th>name</th>
    <th>major</th>
    <th>Branch id (f)</th>
  </tr>
  <tr>
    <td>1</td>
    <td>Jayesh</td>
    <td>Mathematics</td>
    <td>11</td>
  </tr>
  <tr>
    <td>2</td>
    <td>Jay</td>
    <td>Biology</td>
    <td>12</td>
  </tr>
  <tr>
    <td>2</td>
    <td>Jayesh</td>
    <td>Mathematics</td>
    <td>11</td>
  </tr>
</table>

Here both Jayesh are different and can be identified by student id (primary key).

- Here, student id is a **Surrogate Key** and a surrogate key is basically a key that has no mapping to anything in the real world. Just random number.
- We can also use **Natural Keys** instead of surrogate keys. A natural key is a key that has significance in real world. For example :- SSN(social security number), our own roll number 19T5030 as it gives so much info about my academics.
- Another key is **Foreign Keys.** And a foreign key is an attribute that we can store on a database table that will link us to another database table. Here Branch can work as a foreign key.

<table>
  <tr>
    <th>Branch</th>
    <th>Strength</th>
    <th>Class Teacher</th>
    <th>Branch id</th>
  </tr>
  <tr>
    <td>E&TC</td>
    <td>78</td>
    <td>John</td>
    <td>11</td>
  </tr>
  <tr>
    <td>CSE</td>
    <td>72</td>
    <td>Kate</td>
    <td>12</td>
  </tr>
</table>

Here branch id is linking us to another table

- Foreign Keys can also be used to define relationship in same table. Example :- In a database of employees, some employees can be the manager of others.
- Primary key can also consists of more than one columns, and this is what we would call **Composite keys.** A composite key is a key that needs two attribute.

<table>
  <tr>
    <th>Branch</th>
    <th>Teacher</th>
    <th>Subject</th>
  </tr>
  <tr>
    <td>11</td>
    <td>John</td>
    <td>Java</td>
  </tr>
  <tr>
    <td>11</td>
    <td>Kate</td>
    <td>C++</td>
  </tr>
  <tr>
    <td>12</td>
    <td>Kate</td>
    <td>C++</td>
  </tr>
</table>

Here branch id and teacher both works as primary key i.e. they together are composite key.

- Color values
    
    Primary key
    
    Foreign key
    
    Composite key
    

![Untitled](/mysql-queries-basics/Untitled%2012.png)

<div id="structured-query-language"></div>

## Structured Query Language (SQL) ➖

![Untitled](/mysql-queries-basics/Untitled%2013.png)

![Untitled](/mysql-queries-basics/Untitled%2014.png)

![Untitled](/mysql-queries-basics/Untitled%2015.png)

### Queries

- A query is a set of instructions given to the RDBMS (written in SQL) that tell the RDBMS what information you want it to retrieve for you.
    - Tons of data in database.
    - Often hidden in a complex schema.
    - Goal is to only get the data you need.

```sql
SELECT employee.name, employee.age
FROM employee
WHERE employee.salary > 3000;
```

<div id="creating-tables"></div>

## Creating Tables

Datatypes :

```sql
INT -- Whole Numbers
DECIMAL(M,N) -- Decimal Numbers with M total digits, N digits after decimal
VARCHAR(l) -- String of text of length l
BLOB -- Binary Large Object, Stores large data
DATE -- 'YYYY-MM-DD'
TIMESTAMP -- 'YYYY-MM-DD HH:MM:SS
```

Let's create a table -

```sql
CREATE TABLE student (
    student_id INT PRIMARY KEY,
    name VARCHAR(20),
    major VARCHAR(20)
);

or

CREATE TABLE student (
    student_id INT,
    name VARCHAR(20),
    major VARCHAR(20),
		PRIMARY KEY(student_id)
);
```

This will create -

<table>
  <tr>
    <th>student_id (p)</th>
    <th>name</th>
    <th>major</th>
  </tr>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
</table>
- To see table -

```sql
DESCRIBE student;
```
<table>
  <tr>
    <th>Field</th>
    <th>Type</th>
    <th>Null</th>
    <th>Key</th>
    <th>Default</th>
    <th>Extra</th>
  </tr>
  <tr>
    <td>student_id</td>
    <td>int(11)</td>
    <td>NO</td>
    <td>PRI</td>
    <td>NULL</td>
    <td></td>
  </tr>
  <tr>
    <td>name</td>
    <td>varchar(20)</td>
    <td>YES</td>
    <td></td>
    <td>NULL</td>
    <td></td>
  </tr>
  <tr>
    <td>major</td>
    <td>varchar(20)</td>
    <td>YES</td>
    <td></td>
    <td>NULL</td>
    <td></td>
  </tr>
</table>

- To Delete Table -

```sql
DROP TABLE student;
```

- Add a column to the Table -

```sql
ALTER TABLE student ADD gpa DECIMAL(4,2);
```

- Delete a column of the Table -

```sql
ALTER TABLE student DROP COLUMN gpa;
```

<div id="inserting-data-in-table"></div>

## Inserting Data in Table -

```sql
INSERT INTO student VALUES(
    1, 'Jack', 'Biology'
);
```

- See Table values -

```sql
SELECT * FROM student;
```

<table>
  <tr>
    <th>student_id (p)</th>
    <th>name</th>
    <th>major</th>
  </tr>
  <tr>
    <td>1</td>
    <td>Jack</td>
    <td>Biology</td>
  </tr>
  <tr>
    <td></td>
    <td></td>
    <td></td>
  </tr>
</table>
- What if we have some blank values -

```sql
INSERT INTO student(student_id, name) VALUES(2, 'Kate');
```

<table>
  <tr>
    <th>student_id (p)</th>
    <th>name</th>
    <th>major</th>
  </tr>
  <tr>
    <td>1</td>
    <td>Jack</td>
    <td>Biology</td>
  </tr>
  <tr>
    <td>2</td>
    <td>Kate</td>
    <td>NULL</td>
  </tr>
</table>

<div id="constrains"></div>

## Constrains -

- Make fields Required -

```sql
CREATE TABLE student (
    student_id INT PRIMARY KEY,
    name VARCHAR(20) NOT NULL, -- NOT NULL
    major VARCHAR(20)
);
```

- Make fields Unique -

```sql
CREATE TABLE student (
    student_id INT PRIMARY KEY,
    name VARCHAR(20) UNIQUE,  -- UNIQUE
    major VARCHAR(20)
);
```

- PRIMARY KEY is NOT NULL and UNIQUE by default.
- We want to set a default value -

```sql
CREATE TABLE student (
    student_id INT PRIMARY KEY,
    name VARCHAR(20),
    major VARCHAR(20) DEFAULT 'undecided'   -- default string value undecided
);
```

- We are increasing PRIMARY KEY on each entry, we can also make db do that -

```sql
CREATE TABLE student (
    student_id INT AUTO_INCREMENT, -- Now we don't need to enter id
    name VARCHAR(20),
    major VARCHAR(20),
		PRIMARY KEY(student_id)
)
```

<div id="update-and-delete"></div>

## Update and Delete -

- What if we want to change some information from database -

```sql
UPDATE student
SET major = 'Bio'
WHERE major = 'Biology';
-- this will change all Biology major fields to Bio
```

- Other comparison operations -

| = | equal |

| <> | not equal |

| > | greater than |

| < | less than |

| >= | greater than or equal  |

| <= | less than or equal |


```sql
UPDATE student
SET major = 'Biochemistry'
WHERE major = 'Bio' OR major = 'Chemistry';
-- obvious
```

```sql
UPDATE student
SET name = 'Tom', major = 'undecided'
WHERE student_id = 1;
-- obvious
```

- If we remove WHERE statement, then it will get applied to every column of table -

```sql
UPDATE student
SET major = 'Science';
```

- Delete row from table -

```sql
DELETE FROM student;  -- This will delete all the rows from the table

DELETE FROM student
WHERE student_id = 5;  -- Delete a specific row

DELETE FROM student
WHERE name = 'Tom' AND major = 'Bio';
```

<div id="basic-queries"></div>

## Basic Queries -

Getting information from database.

- Grab all the information -

```sql
SELECT * FROM student;
```

- Grab a column -

```sql
SELECT name FROM student;
```

- Grab multiple columns -

```sql
SELECT name, major FROM student;
or
SELECT student.name, student.major FROM student;
```

- Sort by values -

```sql
SELECT name, major 
FROM student
ORDER BY name;

SELECT name, major 
FROM student
ORDER BY name DESC; -- For descending order && ASC for ascending

SELECT name, major 
FROM student
ORDER BY student_id;  -- even though we are not selecting id we can order by it

SELECT name, major 
FROM student
ORDER BY major, student_id;  -- first sort by major then student_id
```

- Limit number of result -

```sql
SELECT *
FROM student
LIMIT 2;  -- gonna show only two result
```

- Filtering -

```sql
SELECT *
FROM student
WHERE major = 'Chemistry';  -- fiter

SELECT *
FROM student
WHERE major = 'Chemistry' OR major = 'Biology';  -- fiter

-- We can use a bunch of comparison operators in WHERE
-- <, >, <=, >=, <>

SELECT *
FROM student
WHERE name IN ('Claire', 'Kate', 'Mike');  -- domains

-- we can always combine all the queries
```

<div id="designing-company-schema"></div>

## Designing company schema -

![cuxkpwg9.bmp](/mysql-queries-basics/cuxkpwg9.bmp)

```sql
CREATE TABLE employee (
  emp_id INT PRIMARY KEY,
  first_name VARCHAR(40),
  last_name VARCHAR(40),
  birth_day DATE,
  sex VARCHAR(1),
  salary INT,
  super_id INT,
  branch_id INT
);

CREATE TABLE branch (
  branch_id INT PRIMARY KEY,
  branch_name VARCHAR(40),
  mgr_id INT,
  mgr_start_date DATE,
  FOREIGN KEY(mgr_id) REFERENCES employee(emp_id) ON DELETE SET NULL
);

ALTER TABLE employee
ADD FOREIGN KEY(branch_id)
REFERENCES branch(branch_id)
ON DELETE SET NULL;

ALTER TABLE employee
ADD FOREIGN KEY(super_id)
REFERENCES employee(emp_id)
ON DELETE SET NULL;

SELECT * FROM employee;

CREATE TABLE client (
  client_id INT PRIMARY KEY,
  client_name VARCHAR(40),
  branch_id INT,
  FOREIGN KEY(branch_id) REFERENCES branch(branch_id) ON DELETE SET NULL
);

CREATE TABLE works_with (
  emp_id INT,
  client_id INT,
  total_sales INT,
  PRIMARY KEY(emp_id, client_id),
  FOREIGN KEY(emp_id) REFERENCES employee(emp_id) ON DELETE CASCADE,
  FOREIGN KEY(client_id) REFERENCES client(client_id) ON DELETE CASCADE
);

CREATE TABLE branch_supplier (
  branch_id INT,
  supplier_name VARCHAR(40),
  supply_type VARCHAR(40),
  PRIMARY KEY(branch_id, supplier_name),
  FOREIGN KEY(branch_id) REFERENCES branch(branch_id) ON DELETE CASCADE
);

-- Corporate
INSERT INTO employee VALUES(100, 'David', 'Wallace', '1967-11-17', 'M', 250000, NULL, NULL);

INSERT INTO branch VALUES(1, 'Corporate', 100, '2006-02-09');

UPDATE employee
SET branch_id = 1
WHERE emp_id = 100;

INSERT INTO employee VALUES(101, 'Jan', 'Levinson', '1961-05-11', 'F', 110000, 100, 1);

-- Scranton
INSERT INTO employee VALUES(102, 'Michael', 'Scott', '1964-03-15', 'M', 75000, 100, NULL);

INSERT INTO branch VALUES(2, 'Scranton', 102, '1992-04-06');

UPDATE employee
SET branch_id = 2
WHERE emp_id = 102;

INSERT INTO employee VALUES(103, 'Angela', 'Martin', '1971-06-25', 'F', 63000, 102, 2);
INSERT INTO employee VALUES(104, 'Kelly', 'Kapoor', '1980-02-05', 'F', 55000, 102, 2);
INSERT INTO employee VALUES(105, 'Stanley', 'Hudson', '1958-02-19', 'M', 69000, 102, 2);

-- Stamford
INSERT INTO employee VALUES(106, 'Josh', 'Porter', '1969-09-05', 'M', 78000, 100, NULL);

INSERT INTO branch VALUES(3, 'Stamford', 106, '1998-02-13');

UPDATE employee
SET branch_id = 3
WHERE emp_id = 106;

INSERT INTO employee VALUES(107, 'Andy', 'Bernard', '1973-07-22', 'M', 65000, 106, 3);
INSERT INTO employee VALUES(108, 'Jim', 'Halpert', '1978-10-01', 'M', 71000, 106, 3);

INSERT INTO branch_supplier VALUES(2, 'Hammer Mill', 'Paper');
INSERT INTO branch_supplier VALUES(2, 'Uni-ball', 'Writing Utensils');
INSERT INTO branch_supplier VALUES(3, 'Patriot Paper', 'Paper');
INSERT INTO branch_supplier VALUES(2, 'J.T. Forms & Labels', 'Custom Forms');
INSERT INTO branch_supplier VALUES(3, 'Uni-ball', 'Writing Utensils');
INSERT INTO branch_supplier VALUES(3, 'Hammer Mill', 'Paper');
INSERT INTO branch_supplier VALUES(3, 'Stamford Lables', 'Custom Forms');

-- CLIENT
INSERT INTO client VALUES(400, 'Dunmore Highschool', 2);
INSERT INTO client VALUES(401, 'Lackawana Country', 2);
INSERT INTO client VALUES(402, 'FedEx', 3);
INSERT INTO client VALUES(403, 'John Daly Law, LLC', 3);
INSERT INTO client VALUES(404, 'Scranton Whitepages', 2);
INSERT INTO client VALUES(405, 'Times Newspaper', 3);
INSERT INTO client VALUES(406, 'FedEx', 2);

-- works_with
INSERT INTO works_with VALUES(105, 400, 55000);
INSERT INTO works_with VALUES(102, 401, 267000);
INSERT INTO works_with VALUES(108, 402, 22500);
INSERT INTO works_with VALUES(107, 403, 5000);
INSERT INTO works_with VALUES(108, 403, 12000);
INSERT INTO works_with VALUES(105, 404, 33000);
INSERT INTO works_with VALUES(107, 405, 26000);
INSERT INTO works_with VALUES(102, 406, 15000);
INSERT INTO works_with VALUES(105, 406, 130000);
```

- Some basic queries -

```sql
-- find all employees
SELECT * FROM employee;

-- find all clients
SELECT * FROM client;

-- find all employees salary sorted
SELECT * 
FROM employee
ORDER BY salary DESC;

-- find all employees order by sex then name
SELECT *
FROM employee
ORDER BY sex, first_name, last_name;

-- find the first 5 employees in table
SELECT *
FROM employee
LIMIT 5;

-- find the first and last name of all employees
SELECT first_name, last_name
FROM employee;

-- find the forename and surname of all employees
SELECT first_name AS forename, last_name as surname
FROM employee;

-- find out all the different gender
SELECT DISTINCT sex
FROM employee;
```

<div id="sql-functions"></div>

## SQL Functions -

```sql
-- find the number of employees
SELECT COUNT(emp_id)
FROM employee;

-- find the number of female employees born after 1970
SELECT COUNT(emp_id)
FROM employee
WHERE sex = 'F' AND birth_day >= '1971-01-01';

-- find the average of all employee salary
SELECT AVG(salary)
FROM employee;

-- find the sum of all employee salary
SELECT SUM(salary)
FROM employee;

-- find how many males and females are there
SELECT COUNT(sex), sex
FROM employee
GROUP BY sex;

-- find the total sales of each salesman
SELECT SUM(total_sales), emp_id
FROM works_with
GROUP BY emp_id;
```

<div id="wildcard"></div>

## Wildcard -

```sql
-- % = any # characters, _ = one character

-- find any client's who are an LLC
SELECT *
FROM client
WHERE client_name LIKE '%LLC';  -- if client_name looks like this, 
-- % here indicates that any character can come before that but it ends with LLC.

-- find any branch suppliers who are in label business
SELECT *
FROM branch_supplier
WHERE supplier_name LIKE '%Label%';

-- find any employee born in october
SELECT *
FROM employee
WHERE birth_day Like '____-10%';

-- find any clients who are schools
SELECT *
FROM client
WHERE client_name LIKE '%school%';
```

<div id="unions"></div>

## Unions -

Union is a basic SQL operator used to combine the results of multiple SELECT statements into one.

Rules of using UNION -

- Should have same number of columns in each queries.
- Should also have similar data types.

```sql
-- find a list of employee and branch names
SELECT first_name
FROM employee
UNION
SELECT branch_name
FROM branch
UNION 
SELECT client_name
FROM client;

-- find a list of all clients & branch suppliers' names
SELECT client_name, branch_id
FROM client
UNION
SELECT supplier_name, branch_id
FROM branch_supplier;

-- find the list of all the money spent or earned by the company
SELECT salary
FROM employee
UNION
SELECT total_sale
FROM works_with;
```

<div id="join"></div>

## JOIN -

JOIN are used to combine rows of two or more tables based on a related column between them -

```sql
-- find all branches and name of their managers
SELECT employee.emp_id, employee.first_name, branch.branch_name
FROM employee
JOIN branch
ON employee.emp_id = branch.mgr_id;
```

Types of joins -

- Inner JOIN - Inner JOIN(simply JOIN) combines the rows from two table whenever they have shared column in common.
- LEFT JOIN - Includes all the rows from the left table (FROM statement one).
- RIGHT JOIN - Includes all the rows from the right table
- Full OUTER JOIN - Combination of LEFT JOIN and RIGHT JOIN.

<div id="nested-queries"></div>

## Nested Queries -

```sql
-- find name of all employees who have
-- sold over 30,000 to a single client
SELECT employees.first_name, employees.last_name
FROM employee
WHERE employee.emp_id IN(
	SELECT works_with.emp_id
	FROM works_with
	WHERE works_with.total_sales > 30000;
)

-- find all clients who are handled by the branch
-- that Micheal Scott manages
-- assume that you know Micheal's ID
SELECT client_name
FROM client
WHERE branch_id IN(
	SELECT branch_id
	FROM branch
	WHERE mgr_id = 102
);
```
<div id="on-delete"></div>

## ON DELETE -

- ON DELETE SET NULL -

```sql
CREATE TABLE branch (
	branch_id INT PRIMARY KEY,
	branch_name VARCHAR(40),
	mgr_id INT,
	mgr_start_date DATE,
	FOREIGN KEY(mgr_id) REFERENCES employee(emp_id) ON DELETE SET NULL
);

-- here mgr_id will becomes NULL when emp_id is deleted

CREATE TABLE branch (
	branch_id INT PRIMARY KEY,
	branch_name VARCHAR(40),
	mgr_id INT,
	mgr_start_date DATE,
	FOREIGN KEY(mgr_id) REFERENCES employee(emp_id) ON DELETE CASCADE
);

-- here mgr_id wil get deleted when emp_id is deleted
```

<div id="trigger"></div>

## Triggers -

Trigger is a block of SQL code which will define a certain action when a certain operation gets performed on the database.

```sql
DELIMETER $$
CREATE
	TRIGGER my_trigger BEFORE INSERT
	ON employee
	FOR EACH ROW BEGIN
		INSERT INTO trigger_test VALUES('added new employee');
	END$$
DELIMETER ;
-- here we are changing delimeter to $$ sign then back to ;
-- Whenever a new value is inserted into employee table
-- 'added new employee' is added into trigger_test table

DELIMETER $$
CREATE
	TRIGGER my_trigger BEFORE INSERT
	ON employee
	FOR EACH ROW BEGIN
		INSERT INTO trigger_test VALUES(NEW.first_name);
	END$$
DELIMETER ;

-- this one will add first_name value of new entry in trigger_test

-- Complex trigger
DELIMETER $$
CREATE
	TRIGGER my_trigger BEFORE INSERT
	ON employee
	FOR EACH ROW BEGIN
		IF NEW.sex = 'M' THEN
			INSERT INTO trigger_test VALUES('added male employee')
		ELSEIF NEW.sex = 'F' THEN
			INSERT INTO trigger_test VALUES('added female employee')
		ELSE 
			INSERT INTO trigger_test VALUES('added other employee')
		END IF;
	END$$
DELIMITER ;
-- functioning obvious

-- Delete a trigger
DROP TRIGGER my_trigger;
```

What is Database?

Tables and keys in RDBMS

Structured Query Language (SQL)

Creating Tables

Inserting Data in Table

Constrains

Update and Delete

Basic Queries

Designing company schema

SQL Functions

Wildcard

UNION

JOIN

Nested Queries

ON DELETE

TRIGGER

MYSQL Queries Basics


There are two fundamental graph algorithms for traversal : Breadth-First Search and Depth-First Search. Both algorithms are given a starting node in the graph, and they visit all nodes that can be reached from the starting node. The difference in the algorithms is the order in which they visit the nodes.

<div id="breadth-first-search"></div>

## Breadth-First Search (BFS) :

Breadth-first search (BFS) visits the nodes in increasing order of their distance from the starting node. Thus, we can calculate the distance from the starting node to all other nodes using breadth-first search. 

![graph-bfs](/graph-traversal/Graph-BFS.gif)

The time complexity of breadth-first search is *O(n+ m),* where n is the number of nodes and m is the number of edges.

Its implementation is based on a queue that contains nodes. At each step, the next node in the queue will be processed. At each step, the next node in the queue will be processed. The following code assumes that the graph is stored as adjacency lists and maintains the following data structures:

```cpp
queue<int> q;
bool visited[N];
int distance[N];
```

The queue q contains nodes to be processed in increasing order of their distance. New nodes are always added to the end of the queue, and the node at the beginning of the queue is the next node to be processed. The array visited indicates which nodes the search has already visited, and the array distance will contain the distances from the starting node to all nodes of the graph.

The search can be implemented as follows, starting at node x:

```cpp
visited[x] = true;
distance[x] = 0;
q.push(x);
while (!q.empty()) {
  int s = q.front(); q.pop();
  // process node s
  for (auto u : adj[s]) {
    if (visited[u]) continue;
    visited[u] = true;
    distance[u] = distance[s]+1;
    q.push(u);
  }
}
```

<div id="bfs-code"></div>

## Breadth-First Search Code:

![graph-bfs](/graph-traversal/Untitled1.png)

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;
	
  public:
    Graph (int v) {
      V = v;
      l = new list<int>[V];
    }
		
    void addEdge (int i, int j, bool undir=true) {
      l[i].push_back(j);
      if (undir) l[j].push_back(i);
    }
		
    void printAdjList () {
      for (int i=0; i<V; i++) {
        cout << i << "-->";
        for (auto node : l[i]) cout << node << ",";
        cout << "\n";
      }
    }
		
    void bfs(int source) {
      queue<int> q;
      bool *visited = new bool[V]{0};  // initialized 0
			
      q.push(source);
      visited[source] = true;
			
      while(!q.empty()) {
        //do some work for every node
        int f = q.front();
        cout << f << " ";
        q.pop();
				
        //push nbr of current node inside queue
        for (auto nbr: l[f]) {
          if (!visited[nbr]) {
            q.push(nbr);
            visited[nbr] = true;
          }
        }
      }
    }
};

int main () {
  Graph g(6);
  g.addEdge(0,1);
  g.addEdge(0,4);
  g.addEdge(2,1);
  g.addEdge(3,4);
  g.addEdge(4,5);
  g.addEdge(2,3);
  g.addEdge(3,5);
  g.printAdjList();
  g.bfs(1);
	
  return 0;
}

//output:
// 
// 0-->1,4,
// 1-->0,2,
// 2-->1,3,
// 3-->4,2,5,
// 4-->0,3,5,
// 5-->4,3,
// 1 0 2 4 3 5
```

<div id="shortest-path-in-undirected-graph"></div>

## Shortest path from source to node in undirected graph

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;
	
  public:
    Graph (int v) {
      V = v;
      l = new list<int>[V];
    }
		
    void addEdge (int i, int j, bool undir=true) {
      l[i].push_back(j);
      if (undir) l[j].push_back(i);
    }
		
    void printAdjList () {
      for (int i=0; i<V; i++) {
        cout << i << "-->";
        for (auto node : l[i]) cout << node << ",";
        cout << "\n";
      }
    }
		
    void bfs(int source) {
      queue<int> q;
      bool *visited = new bool[V]{0};
      int *dist = new int[V]{0};
      int *parent = new int[V];
			
      for (int i=0; i<V; i++) parent[i] = -1;
			
      q.push(source);
      visited[source] = true;
      parent[source] = source;
      dist[source] = 0;
			
      while(!q.empty()) {
        //do some work for every node
        int f = q.front();
        cout << f;
        q.pop();
				
        //push nbr of current node inside queue
        for (auto nbr: l[f]) {
          if (!visited[nbr]) {
            q.push(nbr);
                                  
            parent[nbr] = f;
            dist[nbr] = dist[f]+1;
            visited[nbr] = true;
          }
        }
      }
      cout << "\n";
			
      //print shortest distance
      for (int i=0; i<V; i++) {
        cout << "Shortest dist to " << i << " is " << dist[i] << "\n";
      }
			
      //print the path from a source to any destination
      int dest = 5;
      if (dest != -1) {
        int temp = dest;
        while(temp!=source) {
          cout << temp << " -- ";
          temp = parent[temp];
        }
        cout << source << "\n";
      }
    }
};

int main () {
  Graph g(6);
  g.addEdge(0,1);
  g.addEdge(0,4);
  g.addEdge(2,1);
  g.addEdge(3,4);
  g.addEdge(4,5);
  g.addEdge(2,3);
  g.addEdge(3,5);
  g.printAdjList();
  g.bfs(1);
	
  return 0;
}

//output:
// 
// 0-->1,4,
// 1-->0,2,
// 2-->1,3,
// 3-->4,2,5,
// 4-->0,3,5,
// 5-->4,3,
// 102435
// from 1
// Shortest dist to 0 is 1
// Shortest dist to 1 is 0
// Shortest dist to 2 is 1
// Shortest dist to 3 is 2
// Shortest dist to 4 is 2
// Shortest dist to 5 is 3
// 5 -- 4 -- 0 -- 1
```

 <div id="depth-first-search"></div>

## Depth-First Search :

Depth-first search (DFS) is a straightforward graph traversal technique. The algorithm begins at a starting node, and proceeds to all other nodes that are reachable from the starting node using the edges of the graph.

Depth-first search always follows a single path in the graph as long as it finds new nodes. After this, it returns to previous nodes and begins to explore other parts of the graph. The algorithm keeps track of visited nodes, so that it processes each node only once.

The time complexity of depth-first search is O(n+ m) where n is the number of nodes and m is the number of edges, because the algorithm processes each node and edge once.

Depth-first search can be conveniently implemented using recursion. The following function dfs begins a depth-first search at a given node. The function assumes that the graph is stored as adjacency lists in an array.

```cpp
vector<int> adj[N];
```

and also maintains an array

```cpp
bool visited[N];
```

that keeps track of the visited nodes. Initially, each array value is false, and when the search arrives at node s, the value of visited[s] becomes true. The function can be implemented as follows:

```cpp
void dfs(int s) {
  if (visited[s]) return;
  visited[s] = true;
  // process node s
  for (auto u: adj[s]) {
    dfs(u);
  }
}
```

<div id="dfs-code"></div>

## Depth-First Search Code :

```cpp
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;

 public:
  Graph(int v) {
    V = v;
    l = new list<int>[V];
  }

  void addEdge(int i, int j, bool undir = true) {
    l[i].push_back(j);
    if (undir) l[j].push_back(i);
  }

  void printAdjList() {
    for (int i = 0; i < V; i++) {
      cout << i << "-->";
      for (auto node : l[i]) cout << node << ",";
      cout << "\n";
    }
  }

  void dfsHelper(int node, bool *visited) {
    visited[node] = true;
    cout << node << " ";
    // make a dfs call on all its unvisited neighbours
    for (int nbr : l[node]) {
      if (!visited[nbr]) dfsHelper(nbr, visited);
    }
    return;
  }

  void dfs(int source) {
    bool *visited = new bool[V]{0};
    dfsHelper(source, visited);
  }
};

int main() {
  Graph g(6);
  g.addEdge(0, 1);
  g.addEdge(0, 4);
  g.addEdge(2, 1);
  g.addEdge(3, 4);
  g.addEdge(4, 5);
  g.addEdge(2, 3);
  g.addEdge(3, 5);
  g.printAdjList();
  g.dfs(1);
  return 0;
}

// output
// 0-->1,4,
// 1-->0,2,
// 2-->1,3,
// 3-->4,2,5,
// 4-->0,3,5,
// 5-->4,3,
// 1 0 4 3 2 5
```

![m2791p06.bmp](/graph-traversal/m2791p06.bmp)

Graph Traversal

Breadth-First Search

Breadth-First Search Code

Shortest path in Undirected graph

Depth-First Search

Depth-First Search Code


## What is a Graph ? 🤔

A Graph is a non-linear data structure consisting of nodes (or vertices) and edges. Edges are the lines that connect two nodes in the graph.

![Graph Representation.png](/graph-representation/Graph_Representation.png)

<div id="types-of-graphs"></div>



## Types of Graphs :

Some of the useful types of graphs are :

![Untitled](/graph-representation/Untitled.png)

![Untitled](/graph-representation/Untitled%201.png)

![Untitled](/graph-representation/Untitled%202.png)

<div id="some-special-types-of-graphs"></div>

## Some special types of Graph :

![Untitled](/graph-representation/Untitled%203.png)

![Untitled](/graph-representation/Untitled%204.png)

![Untitled](/graph-representation/Untitled%205.png)

![Untitled](/graph-representation/Untitled%206.png)

<div id="representation-of-graphs"></div>

## Representation of Graphs :

Methods of representing or storing of graphs are :

- Adjacency List
- Adjacency Matrix
- Edge List
- 2D Matrix (Implicit Graph)

<div id="adjacency-list-representation"></div>

## Adjacency List Representation :

In the adjacency list representation, each node x in the graph is assigned an adjacency list that consists of nodes to which there is an edge from x. Adjacency lists are the most popular way to represent graphs, and most algorithms can be efficiently implemented using them.

A convenient way to store the adjacency lists is to declare an array of vectors as follows:

```cpp
vector<int> adj[N];
```

If the graph is undirected, it can be stored in a similar way, but each edge is added in both directions. For a weighted graph, the structure can be extended as follows:

```cpp
vector<pair<int,int>> adj[N];
```

In this case, the adjacency list of node a contains the pair (b,w) always when there is an edge from node a to node b with weight w.

![Untitled](/graph-representation/Untitled%208.png)

Adjecency List Representation using C++ :

```
#include <bits/stdc++.h>
using namespace std;

class Graph {
  int V;
  list<int> *l;
	
  public:
    Graph (int v) {
      V = v;
      l = new list<int>[V];  // here list is used insted of vector.
      // array, list , vector, hashmap anything can be used
    }
		
    void addEdge (int i, int j, bool undir=true) {
      l[i].push_back(j);
      if (undir) l[j].push_back(i);
    }
		
    void printAdjList () {
      for (int i=0; i<V; i++) {
        cout << i << "-->";
        for (auto node : l[i]) cout << node << ",";
        cout << "\n";
      }
		}
};

int main () {
  Graph g(6);
  g.addEdge(0,1);
  g.addEdge(0,4);
  g.addEdge(2,1);
  g.addEdge(3,4);
  g.addEdge(4,5);
  g.addEdge(2,3);
  g.addEdge(3,5);
  g.printAdjList();
	
  return 0;
}

//output:

0-->1,4,
1-->0,2,
2-->1,3,
3-->4,2,5,
4-->0,3,5,
5-->4,3,
```

Another Method : 

```cpp
#include <bits/stdc++.h>
using namespace std;

class Node {
  public:
    string name;
    list<string> neighbours;
		
    Node(string name) {
      this->name = name;
    }
};

class Graph {
  //All Nodes
  //Hashmap (string, Node*)
	
  unordered_map<string, Node*> m;
	
  public:
    Graph(vector<string> cities) {
      for(auto city: cities) {
        m[city] = new Node(city);
      }
    }
		
    void addEdge(string x, string y, bool undir=true) {
      m[x]->neighbours.push_back(y);	
			
      if (undir) m[y]->neighbours.push_back(x);
    }
		
    void printAdjList() {
      for (auto cityPair : m) {
        auto city = cityPair.first;
        Node  *node = cityPair.second;
        cout << city << "-->";
        for (auto nbr : node->neighbours) {
          cout << nbr << ",";
        }
        cout << "\n";
      }
    }
};

int main () {
  vector<string> cities = {"Delhi", "London", "Paris", "New York"};
  Graph g(cities);
	
  g.addEdge("Delhi", "London");
  g.addEdge("New York", "London");
  g.addEdge("Delhi", "Paris");
  g.addEdge("Paris", "New York");
  g.printAdjList();
	
  return 0;
}

//output:

New York-->London,Paris,
Paris-->Delhi,New York,
Delhi-->London,Paris,
London-->Delhi,New York,
```

![Untitled](/graph-representation/Untitled%209.png)

<div id="adjacency-matrix-representation"></div>

## Adjacency Matrix Representation :

An adjacency matrix is a two-dimensional array that indicates which edges the graph contains. We can efficiently check from an adjacency matrix if there is an edge between two nodes. The matrix can be stored as an array :

```cpp
int adj[N][N];
```

![Untitled](/graph-representation/Untitled%2010.png)

If the graph is weighted, the adjacency matrix representation can be extended so that the matrix contains the weight of the edge if the edge exists.

![Untitled](/graph-representation/Untitled%2011.png)

<div id="edge-list-representation"></div>

## Edge List Representation :

An edge list contains all edges of a graph in some order. This is a convenient way to represent a graph if the algorithm processes all edges of the graph and it is not needed to find edges that start at a given node. The edge list can be stored in a vector :

```cpp
vector<pair<int,int>> edges;
```

where each pair (a,b) denotes that there is an edge from node a to node b.

If the graph is weighted, the structure can be extended as follows:

```cpp
vector<tuple<int,int,int>> edges;
```

Each element in this list is of the form (a,b,w), which means that there is an edge from node a to node b with weight w.

<div id="implicit-graph"></div>

## Implicit Graph :

Explicit Graph:

- All vertices are identified individually and represented separatedly.
- All edges are identified individually and represented separatedly.

Implicit Graph:

- Only a subset, possibly only one, of the vertices is given an explicit representation. (The others are implied.)
- Only a subset, and possibly zero, of the edges is given an explicit representation.
- A set of “operators” is provided that can be used to construct “new” edges and vertices.

Example of Implicit Graph:

Collatz conjecture -

- If the number is even, divide it by two.
- If the number is odd, triple it and add one.

![Untitled](/graph-representation/Untitled%2012.png)

*This process will eventually reach the number 1, regardless of which positive integer is chosen initially.*

![Untitled](/graph-representation/Untitled%2013.png)

Image Sources - Google Images, [William Fiset youtube video](https://youtu.be/09_LlHjoEiY)

What is a Graph ?

Types of Graphs

Representation of Graphs

Adjacency List Representation

Adjacency Matrix Representation

Edge List Representation

Implicit Graph

Graph Introduction and Representation


  If you've been thinking about creating a dev blog for yourself, take a look how I made it for myself.

## What is Nextjs? 🤔

[NextJS](https://nextjs.org/) is a the [React](https://reactjs.org/) framework for production. Next.js gives you the best developer experience with all the features you need for production: <i>hybrid static & server</i> rendering, <i>TypeScript</i> support, smart bundling, <i>route pre-fetching</i>, and more. No config needed.

## Contents 🔥

 - [Create new project](#create-new-project)
 - [Responsiveness](#responsiveness)
 - [Navbar](#navbar)
 - [Page routes](#page-routes)
 - [Blog setup](#blog-setup)
 - [Markdown](#markdown)
 - [Blog styling](#blog-styling)
 - [Animation](#animation)

## <div id="create-new-project">Create new project</div>

To create a project, run:

```javascript
npx create-next-app
# or
yarn create next-app
# then inside project directory
npm run dev
```
Then you will get

![nextjs homepage](/how-to-build-blog-using-nextjs/homepage.jpg)

at `localhost:3000/`.

Remove all the unwanted elements from the code and save the file. Next we will see how to figure out responsiveness of our website.

## <div id="responsiveness">Responsiveness</div>

I don't like writing CSS much. So, I started looking for some other ways to make my website responsive. So inside the hook folder, I made a hook named useMediaQuery.js.
Then inside useMediaQuery.js,
```javascript
import { useState, useCallback, useEffect } from "react";

const useMediaQuery = (width) => {
  const [targetReached, setTargetReached] = useState(false);

  const updateTarget = useCallback((e) => {
    if (e.matches) {
      setTargetReached(true);
    } else {
      setTargetReached(false);
    }
  }, []);

  useEffect(() => {
    const media = window.matchMedia(`(max-width: ${width}px)`);
    media.addEventListener("change", (e) => updateTarget(e));

    if (media.matches) {
      setTargetReached(true);
    }

    return () => media.removeEventListener(
      "change", 
      (e) => updateTarget(e)
      );
    }, []);

  return targetReached;
};

export default useMediaQuery;
``` 

So whenever I want to make any component responsive I use the following method - 
```
import React from "react";
import useMediaQuery from "../hooks/useMediaQuery";

const Component = () => {
  const breakpoint = 991;
  const size = useMediaQuery(breakpoint);
  const Desktop = ({ children }) => {
    const isDesktop = !size;
    return isDesktop ? children : null;
  };
  const NotDesktop = ({ children }) => {
    const isNotDesktop = size;
    return isNotDesktop ? children : null;
  };

  return (
    <Desktop>
      # Only visible on desktop screen
    </Desktop>
    <NotDesktop>
      # Visible only on tablet and mobile devices screen
    </NotDesktop>
  )
}

export default Component;
```


## <div id="navbar">Navbar</div>

Navbar helps us to navigate different sections of websites easily.
So to make our navbar component available on every page of our website, we have to make the following changes in the code of our `_app.js` site -

```
import Navbar from "../components/navbar.js" 
# import your navbar component
# keep rest of the code as it was.

const MyApp = ({ Component, pageProps }) => {
  return (
    <div>
      <Navbar />              #Add your navbar component here
      <Component {...pageProps} />
    </div>
  )
}

export default MyApp;
```

## <div id="page-routes">Page Routes</div>

I wanted my blog to be on a different page of the website. You can also make your about, contact, and project section on different pages of your website. For this, you just have to add components inside the pages folder, every component of the pages folder works as a route.
For example - 
```
pages
  |- index.js       #url = "/"
  |- about.js       #url = "/about"
  |- blog
      |- index.js   #url = "/blog"
  |- contact.js     #url = "/contact"
```

## <div id="blog-setup">Blog Setup</div>

Now, I want to add static blog posts to my portfolio. I started with how a blog post should start. So inside component/postDetail/postHeader.js file - 
```
function PostHeader(props) {
  const { title } = props;
  return (
    <header>
      <h1>{title}</h1>
    </header>
  );
}

export default PostHeader;
```
I will pass the title as a prop from its parent component and it will show it as a heading in every blog post.

Then, for the rest of the blog post's content, I have to render markdown code to static Html. I used the following packages for this work - 
```
npm i react-markdown
npm i rehype-raw
```
Then, inside component/postDetail/postContent.js file - 
```
import ReactMarkdown from "react-markdown";
import rehypeRaw from "rehype-raw";
import PostHeader from "./postHeader";

const PostContent = (props) => {
  const { post } = props;
  return (
    <article>
      <PostHeader title={post.title} />
      <ReactMarkdown rehypePlugins={[rehypeRaw]}>
        {post.content}
      </ReactMarkdown>
    </article>
  )
}

export default PostContent;
```
I will pass the post as a prop to the PostContent from its parent component and display post content using it. Wrapped the markdown content of post inside ReactMarkdown component and used rehpye plugin in it. This plugin will help us to recognize html inside markdown files and will help us to give id tags to headings in markdown. 

With all the code above we can show individual posts, but we also want all of our posts inside the blog section of our website with their title and some description, and the creation date.
For this, inside component/blogCard.js file - 
```
import React from 'react';
import Link from 'next/link';

const BlogCard = (props) => {
  const { title, excerpt, date, slug } = props.post;
  const formattedDate = new Date(date).toLocaleDateString(
    "en-us", 
    {
      day: "numeric",
      month: "long",
      year: "numeric",
    }
  );
  return (
    <Link href={`/blog/${slug}`}>
      <a>
        <h2>{title}</h2>
        <div>{formattedDate}</div>
        <div>{excerpt}</div>
      </a>
    </Link>
  )
}

export default BlogCard;
```

Then we have to show this card on the blog page of our website and individually for every post.
So inside blog/index.js - 
```
import BlogCard from "../../components/blogCard";
import {getAllPosts} from "../../lib/postUtils";

const Blog = (props) => {
  const {posts} = props;
  return(
    <h1>Blog</h1>
    <div>{posts.map((post) => {
        return <BlogCard key={post.slug} post={post} />
      })}
    </div>
  )
}

export function getStaticProps() {
  const allPosts = getAllPosts();
  return {
    props: {
      posts: featuredPosts,
    },
  };
}

export default Blog;
```
And inside lib/postUtils.js - 
```
import fs from "fs";
import path from "path";

import matter from "gray-matter";

const postsDirectory = path.join(process.cwd(), "posts");

export function getPostsFiles() {
  return fs.readdirSync(postsDirectory);
}

export function getPostData(postIdentifier) {
  const postSlug = postIdentifier.replace(/\.md$/, ""); // removes the file extension
  const filePath = path.join(postsDirectory, `${postSlug}.md`);
  const fileContent = fs.readFileSync(filePath, "utf-8");
  const { data, content } = matter(fileContent);

  const postData = {
    slug: postSlug,
    ...data,
    content,
  };

  return postData;
}

export function getAllPosts() {
  const postFiles = getPostsFiles();

  const allPosts = postFiles.map((postFile) => {
    return getPostData(postFile);
  });

  const sortedPosts = allPosts.sort((postA, postB) =>
    postA.date > postB.date ? -1 : 1
  );

  return sortedPosts;
}

```
Now we can start writing our blogpost in markdown inside `posts/` folder. The filename you give to your post markdown file is considered as its slug which will be visible in the post's route. Always keep in mind to give title, date, and excerpt in the following format - 
```
---
title: 'First Post'
date: '2021-06-07'
excerpt: This is my first blog post.
---
# Start writing your post content from here
```

## <div id="markdown">Markdown</div>
[Click here](https://www.markdownguide.org/basic-syntax/) to learn some basic syntax of markdown.

## <div id="blog-styling">Blog Styling</div>

You can check in the above code that I nested the blog post's content inside `<article>` tag. This tag will help us in styling our blog posts.
Inside `styles/globals.css`, if we assign some css properties to the tag present inside the article tag, it will directly reflect our blog posts.
For example - 
```
article i {
  font-family: "Sriracha", cursive;
  color: #ff0a78;
}
```
The above property will be reflected in `i` <i>tag</i>.


## <div id="animation">Animation</div>

I also added some small <u>animations</u> on my website using [Framer Motion](https://www.framer.com/api/motion/).