Vertices,edges,undirected and directed graph,cyclic & acyclic graph,degree indegree & outdegree and weights. In an undirected graph, the sum of degrees of all vertices is double the vertices (We consider degree=indegree=outdegree in an undirected graph).
Graph representation in C++
Let us say there are n nodes and m edges. And adj[i][j] represents there is an edge from node i to j.
There are two ways to represent a graph
1. Adjacency matrix:
code
int n, m;
cin >> n >> m;
int adj[n+1][n+1]; //1 based indexing
for(int i = 0;i<m;i++) {
int u, v;
cin >> u >> v;
adj[u][v] = 1;
adj[v][u] = 1; //write this line only if the graph is undirected
}
Time Complexity:O(m)**** Space Complexity:**O(n*n)**
2. Adjacency List
codeint n,m;
cin >> n >> m;
vector<vector<int> > adj(n+1);
for(int i = 0;i<m;i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u); //undirected graph
}
return 0;
}
Time Complexity:**O(m)** Space Complexity:**O(n*n)**
If there are also weights in edges, we create the adjacency list as ' vector <vector < pair <int,int> > > ' where first value is node(v) and second value represents weight b/w the nodes(u and v).
Since there can be multiple disconnected components in a graph, while graph traversal we have to call BFS/DFS from every unvisited node. To avoid repetition we store information if a node is visited or not by creating a boolean array where is_visited[i]==true represents node 'i' is visited.
for(int i=1i<=n;i++)
{
if(!is_visited[i]) BFS(i);
}
BFS
codefor(int i=0;i<n;i++)
{
if(!vis[i])
{
queue<int> q;
q.push(i);
vis[i] = 1;
while(!q.empty())
{
int node = q.front();
q.pop();
cout<<node<<" ";
for(auto child : adj[node])
{
if(!vis[child])
{
q.push(child);
vis[child] = 1;
}
}
}
}
}
Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)
Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for queue )
DFS
codevoid dfs(int node, vector<bool> &vis,vector <vector <int> > &adj)
{
cout<<node<<" ";
vis[node]=1;
for(auto child : adj[node])
{
if(!vis[child])
{
dfs(child,vis,adj);
}
}
}
//Inside main()
for(int i = 1;i<=V;i++)
{
if(!vis[i])
dfs(i, vis, adj);
}
Time Complexity:**O(n+e)** ( O(n+e): n time taken for visiting n nodes and e time taken for traversing through adjacent nodes)
Space Complexity:**O(n)** ( O(n) for visiting array and O(n) for stack space )
Cycle Detection in Graphs
Case 1: Cycle detection in undirected graph using dfs
If a node adjacent to a node ( that is not its parent node ) is already visited, the component contains a cycle.
codebool checkForCycle_DFS(int node, int parent, vector<int> &vis, vector <vector<int> > &adj)
{
vis[node] = 1;
for(auto child:adj[node])
{
if(vis[child]&&child!=parent) return true;
if(!vis[child])
{
if(checkForCycle_DFS(child, node, vis, adj)) return true;
}
}
return false;
}
//Inside main()
for(int i = 0;i<n;i++)
{
if(!vis[i])
{
if(checkForCycle_DFS(i, -1, vis, adj)) return true;
}
}
return false;
Case 2:Cycle detection in the undirected graph using BFS
codecheckCycle_BFS(int node, int parent, vector<bool> &vis, vector <vector<int> > &adj)
{
vis[i]=1;
queue<pair <int,int> > q;
q.push({i,-1});
while(!q.empty())
{
int node = q.front().first;
int parent=q.front().second;
q.pop();
for(auto child : adj[node])
{
if(vis[child]&&child!=parent) return true;
if(!vis[child])
{
q.push({child,node});
vis[child] = 1;
}
}
}
return false;
}
//Inside main()
for(int i=0;i<n;i++)
{
if(!vis[i])
{
if(checkCycle_BFS(i,-1,vis,adj)) return true;
}
}
return false;
Case 3:Cycle detection in the Directed graph using DFS-
codebool checkForCycle_DFS(int node, int parent, vector<int> &color, vector <vector<int> > &adj)
{
color[node] = 1;
for(auto child:adj[node])
{
if(color[child]==1&&child!=parent) return true;
if(!color[child])
{
if(checkForCycle_DFS(child, node, color, adj)) return true;
}
}
color[node]=2;
return false;
}
//Inside main()
for(int i = 0;i<n;i++)
{
if(!vis[i])
{
if(checkForCycle_DFS(i, -1, vis, adj)) return true;
}
}
return false;
Case 3:Cycle detection in the Directed graph using BFS
Assume the directed graph to be acyclic i.e. DAG and find its topological order.If we can do topological sorting i.e. pushing all nodes in queue , the graph is acyclic,other wise it is cyclic.
We increase our count by 1 (starting from 0) each time we push a node in queue. And if final value of count==no. of nodes in graph, the graph is a DAG.
code//The given code is for one component graph.
//You can find topological order for multiple component graph using vis array.
bool isCyclic(int N, vector<int> adj[])
{
queue <int> q;
vector <int> indegree(N, 0);
for(int i = 0;i<N;i++)
{
for(auto it: adj[i])
indegree[it]++;
}
for(int i = 0;i<N;i++)
{
if(indegree[i] == 0)
q.push(i);
}
int cnt = 0;
while(!q.empty())
{
int node = q.front();
q.pop();
cnt++;
for(auto it : adj[node])
{
indegree[it]--;
if(indegree[it] == 0)
q.push(it)
};
}
if(cnt == N) return false;
return true;
}
Bipartite graph:
A graph will not be a bipartite iff it has a cycle with an odd no. of nodes.
Check whether a graph is bipartite or not using BFS
codebool bipartiteBFS(int src, vector <vector<int> > &adj, int color[])
{
color[src] = 1;
queue<int> q;
q.push(src);
while(!q.empty())
{
int node = q.front();
q.pop();
for(auto child : adj[node])
{
if(color[child] == color[node])
{
return false;
}
else if(color[child] == -1)
{
color[child] = 1 - color[node];
q.push(child);
}
}
}
return true;
}
//Inside main()
for(int i = 0;i<n;i++)
{
if(color[i] == -1)
{
if(!bipartiteBFS(i, adj, color)) return false;
}
}
return true;
Check whether a graph is bipartite or not using DFS
codebool bipartiteDfs(int node, vector <vector<int> > &adj, int color[])
{
for(auto child : adj[node])
{
if(color[child] == color[node]) return false;
else if(color[child] == -1)
{
color[child] = 1 - color[node];
if(!bipartiteDfs(child, adj, color))
{
return false;
}
}
}
return true;
}
//Inside main()
for(int i = 0;i<n;i++)
{
if(color[i] == -1)
{
color[i] = 1;
if(bipartiteDfs(i, adj, color)==false) return false;
}
}
return true;
Topological Sorting:
Only possible in DAG. It is a linear order of vertices such that for every directed edge u-->v, vertex u comes before v in that order. A DAG has at least one node with indegree=0.
Topological sorting using BFS
First, calculate indegree of all nodes and store it in vector.Then push all nodes with degree==0 in a queue.Take each node one by one out of queue and for all its child ,decrease their indegree by 1. After this if any child has indegree==0, push them in the queue.
code//The given code is for one component graph.
//You can find topological order for multiple component graph by calling this func for every unvisited node.
vector<int> findTopo(int N,vector < vector <int> > &adj)
{
vector<int> indegree(N, 0);
for(int i = 0;i<N;i++)
for(auto it: adj[i])
indegree[it]++;
queue<int> q;
for(int i = 0;i<N;i++)
{
if(indegree[i] == 0) q.push(i);
}
vector<int> topo;
while(!q.empty())
{
int node = q.front();
q.pop();
topo.push_back(node)
for(auto child : adj[node])
{
indegree[child]--;
if(indegree[child] == 0)
q.push(child);
}
}
return topo;
}
Topological sorting using DFS
Topological order is the order of nodes in decreasing order of finishing time i.e. the node that gets finished at last comes first in order.
code//The given code is for one component graph.
//You can find topological order for multiple component graph by calling this func for every unvisited node.
void findTopoSort(int node, vector<int> &vis, stack<int> &st, vector<int> adj[])
{
vis[node] = 1;
for(auto it : adj[node])
{
if(!vis[it])
findTopoSort(it, vis, st, adj);
}
st.push(node);
}
Shortest path algorithms:
Shortest path of all nodes from a node in a uni-weighted undirected graph.
Use BFS for this because BFS visits nodes in a sequential manner. That is nodes at the same level are visited simultaneously. Run BFS and equate dist[node] = 1+dist[parent].
codevoid BFS(vector<int> adj[], int N, int src)
{
int dist[N];
dist[src] = 0;
for(int i = 1;i<N;i++) dist[i] = INT_MAX;
queue<int> q;
q.push(src);
while(q.empty()==false)
{
int node = q.front();
q.pop();
for(auto it:adj[node])
{
//no use of vis array because if a dist[node] is relaxed,
//it implies it is being visited first time.
if(dist[node] + 1 < dist[it])
{
dist[it]=dist[node]+1;
q.push(it);
}
}
}
for(int i = 0;i<N;i++) cout << dist[i] << " ";
}
Shortest path of all nodes from a node in a weighted DAG
The weights can be -ve.
Minimum sum to reach a node 'v' i.e. dist[v] is minimum of all (dist[u]+weight(u-->v)),where u is node from all its parents. Similarly, dist[u] is calculated with the help of its parents.We can observe that ultimately we have to start calculating dist[] from source node and in topological order ,we have to visit the nodes
We visit nodes in topological order and relax all its children. In this way, each node is relaxed by all its parents.
codevoid shortestPath(int src, int N, vector<pair<int,int>> &adj)
{
int vis[N] = {0};
stack<int> st;
for (int i = 0; i < N; i++)
if(!vis[i])
findTopoSort(i, vis, st, adj);
int dist[N];
for (int i = 0; i < N; i++)
dist[i] = 1e9;
dist[src] = 0;
while(!st.empty())
{
int node = st.top();
st.pop();
if (dist[node] != INF)
{
for(auto child : adj[node])
{
if(dist[node] + .second < dist[child.first])
dist[child.first] = dist[node] + child.second;
}
}
}
for (int i = 0; i < N; i++)
(dist[i] == 1e9)? cout<< "INF ": cout << dist[i] << " ";
}
Shortest path in +ve weighted graph.
Dijkstra's algorithm is basically an efficient version of breadth-first search on a different graph.
Given a graph G with positive integer edge-weights, one could construct a new unweighted graph H, by replacing each weighted edge with a number of edges equivalent to its weight. So, for example, if you had an edge (u,v) with weight 10 in G, you'd replace this edge with a series of 10 edges between u and v.
Since BFS visits nodes in increasing order of their level (distance from source node) i.e. at any point of time,if a node n1 level is smaller than node n2, minimum distance from n1 will be calculated earlier than n2.
From this, we get an intuition that at any point of time, calculate minimum distance of children of that node which is nearest to the source node. This is a kind of greedy approach because we are relaxing children of that node which is locally(at a point of time) nearest to the source.
Since min_priority_queue always stores elements in increasing order,we will use it.We can also use set instead of it.
codetypedef pair<int, int> pi;
vector <int> dijkstra(int n,vector<vector<pi>> &adj, int s)
{
priority_queue<pi, vector<pi>, greater<pi> > pq;
//min heap (weight,node)
vector <int> dist(n);
for(int i=0; i<n; i++) dist[i]=1e9;
dist[s]=0;
pq.push({dist[s], s});
while (!pq.empty())
{
int u=pq.top().second;
pq.pop();
for(auto p: adj[u])
{
int v=p.first;
int w=p.second;
if(dist[u] + w < dist[v])
{
dist[v] =dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
Why Dijkstra doesn't work with -ve weights:
If all weights are non-negative, adding an edge can never make a path shorter but this is not valid if edge weight is -ve.Dry run a case to explain it further.
Bellman Ford
Since the negative weighted cycle has sum — infinity, Bellman-Ford works in a directed graph iff the graph has no -ve weighted cycle and works in an undirected graph iff all weights are non -ve.
Relax all edges n-1 times.Why exactly n-1 times.Since in each relaxation,in worst case,only one node will get relaxed and maximum distance of a node from source node is n-1. Consider example 1-->2-->3-->4-->5. First 5 is relaxed,then 4 and so on till 2 ,n-1 times.
code// dp[i] = shortest distance to node i
// dp[i] = INFINITY for all
dp[s]= 0 ;
for ( int i= 1 ; i<=n -1 ; i++)
{
for ( auto e: edges)
{
int u=e.first;
int v=e.second.first;
int w=e.second.second;
if (dp[u]+w <dp[v])
dp[v]=dp[u]+w;
}
}
DSU
It is a data structure used to perform the union of disjoint sets efficiently.Each node in the set has parent.
Representative node:Topmost node of a set whose parent is the node itself.
Naive Implementation:
codevoid make_set ( int n)
{
for ( int i= 0 ; i<n; i++)
{
par[i]=i;
}
}
int find_set (int x)
{
if ( par[x] == x)
return x;
return find_set(par[x]);
}
int union_set(int a,int b)
{
int p1=find_set(a),p2=find_set(b);
//ensuring both nodes are not belonging to same set
if(p1!=p2)
par[p1]=p2;
}
Time complexity:O(n) for make_set and O(d) for find_set() and union_set() where d=maximum depth possible of a node.
To reduce time complexity of find_set() and union_set(),we have to decrease depth.This can be possible if a parent has maximum children possible.
We can do this by doing modification in find_set() and union_set():
For finding representative node a node using find_set(), we will be traversing to its parent, grandfather and so on... . While traversing, we make a representative node,the parent of each node traversed.
While merging two sets, we make the smaller-sized set child of the larger-sized set to ensure minimum depth. (visualize why so, by a diagram). To know the size of the set, we have to maintain an array ,where rnk[i] tells the size of the set treating 'i' as representative node.
codevoid make_set (int n)
{
for (int i= 0 ; i<n; i++)
{
par[i] = i;
rnk[i] = 1 ;
}
}
//While traversing ,we make representative node ,the parent of each node traversed.
int find_set ( int x)
{
if ( par[x] == x)
return x;
par[x]=find_set(par[x]);
return par[x];
}
void union_set ( int a, int b)
{
int p1 = find_set(a);
int p2 = find_set(b);
if ( p1 == p2)
return ;
if (rnk[p1] > rnk[p2])
{
par[p2]=p1;
rnk[p1] = rnk[p1] + rnk[p2];
}
else
{
par[p1] = p2;
rnk[p2] = rnk[p1] + rnk[p2];
}
}
Time complexity :O(1)
( Using path compression in find_set() alone reduces time complexity to O (log N)approximately. And time Complexity of find_set() and union_set(), when you use both path compression and union by rank: O( α(N) ) where α(N) = Inverse Ackermann Function which is approximately equal to O(1). )
Minimum Spanning Tree:
A spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. Thus it has n nodes and n-1 edges. A single graph can have many different spanning trees.
A minimum spanning tree (MST) for a weighted, connected, undirected graph is a spanning tree with sum of the weight of its all edges is less than or equal to the weight of every other spanning tree.
Sort all edges in increasing order and keep including the edge only if the edge is not making a cycle. This is greedy approach because we are trying to make globally minimum weight by selecting locally minimum weighted edge.To join to edges ,we use DSU operations,union_set and find_set.
code
struct node
{
int u,v,w;
node(int first, int second, int weight)
{
u = first,v = second, wt = weight;
}
};
bool comp(node a, node b)
{
return a.wt < b.wt;
}
int find_set(int u, vector<int> &parent)
{
if(u == parent[u]) return u;
return parent[u] = find_set(parent[u], parent);
}
void union_set(int u, int v, vector<int> &parent, vector<int> &rank)
{
u = find_set(u, parent);
v = find_set(v, parent);
if(rank[u] < rank[v])
{
parent[u] = v;
rank[u]+=rank[v];
}
else
{
parent[v] = u;
rank[v]+=rank[u];
}
}
int main()
{
int N,m;
cin >> N >> m;
vector<node> edges;
for(int i = 0;i<m;i++)
{
int u, v, wt;
cin >> u >> v >> wt;
edges.push_back(node(u, v, wt));
}
sort(edges.begin(), edges.end(), comp);
vector<int> parent(N);
for(int i = 0;i<N;i++)
parent[i] = i;
vector<int> rank(N, 0);
int cost = 0;
vector<pair<int,int>> mst;
for(auto it : edges)
{
if(find_set(it.v, parent) != find_set(it.u, parent))
{
cost += it.wt;
mst.push_back({it.u, it.v});
unionn(it.u, it.v, parent, rank);
}
}
cout << cost << endl;
for(auto it : mst) cout << it.first << " - " << it.second << endl;
return 0;
}
Finding Strongly Connected Component(SCC)
SCC of a directed graph is a subgraph such that ∃ a path b/w every pair of vertices of the subgraph. (In undirected graph,each component is a SCC.)
Brute Force: Find distance b/w every pair of vertices using floyd warshall algo.Take a node say 1 and push all nodes 'i' where dist[1][i]!=INF in a vector.For nodes pushed take all pairs say (i,j) and delete if the dist[i][j]==INF. Repeat this process. TC:O(N^3).
Kosaraju Algo
Intiution
If we consider a SCC as one node ,the graph formed will be DAG.
If we reverse the direction of all edges of graph i.e. take transpose of graph ,the SCCs remain the same.
For transpose of a DAG,if we visit nodes in topological order,for one DFS call from main(),only one node will be visited because there will be no outdegree. (source node has become sink node.)
Steps:
Find topological sorting of graph .
Find reverse of graph
Run DFS in topological order of graph.
code
void dfs(int node, stack<int> &topo, vector<int> &vis, vector < vector<int> > &adj)
{
vis[node] = 1;
for(auto it: adj[node])
{
if(!vis[it])
{
dfs(it, topo, vis, adj);
}
}
topo.push(node);
}
void revDfs(int node, vector<int> &vis, vector <vector <int> >transpose,vector<int> &component)
{
vis[node] = 1;
component.push_back(node);
for(auto it: transpose[node])
{
if(!vis[it])
revDfs(it, vis, transpose,component);
}
}
vector <vector<int> > findSCCs(int n,vector <vector<int> > &adj)
{
//Step-1:Find topo order
stack<int> topo;
vector<bool> vis(n, 0);
for(int i = 0;i<n;i++)
{
if(!vis[i]) dfs(i, topo, vis, adj);
}
//Step 2:Making transpose of graph
vector <vector<int> > transpose;
for(int i = 0;i<n;i++)
{
vis[i] = 0;
for(auto it: adj[i]) {
transpose[it].push_back(i);
}
}
//Step 3: DFS on transpose in topological order
vector <vector<int> > SCCs;
while(!st.empty())
{
int node = st.top();
st.pop();
if(!vis[node])
{
vector <int> component;
component.clear();
revDfs(node, vis, transpose,component);
SCCs.push_back(component);
}
}
return adj;
}