Revise Complete Graphs For Interview | C++

Revision en20, by harshiscoding, 2021-10-02 00:56:37

Basic terminologies:

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.

There are two ways to represent a graph

  1. Adjacency matrix:

adj[i][j] represents there is an edge from node i to j.

int n, m;
cin >> n >> m; 	
// declare the adjacent matrix 
int adj[n+1][n+1]; 
// take edges as input 
for(int i = 0;i<m;i++) {
int u, v; 
cin >> u >> v;
adj[u][v] = 1; 
adj[v][u] = 1; //write this line only if the graph is undirected 
}

Time Complexity:**O(m)**

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

  1. Adjacency List
cin >> n >> m; 

	// declare the adjacent matrix 
	vector<vector<int>> adj[n+1]; 
	vector<int> adj[n+1]; 

	// take edges as input 
	for(int i = 0;i<m;i++) {
	    int u, v; 
	    cin >> u >> v;
	    adj[u].push_back(v); 
	    adj[v].push_back(u); 
	}
	return 0;
}

Time Complexity:**O(m)**

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

If there are also weights in edges we create the adjacency list like vector <vector < pair <int,int> > > where first value is node and second value represents weight b/w the nodes.

Since there can be multiple components in a graph, for graph traversal we have to call BFS/DFS from every unvisited node, but to avoid repetition we will store information if a node is visited by creating a boolean array where is_visited[i]==true represents node 'i' is visited.

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 undirected graph using DFS

If a node adjacent to a node is already visited except the adjacent node is its parent, the component contains a cycle.

Cycle detection in the undirected graph using BFS

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