Table of contents
- BFS
- DFS
- GET PATH- BFS
- Find all connected components in an undirected graph
- Detect cycle in undirected graph -DFS
- Detect cycle in undirected graph -BFS
- Clone a connected undirected graph Graph - DFS
- Clone a connected undirected graph Graph - BFS
- Topological Sorting a Directed Graph- DFS
- Topological Sorting a Directed Graph -BFS (KAHNS AlGO)
- Detect cycle in a Directed Graph (BFS- KAHNS ALGO)
- Detect Cycle in a Directed Graph -DFS
- Bipartite Check DFS
- Bipartite Check BFS
- Find all "Strongly" connected components in a Directed graph- KOSARAJUS ALGO
- Find All Cut vertices and Bridges in a Directed Graph- TARJANS ALGO
- Find all "Strongly" connected components in a Directed graph- TARJANS ALGO
- Disjoint Set | Union by Rank | Union by Size | Path Compression
- Kruskals Algorithm for Finding Minimum Spanning Trees in undirected graphs
- Prims Algorithm
- Dijkstra's Algorithm
- Bellman Ford Algorithm
- FLOYD WARHSHALL (DP)
- Notes
BFS
BFS (Breadth-First Search):
Introduction: BFS explores nodes in layers, starting from the root node and moving level by level through adjacent nodes.
Applications:
Shortest path problems in unweighted graphs. In an unweighted undirected graph, Breadth-First Search (BFS) is guaranteed to find the shortest path between any two nodes.
Finding connected components in an undirected graph.
Clone a connected undirected graph.
Bipartite checking in graphs.
Detecting cycles in undirected graphs.
int main() {
int v,e;
cin>>v>>e;
int** adjMat=new int*[v];// this can even be boolean
for(int i=0;i<v;i++)
adjMat[i]=new int[v]();
for (int i = 0; i < e; i++) {
int sv,ev; cin>>sv>>ev;
adjMat[sv][ev]=1;
adjMat[ev][sv]=1;// an undirected Graph
}
vector<bool> visited(v,false);
for(int i=0;i<v;i++){
if(!visited[i]){// handling for disconnted graphs
queue<int> pendingNodes;
pendingNodes.push(i);
visited[i]=true;
while (!pendingNodes.empty()) {
int thisv=pendingNodes.front();
cout<<thisv<<" ";
pendingNodes.pop();
for(int j=0;j<v;j++){
if(i!=j && adjMat[thisv][j] && !visited[j]){
visited[j]=true;
pendingNodes.push(j);
}
}
}
}
}
return 0;
}
DFS
Introduction: DFS explores as far as possible along each branch before backtracking.
Applications:
Topological sorting in directed graphs.
Detecting cycles in directed and undirected graphs.
Bipartite checking in graphs.
Find all strongly connected components in a directed graph.
void dfs(int sv,int v,int** adjMat,vector<bool>& visited){
visited[sv]=true;
cout<<sv<<" ";
for(int i=0;i<v;i++){
if(i!=sv && adjMat[sv][i] && !visited[i])
dfs(i, v, adjMat, visited);
}
}
int main() {
int v,e;
cin>>v>>e;
int** adjMat=new int*[v];
for(int i=0;i<v;i++)
adjMat[i]=new int[v]();
for (int i = 0; i < e; i++) {
int sv,ev; cin>>sv>>ev;
adjMat[sv][ev]=1;
adjMat[ev][sv]=1;// an undirected Graph
}
vector<bool> visited(v,false);
for(int i=0;i<v;i++){
if(!visited[i])
dfs(i,v,adjMat,visited);
}
return 0;
}
GET PATH- BFS
Description: It refers to finding the path between two nodes using BFS.
Applications:
- Shortest path problems in unweighted graphs.
vector<int> getpathbfs(int** adjMat,int V,int E,int s,int e){
vector<int> ans;
queue<int> pendingnodes;
vector<bool> visited(V,false);
pendingnodes.push(s);
unordered_map<int, int> m;//child-> parent
bool pathFound=false;
while (!pendingnodes.empty()) {
int sv=pendingnodes.front();
visited[sv]=true;
pendingnodes.pop();
if(adjMat[sv][e]){// checking direct edge
m.insert({e,sv});
pathFound=true;
break;
}
// checking indierect edges
for(int i=0;i<V;i++){
if(i!=sv && adjMat[sv][i]==1 && !visited[i]){
pendingnodes.push(i);
m.insert({i,sv});// child is mapped to parent
}
}
}
if(pathFound){
ans.push_back(e);
while(m.find(e)!=m.end()){
ans.push_back(m[e]);// parent of e
e=m[e];// parent's parent need to be found now ,
// so parent becomes new child
if(e==s)break;
}
}
return ans;
}
Find all connected components in an undirected graph
void dfs(vector<int>* adjList,int sv,int n,set<int>* component,vector<bool>& visited){
visited[sv]=true;
component->insert(sv);
for(auto& adjV:adjList[sv]){
if(!visited[adjV])
dfs(adjList, adjV, n, component, visited);
}
}
set<set<int>*>* getComponenets(vector<int>* adjList,int n){
vector<bool> visited(n,false);
set<set<int>*>* output=new set<set<int>*>();
for(int i=0;i<n;i++){
if(!visited[i]){
set<int>* component=new set<int>();
dfs(adjList,i,n,component,visited);
output->insert(component);
}
}
return output;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,m; cin>>n>>m;
vector<int>* adjList=new vector<int>[n];// array of vectors-ADjList
for(int i=0;i<m;i++){
int sv,ev; cin>>sv>>ev;
adjList[sv].push_back(ev);
adjList[ev].push_back(sv);
}
set<set<int>*>* components=getComponenets(adjList,n);
for(auto setPointer:*components){
for(auto & setElement:*setPointer)
cout<<setElement<<" ";
cout<<endl;
}
delete components;
return 0;
}
Detect cycle in undirected graph -DFS
Find a node that is visited and not the parent
(Perform DFS whilst checking if you encounter a node that is already visited -provided it's not the current vertexes parent)
bool hasCycle(int sv,int parentV,vector<int>* adjList,int n,int m,vector<bool>& visited){
visited[sv]=true;
for(auto adjacentv:adjList[sv]){
if(visited[adjacentv] && adjacentv!=parentV) return true;
if(!visited[adjacentv])
if(hasCycle(adjacentv, sv, adjList, n, m, visited)) return true;
// return hasCycle(adjacentv, sv, adjList, n, m, visited) XXXX -DONT DO THIS MISTAKE
}
return false;
}
string cycleDetection (vector<vector<int>>& edges, int n, int m){
// taking the edges and forming an adjaceny list
vector<int>* adjList=new vector<int>[n+1];// n vertices and m edges
// edges are 1 indexed
for(auto& edge:edges){
adjList[edge[0]].push_back(edge[1]);
adjList[edge[1]].push_back(edge[0]);
}
vector<bool> visited(n+1,false);
for(int i=1;i<=n;i++)// handling for disconnected graphs
if(!visited[i])
if(hasCycle(i,-1,adjList,n,m,visited)) return "Yes";
return "No";
}
Detect cycle in undirected graph -BFS
Find a node that is visited and not the parent
(Perform BFS whilst checking if you encounter a node that is already visited -provided it's not the current vertexes parent, we can use a similar to GET-PATH-BFS and maintain a map of child->parent, but an even better approach would be to store parent with each element in the queue itself )
#include<bits/stdc++.h>
string cycleDetection (vector<vector<int>>& edges, int n, int m){
// taking the edges and forming an adjaceny list
vector<int>* adjList=new vector<int>[n+1];// n vertices and m edges
// edges are 1 indexed
for(auto& edge:edges){
adjList[edge[0]].push_back(edge[1]);
adjList[edge[1]].push_back(edge[0]);
}
vector<bool> visited(n+1,false);
for(int i=1;i<=n;i++)
if(!visited[i]){
queue<pair<int, int>> pendingNodes;// bfsQ
pendingNodes.push({i,-1});
visited[i]=true;
while (!pendingNodes.empty()) {
pair<int, int> child_parent=pendingNodes.front();
pendingNodes.pop();
int sv=child_parent.first;
int parentv=child_parent.second;
for(auto adjacentv:adjList[sv]){
if(visited[adjacentv] && adjacentv!=parentv) return "Yes";
if(!visited[adjacentv]){
visited[adjacentv]=true;
pendingNodes.push({adjacentv,sv});
}
}
}
}
return "No";
}
Clone a connected undirected graph Graph - DFS
Maintain a reference to the clone
// Definition for a Graph Node.
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}
Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
We do the DFS on the original whilst maintaining a refs to the clone
When we visit each node we create clones simultaneously
class Solution {
public:
unordered_map<Node*, Node*> myClone;
void clone(Node* node,vector<bool>& visited){
if(node==nullptr) return;
visited[node->val]=true;
Node* cloneNode=new Node(node->val);
myClone[node]=cloneNode ;
for(auto adjNode:node->neighbors){//iterating over original neighbours
if(!visited[adjNode->val])
clone(adjNode, visited);// Induction Step: "give me clones"
cloneNode->neighbors.push_back(myClone[adjNode]);
//Induction Hypothesis: "i have the clones and now i handle"
}
}
Node* cloneGraph(Node* node) {
//Given a reference of a node in a connected undirected graph.
// each node's value is the same as the node's index (1-indexed)
//The given node will always be the first node with val = 1
//-> we can infer from the above statement that all node vals are uniq
vector<bool> visited(101,false);//1 <= Node.val <= 100
clone(node,visited);
return myClone[node];
}
};
Clone a connected undirected graph Graph - BFS
Maintain a reference to the clone
We do the BFS on the original whilst maintaining a refs to the clone
When we visit each node we create clones simultaneously
class Solution {
public:
Node* cloneGraph(Node* node) {
//Given a reference of a node in a connected undirected graph.
// each node's value is the same as the node's index (1-indexed)
//The given node will always be the first node with val = 1
//-> we can infer from the above statement that all node vals are uniq
vector<bool> visited(101,false);//1 <= Node.val <= 100
unordered_map<Node*, Node*> myClone;
if(node==NULL) return node;
queue<Node*> pendingNodes;
pendingNodes.push(node);
visited[node->val]=true;// we infer node values are uniq
myClone[node]=new Node(node->val);
//When we visit each node we create clone simultaneously
while (!pendingNodes.empty()) {
Node* thisNode=pendingNodes.front();
pendingNodes.pop();
for(auto& adjNode: thisNode->neighbors){
if(!visited[adjNode->val]){
visited[adjNode->val]=true;
myClone[adjNode]=new Node(adjNode->val);
pendingNodes.push(adjNode);
}
myClone[thisNode]->neighbors.push_back(myClone[adjNode]);
}
}
return myClone[node];
}
};
Topological Sorting a Directed Graph- DFS
Push in stack when DFS is exhausted
Topological sorting of DAG is a linear ordering of vertices such that for every directed edge from vertex u to vertex v, vertex u comes before v in the ordering. Topological sorting for a graph is not possible if the graph is not a DAG.
We just run a simple DFS, we push every vertex in the stack after DFS is exhausted
void dfs(vector<int>* adjList,vector<bool> &visited,stack<int> &st,int sv){
visited[sv]=true;
for(int v:adjList[sv])
if(!visited[v])
dfs(adjList, visited, st, v);
st.push(sv);// push every vertex in the stack after DFS is exhausted
}
vector<int> topologicalSort(vector<vector<int>> &edges, int v, int e) {
vector<int>* adjList=new vector<int>[v];
for(int i=0;i<e;i++)
adjList[edges[i][0]].push_back(edges[i][1]);// Directed Acyclic Graph
vector<bool> visited(v,false);
stack<int> st;
for(int i=0;i<v;i++)
if(!visited[i])
dfs(adjList,visited,st,i);
vector<int> ans;
while(!st.empty()){
ans.push_back(st.top());
st.pop();
}
return ans;
}
Topological Sorting a Directed Graph -BFS (KAHNS AlGO)
We create an in-degree array, which has in-degress for all the verticesWe seed the queue (an approach similar to the Rotting oranges problem) with all vertices with in-degree as zeroStart the BFS and in each iteration, the vertex we get is the subsequent vertex in the correct topo sort ordering- reduce the indegrees of neighbours (as we are emulating removing these vertices and edges one by one )
vector<int> topologicalSort(vector<vector<int>> &edges, int v, int e) {
vector<int>* adjList=new vector<int>[v];
for(int i=0;i<e;i++)
adjList[edges[i][0]].push_back(edges[i][1]);// Directed Acyclic Graph
vector<int> indegree(v,0);// calculating indegrees of each vertex
for(int i=0;i<v;i++)
for(int v:adjList[i])
indegree[v]++;
queue<int> pendingNodes;
for(int i=0;i<v;i++)
if(indegree[i]==0)
pendingNodes.push(i);
vector<int> ans;
while(!pendingNodes.empty()){
int temp=pendingNodes.front(); pendingNodes.pop();
ans.push_back(temp);
for(int vrtx:adjList[temp]){
indegree[vrtx]--;
if(indegree[vrtx]==0)
pendingNodes.push(vrtx);
}
}
return ans;
}
Kahn's algorithm is primarily used to find a topological ordering of nodes in a Directed Acyclic Graph (DAG) and also to detect cycles in directed graphs.
Using the BFS approach for top sorting is better as it can even detect if a graph is not a DAG, in which no topo-sort sequence exists for it in the first place
It does not directly detect if a graph is not a DAG; instead, it identifies cycles within a graph, and if it finds any, it indicates that the graph is not a DAG.
If, during the execution of Kahn's algorithm, you encounter a situation where no nodes with in-degree 0 are available to be processed, it means that there are nodes with unmet dependencies, indicating the presence of cycles in the graph. This is the point where you can conclude that the graph is not a DAG.
Detect cycle in a Directed Graph (BFS- KAHNS ALGO)
During kahns if all vertices do not enter the queue exactly once - we have a cycle
int detectCycleInDirectedGraph(int n, vector < pair < int, int >> & edges) {
vector<int>* adjList=new vector<int>[n];
for(int i=0;i<edges.size();i++)
adjList[edges[i].first-1].push_back(edges[i].second-1);// Directed Acyclic Graph
vector<int> indegree(n,0);// calculating indegrees of each vertex
for(int i=0;i<n;i++)
for(int v:adjList[i])
indegree[v]++;
queue<int> pendingNodes;
for(int i=0;i<n;i++)
if(indegree[i]==0)
pendingNodes.push(i);
int visitedNodes=0;
vector<int> ans;
while(!pendingNodes.empty()){
int temp=pendingNodes.front(); pendingNodes.pop();
visitedNodes++;
ans.push_back(temp);
for(int vrtx:adjList[temp]){
indegree[vrtx]--;
if(indegree[vrtx]==0)
pendingNodes.push(vrtx);
}
}
if(visitedNodes==n) return false;
return true;
}
Detect Cycle in a Directed Graph -DFS
Apart from the visited array take one more array that is marked unvisited when DFS completes and we backtrack, IFF for any node you see a node which is visited and visited in the same DFS iteration, then you find a cycle
Notice we don’t need a parent array for this as that case is also handled by the second visited array - but we need that for undirected graphs
bool hasCycle(vector<int>* adjList,vector<bool>& visited, vector<bool>& visitedInSameDfs,int sv){
visited[sv]=true;
visitedInSameDfs[sv]=true;
for(int v:adjList[sv]){
if(visited[v] && visitedInSameDfs[v])
return true;
if(!visited[v])
if(hasCycle(adjList, visited, visitedInSameDfs, v)) return true;
// DO NOT DO THE MISTAKE OF return f(adList...) here, we want loop to continue
}
visitedInSameDfs[sv]=false;
return false;
}
int detectCycleInDirectedGraph(int n, vector < pair < int, int >> & edges) {
vector<int>* adjList=new vector<int>[n];
for(int i=0;i<edges.size();i++)
adjList[edges[i].first-1].push_back(edges[i].second-1);// Directed Acyclic Graph
vector<bool> visited(n,false);
vector<bool> visitedInSameDfs(n,false);
for(int i=0;i<n;i++)
if(!visited[i])
if(hasCycle(adjList,visited,visitedInSameDfs,i))
return true;
return false;
}
Bipartite Check DFS
Simply do a DFS and keep assigning opposite colors to neighbours
class Solution {
public:
bool dfs(vector<vector<int>>& graph,vector<int> &color,int sv,int thiscolor){
color[sv]=thiscolor;
for(int adj:graph[sv]){
if(color[adj]==-1){
if(!dfs(graph, color, adj, thiscolor^1))return false;// neighbour assigned opposite color
}else if(color[adj]==thiscolor){
return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
// graph is actually adjList
int v=graph.size();
vector<int> color(v,-1);//doubling as visited array
//node is numbered between 0 and v - 1.
for(int x=0;x<v;x++){
if(color[x]==-1)
if(!dfs(graph,color,x,0)) return false;// do not do the mistake of return dfs() here
}
return true;
}
};
Bipartite Check BFS
simply do a BFS and assign neighbours opposite colors
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
// graph is actually adjList
int v=graph.size();
vector<int> color(v,-1);//doubling as visited array
queue<int> pendingNodes;
//node is numbered between 0 and v - 1.
for(int x=0;x<v;x++){
if(color[x]==-1){
color[x]=0;
pendingNodes.push(x);
while(!pendingNodes.empty()){
int v=pendingNodes.front();pendingNodes.pop();
for(int adjacent:graph[v]){
if(color[adjacent]==-1){
color[adjacent]=color[v]^1;
pendingNodes.push(adjacent);
}else if (color[adjacent]==color[v]){
return false;
}
}
}
}
}
return true;
}
};
Find all "Strongly" connected components in a Directed graph- KOSARAJUS ALGO
TopoSort + transpose matrix + Start DFS again (go to all unvisited vertices ) picking from stack-top
A strongly connected component is a subset of vertices within a directed graph where every vertex is reachable from every other vertex within that subset
In other words, for any pair of vertices u and v within the SCC, there exist directed paths from u to v and from v to u.
SCCs are particularly relevant in directed graphs because they capture the idea of strong connectivity, where not only can you reach a vertex from another, but you can also return to the starting vertex by following directed edges.
Algorithms like Tarjan's algorithm or Kosaraju's algorithmare commonly used to find strongly connected components in directed graphs.
Start DFS from any node which you find un-visited iterativelyJust like topo sort, push vertex in the stack when dfs is exhausted for that particular vertex (although this is exactly the same as dfs topo sort please understand that this is NOT a DAG and may very well have cycles)Reverse all edges in the graph (or maintain this at the time of input itself)- take transposePick from the top of the stack and if that element is unvisited -start a dfs in the transposed graph in which this vertex has start - You will encounter SCC vertices in each iteration
void dfs1(vector<int>* adjList,vector<bool> &visited,stack<int> &st,int sv){
visited[sv]=true;
for(int v:adjList[sv])
if(!visited[v])
dfs1(adjList, visited, st, v);
st.push(sv);
}
void dfs2(vector<int>* &adjList,vector<bool> &visited,vector<int> &ans,int sv){
visited[sv]=true;
ans.push_back(sv);
for(int v:adjList[sv])
if(!visited[v])
dfs2(adjList, visited, ans, v);
}
vector<vector<int>> stronglyConnectedComponents(int n, vector<vector<int>> &edges){
vector<int>* adjList=new vector<int>[n];
vector<int>* adjListT=new vector<int>[n];// transposed adjacecny List
for(int i=0;i<edges.size();i++){
int a=edges[i][0]; int b=edges[i][1];
adjList[a].push_back(b);// Directed Acyclic Graph
adjListT[b].push_back(a);// transpose graph
}
vector<bool> visited(n,false);
stack<int> st;
for(int i=0;i<n;i++)
if(!visited[i]) dfs1(adjList,visited,st,i);
for(int i=0;i<visited.size();i++)
visited[i]=false;
vector<vector<int>> allSCC;
while (!st.empty()) {
int sv=st.top();
if(!visited[sv]){
vector<int> scc;
dfs2(adjListT,visited,scc,sv);
allSCC.push_back(scc);
}
st.pop();
}
return allSCC;
}
Find All Cut vertices and Bridges in a Directed Graph- TARJANS ALGO
When we backtrack we update our low value from neighbours' low value, when we see an already visited node we update our low value from neighbours' discovery value
Articulation Point (Cut Vertex): It's a vertex in a connected graph. Removing it along with its incident edges increases the number of disconnected components by at least 1.
Bridge (Cut Edge): It's an edge in a connected graph. Removing it increases the number of disconnected components.
Relationship: An articulation point can be thought of as a vertex connected to at least one bridge. Removing the articulation point removes these bridges, and therefore, the two concepts are related in connected graphs.
TARJANS ALGO
Create two arrays
Discovery array: Assign a number to the vertex, 1...n in order of DFS reach
Low array: See the discovery array, If you ignore the original DFS path i.e. remove it -what is the node with the lowest discovery number you can touch?
We start DFS,now updating discovery and parent is very straightforward forward in DFS we have to see neighbours and update the low array accordingly, while doing DFS we encounter three types of nodes
Parent Node: cannot update low array as low array is found by ignoring the original path -which will always include parent vertex, so for this neighbour, nothing is to be done
Not parent and visited: If the visited node has a lower value of discovery, you may update your low value with its discovery value.
Not parent and unvisited: We called DFS on it and when we backtrack from the call we update our low value with its low value.
NOTE: When we backtrack from the DFS call we update with the neighbour node's low value, but when its already visited we update with the neighbour node'sdiscovery valuethis is because we are not sure that the low value this visited neighbour is using was found by a path which different/same or even crosses our current path
If for any vertex sv, you find a neighbour v whose low value is greater or equal to your discovery value - you find an articulation point
If you see for a neighbour the low value (lowest discovery value node it can reach of original path is ignored) is greater or equal to your own discovery value it means that it has no other way to reach the nodes "behind" you (nodes having lower discovery values than you ) it clearly means that this vertex is an articulation point
NOTE : We cannot do articulation point ++ and count articulation points when we encounter this condition as we would count the same single articulation time multiple times for multiple bridges
This algorithm doesn't work for the actual source directly as it has the lowest discovery value which can't be reduced further, so according to our algo it will always be an articulation point - which it is not. So for source only we count the DFS calls, if you have >=2 calls from src its surely a cut vertex
If for any vertex sv, you find a neighbour v whose low value is strictly greater than your discovery value - you find a Bridge
// LC: https://leetcode.com/problems/critical-connections-in-a-network/
class Solution {
public:
vector<vector<int>> bridges;
void dfs(int sv,int parent,int time,vector<int>* adjList,vector<bool>& visited,vector<int> &discovery,vector<int> &low,vector<bool> &isArticulationPoint){
visited[sv]=true;
discovery[sv]=time;
low[sv]=discovery[sv];
int dfscallsfromSourceVertex=0;// if you have >=2 calls from src its surely a cut vertex
for(int v:adjList[sv]){
if(v==parent) continue;
if(visited[v]) low[sv]=min(low[sv],discovery[v]);
else{
dfs(v,sv,time+1,adjList, visited, discovery, low, isArticulationPoint);
dfscallsfromSourceVertex++;
low[sv]=min(low[sv],low[v]);// when we backtrack we are updating low from low
if(parent==-1){
if(dfscallsfromSourceVertex>=2) isArticulationPoint[sv]=true;
}else
if(low[v]>=discovery[sv]) isArticulationPoint[sv]=true;// cut vertex condidtion
if(low[v]>discovery[sv]) bridges.push_back({sv,v});// bridge condition
}
}
}
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
vector<int>* adjList=new vector<int>[n];
for(vector<int> edge:connections){
adjList[edge[0]].push_back(edge[1]);
adjList[edge[1]].push_back(edge[0]);
}
vector<bool> visited(n,false);
vector<int> discovery(n,-1);
vector<int> low(n,-1);// lowest discovery time for each vertex
vector<bool> isArticulationPoint(n,false);// for each vertex is it articulation point ?
for(int i=0;i<n;i++)
if(!visited[i])
dfs(i,-1,0,adjList,visited,discovery,low,isArticulationPoint);
/* Print all cut vertices
for(int i=0;i<n;i++)
if(isArticulationPoint[i]) cout<<i<<" ";
cout<<endl;
**/
return bridges;
}
};
Find all "Strongly" connected components in a Directed graph- TARJANS ALGO
same SCC === same low link value for a special kind of DFS
src: https://youtu.be/ZeDNSeilf-Y?t=1237
Apart from the usual discovery and low arrays we maintain two more data structures a stack and a boolean array which signifies an element is in the stack or not
As usual, we do DFS and when we backtrack from DFS we update our low value from the low value of the neighbour but we only update from the discovery value of the neighbour when the neighbour is both visited and present in the stack (earlier (in tarjans) we directly updated our low value from neighbours discovery value when the neighbour was visited)
Note: This stack is used for the same purpose we maintain a second visited queue while finding cycles in directed graphs using DFS
If during DFS we find a node with the low value == discovery value , it signifies start of an SCC , with it being the last member from this scc on the stack - so we pop stack until this node is popped and all these removed elements from a single SCC
int t = 1;
void dfs(vector<vector<int>> &adjList, int node, vector<int> &disc, vector<int> &low, vector<bool> &inStack, stack<int> &nodeStack, vector<vector<int>> &allScc){
disc[node] = t;
low[node] = disc[node];
t++;
nodeStack.push(node);
inStack[node] = true;
for (int v : adjList[node]){
if (disc[v] == -1){
dfs(adjList, v, disc, low, inStack, nodeStack, allScc);
low[node] = min(low[node], low[v]);
} else {
if (inStack[v]) // visited and is in stack
low[node] = min(low[node], disc[v]);
}
}
if (low[node] == disc[node]){// this node is the start of an SCC and its surely somehere down the stack
vector<int> scc;
while (true) {
int v=nodeStack.top();
nodeStack.pop();
inStack[v]=false;
scc.push_back(v);
if(v==node){
allScc.push_back(scc);
break;
}
}
}
}
vector<vector<int>> stronglyConnectedComponents(int n, vector<vector<int>> &edges){
vector<vector<int>> allScc;
vector<vector<int>> adjList(n);
for (vector<int> &edge : edges)
adjList[edge[0]].push_back(edge[1]);
vector<int> disc(n, -1);// doubling as visited array for dfs
vector<int> low(n, -1);
stack<int> nodeStack;
vector<bool> inStack(n, false);
for (int i = 0; i < n; i++)
if (disc[i] == -1)
dfs(adjList, i, disc, low, inStack, nodeStack, allScc);
return allScc;
}
Disjoint Set | Union by Rank | Union by Size | Path Compression
Take two arrays a rank array (only needed if you are doing union by rank) and a parent array, rank is initialised to zero and each vertex assigns the parent to its value (signifies each node right now is a separate component)We do the union of each of the vertex pairs firstIf we are doing naive union, we just find the ultimate parents of each and make any one parent of the othervoid union(int u, int v) { u = findPar(u); v = findPar(v); parent[u] = v; // Attach u's tree to v's tree }If we are doing union by rank size, the vertex with the strictly higher rank becomes the parent if ranks are equal we make any one parent but remember to increase its rankvoid unionByRank(int u, int v) { u = findPar(u); v = findPar(v); if (u != v) { if (rank[u] < rank[v]) { parent[u] = v; } else if (rank[u] > rank[v]) { parent[v] = u; } else { parent[u] = v; rank[v]++; } } }
We pick any pair of vertices and find the ultimate parents of each, If they are the same these vertices belong to the same component and different components otherwise
int findPar(int u) { if (parent[u] == u) { return u; } return parent[u] = findPar(parent[u]); },
Allows us to find if two vertices are in the same component or not in constant time (DFS/BFS would take O(V+E))
class DisjointSet { public: DisjointSet(int n) { parent.resize(n); for (int i = 0; i < n; ++i) parent[i] = i; rank.resize(n, 0); } int findUltimateParent(int u) { if(u==parent[u]) return u; return parent[u] = findUltimateParent(parent[u]); // Path compression } void unionSets(int u, int v) { u = findUltimateParent(u); v = findUltimateParent(v); if (u != v) { if (rank[u] < rank[v]) { parent[u] = v;// stritly higher rank becomes parent } else if (rank[u] > rank[v]) { parent[v] = u; } else { parent[v] = u;// make any one parent but remeber to increase its rank rank[u]++; } } } private: vector<int> parent; vector<int> rank; }; int main() { int n; // Number of vertices int m; // Number of edges cin >> n >> m; DisjointSet dsu(n); // Input edges for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; dsu.unionSets(u, v); } int q; // Number of queries cin >> q; for (int i = 0; i < q; ++i) { int u, v; cin >> u >> v; if (dsu.findUltimateParent(u) == dsu.findUltimateParent(v)) { cout << "Yes, they are in the same component." << endl; } else { cout << "No, they are in different components." << endl; } } return 0; }
Kruskals Algorithm for Finding Minimum Spanning Trees in undirected graphs
Repeatedly adds the edge with the smallest weight that does not create a cycle.
A Minimum Spanning Tree (MST) is a subset of edges in a connected, undirected graph that connects all the vertices together with the minimum possible total edge weight while forming a tree (i.e., no cycles)
Several algorithms can find the Minimum Spanning Tree of a graph:
Kruskal's Algorithm: Kruskal's algorithm is a greedy algorithm that starts with an empty set of edges and repeatedly adds the edge with the smallest weight that does not create a cycle. This process continues until all vertices are included, resulting in an MST.
Prim's Algorithm: Prim's algorithm is another greedy algorithm that starts with an arbitrary vertex and repeatedly adds the minimum-weight edge connecting a vertex in the current MST to a vertex outside the MST until all vertices are included.
Chu-Liu/Edmonds Algorithm: This algorithm is used to find the Minimum Spanning Arborescence in a directed graph. It's an extension of MST algorithms for directed graphs where each vertex has a single parent.
class Edge{
public:
int source,destination,weight;
Edge(){
this->source=-1;
this->destination=-1;
this->weight=-1;
}
Edge(int s,int d,int w){
this->source=s;
this->destination=d;
this->weight=w;
}
};
void printMST(Edge mstEdges[],int V){
for(int i=0;i<V-1;i++){
if(mstEdges[i].source<=mstEdges[i].destination)
cout<<mstEdges[i].source<<" "<<mstEdges[i].destination<<" "<<mstEdges[i].weight<<endl;
else
cout<<mstEdges[i].destination<<" "<<mstEdges[i].source<<" "<<mstEdges[i].weight<<endl;
}
}
bool wayToSort(Edge e1,Edge e2){ return e2.weight > e1.weight; }// Sort in increading order of weight
int getParent(int* parent,int v){
if(parent[v]==v)return v;
return parent[v]=getParent(parent,parent[v]);
}
int main(){
int V, E;
cin >> V >> E;
Edge inputEdges[E];
Edge mstEdges[V-1];// our MST as this would always have v-1 edges
for(int i=0;i<E;i++){
int s,d,w;
cin>>s>>d>>w;
inputEdges[i]=Edge(s,d,w);
}
sort(inputEdges,inputEdges+E,wayToSort);
int parent[V];
for(int i=0;i<V;i++)parent[i]=i;//UNION FIND
int rank[V];
for(int i=0;i<V;i++)rank[i]=0;//Union by rank
int count=0;
for(int i=0;count<V-1;i++){// V vertices so V-1 edges in MST
// for every edge ---v1 and v2 cheak if p1!=p2 ---if p1=p2 skip edge
int v1=inputEdges[i].source;
int v2=inputEdges[i].destination;
int p1=getParent(parent,v1);
int p2=getParent(parent,v2);
if(p1==p2)continue;// they lie in the same component-joining them will cause loop
else{
int r1=rank[p1], r2=rank[p2];
// higher rank becomes the parent
if(r1>r2) parent[p2]=p1;
else if(r2>r1) parent[p1]=p2;
else{// choose any one parent but make sure its rank is increased now
parent[p1]=p2;
rank[p2]++;
}
mstEdges[count]=inputEdges[i];
count++;
}
}
printMST(mstEdges,V);
return 0;
}
Prims Algorithm
Pick a vertex as source, and maintain three arrays, a parent array, a weights array for every vertex and a visited array
We pick the unvisited vertex with minimum weight in every iteration. (in kruskals we picked the edge with minimum weight )
We explore all neighbours of the source which are unvisited, if the current weight of that node is more than the weight assigned by your path, update it and also make the current node a parent
In the end, the vertex and parent array give all vertices and parents of MST
#include<bits/stdc++.h>
using namespace std;
int findMinVertex(bool* visited,int* weight,int V){
// Find the unvisited vertex with minimum weight
int x=INT_MAX;
int vrtx=-1;
for(int i=0;i<V;i++)
if(weight[i]<x && !visited[i]){
x=weight[i];
vrtx=i;
}
return vrtx;
}
void prims(int** adjMat,int V){
bool* visited=new bool[V];
int* parent=new int[V];
int* weight=new int[V];
for(int i=0;i<V;i++){
visited[i]=false;
weight[i]=INT_MAX;
}
parent[0]=-1;
weight[0]=0;
for(int i=0;i<V;i++){
int vrtx=findMinVertex(visited,weight,V);
visited[vrtx]=true;
for(int i=0;i<V;i++)
if(i!=vrtx && adjMat[vrtx][i]!=0 && !visited[i])
if(adjMat[vrtx][i]<weight[i]){
weight[i]=adjMat[vrtx][i];
parent[i]=vrtx;
}
}
for(int i=1;i<V;i++){
if(i<parent[i])
cout<<i<<" "<<parent[i]<<" "<<weight[i]<<endl;
else
cout<<parent[i]<<" "<<i<<" "<<weight[i]<<endl;
}
}
int main(){
int V,E;
cin >> V >> E;
int** adjMat=new int*[V];
for(int i=0;i<V;i++){
adjMat[i]=new int[V];
for(int j=0;j<V;j++)
adjMat[i][j]=0;
}
for(int i=0;i<E;i++){
int v1,v2,w;
cin>>v1>>v2>>w;
adjMat[v1][v2]=w;
adjMat[v2][v1]=w;
}
prims(adjMat,V);
for(int i=0;i<V;i++)
delete [] adjMat[i];
delete [] adjMat;
return 0;
}
Dijkstra's Algorithm
Shortest Path: Dijkstra's Algorithm is primarily used to find the shortest path from a source node to all other nodes in a weighted graph. It's particularly useful in scenarios where you need to find the optimal path, such as in GPS navigation, network routing, and transportation logistics.
Single-Source Shortest Path: It can be adapted to find the shortest path from a source node to a specific target node by terminating the algorithm once the target node is reached.
Limitations of Dijkstra's Algorithm:
Positive Weighted Edges: Dijkstra's Algorithm assumes that all edge weights in the graph are non-negative. If the graph contains negative edge weights, the algorithm may produce incorrect results.
Net Negative Cycles: It cannot handle graphs with negative weight cycles. If such cycles exist, the algorithm can enter an infinite loop or produce incorrect results.
Non-Greedy: Dijkstra's Algorithm uses a greedy approach by selecting the node with the smallest tentative distance at each step. This means it may not work correctly in scenarios where a global optimization is required, such as finding the shortest path in graphs with negative weights.
Alternative Algorithms:
Bellman-Ford Algorithm: The Bellman-Ford Algorithm can handle graphs with negative edge weights and negative cycles, making it more versatile than Dijkstra's Algorithm. However, it has a higher time complexity of O(V*E), where V is the number of vertices and E is the number of edges.
A\ Algorithm:* A* is used for finding the shortest path in graphs, but it employs a heuristic to guide the search. It combines elements of Dijkstra's Algorithm and greedy search, making it more efficient than Dijkstra's Algorithm in many cases.
Floyd-Warshall Algorithm: This algorithm finds the shortest paths between all pairs of nodes in a graph. It can handle graphs with both positive and negative edge weights, but it has a time complexity of O(V^3), which can be inefficient for large graphs.
Algorithm
Pick a vertex as a source, and maintain two arrays, a distances array for every vertex and a visited array
We pick the unvisited vertex with minimum distances in every iteration.
We explore all neighbours of the source which are unvisited, if the current distance of that node is more than the distance assigned by your path, update it
In the end distance array contains all the single source shortest paths
#include<iostream>
#include<algorithm>
#include<climits>
using namespace std;
int pickVertexWithMinDistance(bool* visited,int* distance,int V){
//unvisited vertex with min distance
int vrtx=-1;
for(int i=0;i<V;i++)
if(!visited[i] &&(vrtx==-1 || distance[i]<distance[vrtx] ))
vrtx=i;
return vrtx;
}
void dijkstras(int** adjMat,int V){
bool* visited=new bool[V];
int* distance =new int[V];
for(int i=0;i<V;i++){
visited[i]=false;
distance[i]=INT_MAX;
}
distance[0]=0;
for(int i=0;i<V;i++){
int vrtx=pickVertexWithMinDistance(visited,distance,V);
visited[vrtx]=true;
for(int j=0;j<V;j++){
int newDistance= distance[vrtx]+adjMat[vrtx][j];
if(adjMat[vrtx][j] && !visited[j] && newDistance < distance[j])
distance[j]=newDistance;
}
}
for(int i=0;i<V;i++){
cout<<i<<" "<<distance[i]<<endl;// Single souce shortest path
}
delete [] visited;
delete [] distance;
}
int main() {
int V,E;
cin >> V >> E;
int** adjMat=new int*[V];
for(int i=0;i<V;i++){
adjMat[i]=new int[V];
for(int j=0;j<V;j++)
adjMat[i][j]=0;
}
for(int i=0;i<E;i++){
int v1,v2,w;
cin>>v1>>v2>>w;
adjMat[v1][v2]=w;
adjMat[v2][v1]=w;
}
dijkstras(adjMat,V);
for(int i=0;i<V;i++)
delete [] adjMat[i];
delete [] adjMat;
return 0;
}
Bellman Ford Algorithm
We repeatedly "relax" each edge for V-1 times, as the longest path itself will contain V-1 edges at max
This "relax" mechanism is the same as that of Dijstras, for V-1 times for each edge (u,v, weight) , if d[u]+weight < d[v] ———> dv=d[u]+w
Applied to Directed Graphs(to apply to undirected you will have to convert to directed) -may have negative weights
Can detect a net negative cycle, Same purpose as Djkstras otherwise
As this runs on edges -it is ideal for sparse graphs, by will give a bad performace of O(VE) as compared to (E+V)logV for Dijkstras
Do the above step one more time, if any update happens - a net negative cycle exits
int bellmonFord(int n, int m, int src, int dest, vector<vector<int>> &edges) {
// Finds distance from src to all paths
vector<int> dist(n+1,1e9);
dist[src]=0;
bool hasNegCycle=false;
for(int i=0;i<n;i++){// i am relaxing n times , the last one just for cycle check
for(vector<int> edge:edges){
int u=edge[0],v=edge[1],w=edge[2];
if(dist[u]!=1e9 && dist[u]+w<dist[v]){
if(i==n-1){
hasNegCycle=true; break;
}
dist[v]=dist[u]+w; }
}
}
return hasNegCycle? -1:dist[dest];
}
FLOYD WARHSHALL (DP)
All pair shortest path, again works for negative weights and detects net negative weights cycles
Earlier algos were single source shortest path - this is ALL pair shortest path! - You may pick any pair of vertices
Floyd-Warshall algorithm can detect the presence of negative cycles in a graph. It does so by detecting negative values along the main diagonal of the distance matrix after the algorithm has run. If there is a negative value in the diagonal, it indicates the existence of at least one negative cycle in the graph.
int floydWarshall(int n, int m, int src, int dest, vector<vector<int>> &edges) {
// Finds min distance b/w each and every pair of vertices
// Note: vertices are labelled [1,N]
vector<vector<int>> dist(n+1,vector<int>(n+1,1e9));
bool hasNetNegCycle=false;
for(int i=1;i<=n;i++) dist[i][i]=0;
for(vector<int> edge:edges){
int u=edge[0],v=edge[1],w=edge[2];
dist[u][v]=w;
}
for(int intermNode=1;intermNode<=n;intermNode++){//first vertex is label 1
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dist[i][intermNode]==1e9 || dist[intermNode][j]==1e9) continue;
int suggested=dist[i][intermNode]+dist[intermNode][j];
dist[i][j]=min(dist[i][j],suggested);
}
if(dist[i][i]<0){ hasNetNegCycle=true; break;}
}
}
return hasNetNegCycle? -1: dist[src][dest];
}
Notes
- Types of edges in graphs
Eulerian Path is a path in a graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path that starts and ends on the same vertex.
A Spanning Tree is a path that visited every vertex exactly once.
Shortest path in a grid with Obstacle elimination - When ever shortest path is mentioned in a grid consider BFS