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:
Time Complexity:O(m)**** Space Complexity:**O(n*n)**
2. Adjacency List
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
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
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.
Case 2:Cycle detection in the undirected graph using BFS
Case 3:Cycle detection in the Directed graph using DFS-
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.
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
Check whether a graph is bipartite or not using DFS
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.
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.