Revise Complete Graphs For Interview | C++

Revision en15, by harshiscoding, 2021-09-29 23:26:56

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



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 )



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.


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].


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.



  Rev. Lang. By When Δ Comment
en43 English harshiscoding 2022-09-03 16:10:01 36
en42 English harshiscoding 2022-09-03 16:08:44 1 Tiny change: 'SU**\n\n1. Finding th' -> 'SU**\n\n1.Finding th'
en41 English harshiscoding 2022-09-03 16:07:56 360
en40 English harshiscoding 2022-09-03 09:01:58 177
en39 English harshiscoding 2022-09-02 09:05:56 14
en38 English harshiscoding 2022-09-02 09:02:37 17
en37 English harshiscoding 2022-09-01 15:49:51 240
en36 English harshiscoding 2022-08-31 14:19:06 57
en35 English harshiscoding 2022-05-29 14:19:28 0 (published)
en34 English harshiscoding 2021-12-12 18:30:08 47
en33 English harshiscoding 2021-12-12 18:28:58 241
en32 English harshiscoding 2021-12-12 12:44:47 1008
en31 English harshiscoding 2021-12-11 22:11:56 57
en30 English harshiscoding 2021-12-11 22:08:01 190
en29 English harshiscoding 2021-12-11 21:17:12 334
en28 English harshiscoding 2021-12-11 18:51:41 18 Tiny change: 'ouble the vertices (We con' -> 'ouble the the no. of edges (We con'
en27 English harshiscoding 2021-10-02 02:07:28 38
en26 English harshiscoding 2021-10-02 02:06:13 776
en25 English harshiscoding 2021-10-02 01:31:17 88
en24 English harshiscoding 2021-10-02 01:29:02 21237
en23 English harshiscoding 2021-10-02 01:28:45 11261 Reverted to en21
en22 English harshiscoding 2021-10-02 00:57:40 11261 Reverted to en16
en21 English harshiscoding 2021-10-02 00:57:20 2367 Reverted to en9
en20 English harshiscoding 2021-10-02 00:56:37 23786 Reverted to en8
en19 English harshiscoding 2021-10-01 22:03:18 5435
en18 English harshiscoding 2021-09-30 13:26:59 2377
en17 English harshiscoding 2021-09-30 01:11:18 910
en16 English harshiscoding 2021-09-30 00:51:45 2037
en15 English harshiscoding 2021-09-29 23:26:56 2409
en14 English harshiscoding 2021-09-29 22:37:35 1295
en13 English harshiscoding 2021-09-29 22:18:17 2063
en12 English harshiscoding 2021-09-29 21:42:26 112
en11 English harshiscoding 2021-09-29 21:40:43 802
en10 English harshiscoding 2021-09-29 21:29:57 2367
en9 English harshiscoding 2021-09-29 20:39:11 2367 Tiny change: '\n==================\n' -> '\n========\n'
en8 English harshiscoding 2021-09-27 19:09:00 231
en7 English harshiscoding 2021-09-27 18:46:00 1502
en6 English harshiscoding 2021-09-27 17:14:14 138
en5 English harshiscoding 2021-09-27 17:10:22 257
en4 English harshiscoding 2021-09-27 17:08:58 228
en3 English harshiscoding 2021-09-27 17:06:13 703
en2 English harshiscoding 2021-09-27 16:42:44 15 Tiny change: 'ologies:\n\nbhbm\n==================' -> 'ologies:\n==================\n\nhvh'
en1 English harshiscoding 2021-09-27 16:41:52 90 Initial revision (saved to drafts)