Revise Complete Graphs For Interview | C++

Revision en21, by harshiscoding, 2021-10-02 00:57:20

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

code

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

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

# Check whether a graph is bipartite or not using BFS

A graph will not be a bipartite iff it has a cycle with odd no. of nodes.

#### History

Revisions

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