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;
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);
}