Bipartite graphs
- If a graph has no cycle or even length cycle then it is Bipartite if cycle length is odd it is not Bipartite
- If a graph can be colored using 2 colors such that adjacent nodes have different color then we can say that it is Bipartite
- Formal definition :
A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of same set
Using BFS
- Just do simple bfs and intead of taking a visited array we can take color [ ] and initialise it with -1 and then on traversing each node fill it with either of the 2 colors 0 or 1
- While traversing adjacent nodes of a node , if the color of the adjacent node is -1 that means it is not traversed so simply fill it with opposite color of that of its adjacent(parent/(prev) whatever you might call it
color[adjacent]=1-color[parent];
// 1-0 = 1 and 1-1=0- if the color of the adjacent node is not -1 then check its color if opposite colors then its fine but if both have dame colors return false;
bool bfs(vector<vector<int>>& adj,vector<int> &color,int start)
{
queue<int> q;
q.push(start);
color[start]=0; // we can start with any of the 2 colors 0/1
while(q.size()>0)
{
int curr=q.front();
q.pop();
for(auto it: adj[curr])
{
if(color[it]==-1) // if adjacent is not colored, color it
{ // with opposite color
color[it]=1-color[curr]; // 1->0 or 0->1
q.push(it);
}
else if(color[it]==color[curr])
return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& adj) {
int v=adj.size();
vector<int> color(v,-1);
for(int i=0;i<v;i++)
{
if(color[i]==-1)
{
if(bfs(adj,color,i)==false) // if any of the component is not bipartite
return false; // then the whole graph is not bipartite
}
}
return true;
}Using DFS
Same concept as before
bool dfs(int node, vector<int> adj[], int color[]) {
for(auto it : adj[node]) {
if(color[it] == -1) {
color[it] = 1 - color[node];
if(!dfs(it, adj, color)) {
return false;
}
} else if(color[it] == color[node]) return false;
}
return true;
}
bool checkBipartite(vector<int> adj[], int n) {
int color[n];
memset(color, -1, sizeof color);
for(int i = 0;i<n;i++) {
if(color[i] == -1) {
color[i] = 1;
if(!dfs(i, adj, color)) {
return false;
}
}
}
return true;
}Topological Sort
Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG
By topologically sorting we sort all the vertices according to their finish time
Using DFS
- We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of the stack.
- Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in the stack.
void dfs(int start, vector<bool> &vis, stack<int> &st, vector<int> adj[]) {
vis[start] = true;
for(auto it : adj[start]) {
if(!vis[it]) {
dfs(it, vis, st, adj);
}
}
st.push(start);
}
vector<int> topoSort(int N, vector<int> adj[]) {
stack<int> st;
vector<int> vis(N, 0);
for(int i = 0;i<N;i++) {
if(vis[i] == false) {
findTopoSort(i, vis, st, adj);
}
}
// just print the stack
vector<int> topo;
while(!st.empty()) {
topo.push_back(st.top());
st.pop();
}
return topo;
}Topological sort using BFS :
Kahn’s Algo
- Keep removing the vertex with degree =0 and print them and at the same time delete thier corresponding edges i.e decreasing the indegree by one for all the neighbours of the nodes with indegree=0
Code:
vector<int> topoSort(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);
}
}
vector<int> ans;
while(!q.empty()) {
int curr = q.front();
q.pop();
ans.push_back(curr);
for(auto it : adj[curr]) {
indegree[it]--;
if(indegree[it] == 0) {
q.push(it);
}
}
}
return ans;
}Note : 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. We can check that if we want ..here we assumed that topological sort was possible
Cycle Detection in Directed Graph using BFS(Kahn’s Algorithm)
- Exactly same as code as above just maintain a “count” variable to count no of elements in the topological sort
- If count==no of vertexes return true else return false
bool topoSort(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 count=0;
while(!q.empty()) {
int curr = q.front();
q.pop();
count++;
for(auto it : adj[curr]) {
indegree[it]--;
if(indegree[it] == 0) {
q.push(it);
}
}
}
return count==N;
}Shortest Path in Directed Acyclic Graph from single source to all nodes
1) Initialize dist[] = {INF, INF, ….} and dist[s] = 0 where s is the source vertex.
2) Create a toplogical order of all vertices.
3) Do following for every vertex u in topological order.
………..Do following for every adjacent vertex v of u
………………if (dist[v] > dist[u] + weight(u, v))
………………………dist[v] = dist[u] + weight(u, v)
Code : (topological order using bfs) :
Note: For Adjcency List we’ll be needing a an array of vector<pair<int,int>>
#include <bits/stdc++.h>
#define INF INT_MAX
using namespace std;void addEdge(vector <pair<int, int> > adj[], int u,
int v, int wt)
{
adj[u].push_back(make_pair(v, wt));
}
void TopoSortShortestDist(int source, int N, vector<pair<int,int>> adj[])
{
queue<int> q;
vector<int> indegree(N, 0);
for(int i = 0;i<N;i++) {
for (auto it = adj[i].begin(); it!=adj[i].end(); it++)
{
indegree[it->first]++;
}
}
for(int i = 0;i<N;i++) {
if(indegree[i] == 0) {
q.push(i);
}
}
vector<int> topo;
while(!q.empty()) {
int curr = q.front();
q.pop();
topo.push_back(curr);
for(auto it = adj[curr].begin(); it!=adj[curr].end(); it++) {
int x=it->first;
indegree[x]--;
if(indegree[x] == 0) {
q.push(x);
}
}
}
// topo[ ] contains topological order of the nodes
vector<int> dist(N,10000); // INT_MAX or 10000
dist[source]=0;
for(int i=0;i<topo.size();i++)
{
if(dist[i]!=10000)
{
for(auto it: adj[i])
{
if(dist[i]+it.second < dist[it.first])
dist[it.first]=dist[i]+it.second;
}
}
}
for(int i=0;i<N;i++)
{
cout<<"Dist from "<<i<<" is ";
if(dist[i]==10000)cout<<"INFINITY"<<endl;
else cout<<dist[i]<<endl;
}
}int main()
{
int n=6, m=9; // n nodes & m edges
vector<pair<int, int> > adj[n];
addEdge(adj,0, 1, 5);
addEdge(adj,0, 2, 3);
addEdge(adj,1, 3, 6);
addEdge(adj,1, 2, 2);
addEdge(adj,2, 4, 4);
addEdge(adj,2, 5, 2);
addEdge(adj,2, 3, 7);
addEdge(adj,3, 4, -1);
addEdge(adj, 4, 5, -2);// assuming source=1
TopoSortShortestDist(1, n, adj);return 0;
}
Using topological sort (dfs)
void dfs(int node, int vis[], stack<int> &st, vector<pair<int,int>> adj[]) {
vis[node] = 1;
for(auto it : adj[node]) {
if(!vis[it.first]) {
dfs(it.first, vis, st, adj);
}
}
st.push(node); // stack stores our topological sort
}void 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 it : adj[node]) {
if(dist[node] + it.second < dist[it.first]) {
dist[it.first] = dist[node] + it.second;
}
}
}
}for (int i = 0; i < N; i++)
(dist[i] == 1e9)? cout << "INF ": cout << dist[i] << " ";
}
