Revise Complete Graphs For Interview | C++

Revision en12, by harshiscoding, 2021-09-29 21:42:26

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

Time Complexity:O(m)**** Space Complexity:**O(n*n)**

2. Adjacency List

code

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

code

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

code

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.

code

Case 2:Cycle detection in the undirected graph using BFS

code

Case 3:Cycle detection in the Directed graph using DFS

code

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

code

Check whether a graph is bipartite or not using DFS

code

History

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