Bissoy.com
Doctors Medicines MCQs Q&A

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix? Correct Answer Θ (n<sup>2</sup>)

Concept

In adjacency matrix representation, graph is represented as an “n x n” matrix.

Graph:

[ alt="F1 Raju Shraddha 10.07.2020 D1" src="//storage.googleapis.com/tb-img/production/20/07/F1_Raju_Shraddha_10.07.2020_D1.png" style="width: 157px; height: 153px;">

Then, its adjacency matrix will be

[ alt="F1 Raju Shraddha 10.07.2020 D2" src="//storage.googleapis.com/tb-img/production/20/07/F1_Raju_Shraddha_10.07.2020_D2.png" style="width: 132px; height: 138px;">

Explanation:

For performing DFS on the above graph or any adjacency matrix of a graph G, we traverse the row corresponding to that vertex. This way, we find all the adjacent vertices.

Hence, the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix is Θ (n2).

Related Questions

In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
A word is represented by only a set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered alternatively and represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example, ‘C’ can be represented by 42, 56 etc and ‘P’ can be represented by 03, 65 etc. Similarly, you have to identify the set for the word ‘THRONE’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 H D U P F 5 J C N R G 1 O S K X I 6 P V T X L 2 R E W A Z 7 E Y W A O 3 B T Q Y N 8 K H Q U I 4 J L C V G 9 B S F M D
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘A’ can be represented by 10, 75 etc and ‘B’ can be represented by 44, 79 etc. Similarly, you have to identify the set for the word ‘FOLDER’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 H L F M I 5 E I C J G 1 A U W S E 6 P R U S K 2 R Y C Z O 7 A W O D B 3 K T X V J 8 O T V Q L 4 D Q G P B 9 H N D M F
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘T’ can be represented by 02, 98 etc and ‘E’ can be represented by 12, 59, 97 etc. Similarly, you have to identify the set for the word ‘FAMILY’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 I M T K G 5 O C M R E 1 O R E Z X 6 J S F W Y 2 A G W U N 7 P I V N G 3 Q S L A H 8 L U B K W 4 J F V P B 9 H Q E T D
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘K’ can be represented by 43, 89 etc and ‘F’ can be represented by 14, 78 etc. Similarly, you have to identify the set for the word ‘SAMPLE’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 D L H O A 5 E P V J C 1 E B R L F 6 M T W R S 2 V Q W S J 7 A H O F R 3 G A P D M 8 Q R L A K 4 S N I K C 9 G B I N D
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘Q’ can be represented by 01, 69 etc and ‘W’ can be represented by 33, 77 etc. Similarly, you have to identify the set for the word ‘MODERN’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 B Q M I E 5 E K G M B 1 F V T Y G 6 I P T N Q 2 L X J A P 7 S A W V F 3 S H Z W K 8 M U R S J 4 C O U R D 9 D O L H C
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘D’ can be represented by 40, 68 etc and ‘G’ can be represented by 77, 31 etc. Similarly, you have to identify the set for the word ‘BROKE’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 J O C T M 5 M V P S A 1 P E V H Y 6 F T K D I 2 B L Q F W 7 H R G W N 3 H G A X R 8 J Z U Q B 4 D S N U K 9 O C L E H
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘A’ can be represented by 40, 04, 98 etc and ‘X’ can be represented by 23, 85 etc. Similarly, you have to identify the set for the word ‘FRIEND’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 E O T U A 5 G Q S K E 1 K W I C Z 6 Y V U D P 2 U M P X S 7 R M I Z T 3 P F Y D N 8 X T C N W 4 A R V Q K 9 O Z Q A F
A word is represented by only set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example ‘N’ can be represented by 42, 96 etc and ‘Z’ can be represented by 40, 21, 67 etc. Similarly, you have to identify the set for the word ‘MOTHER’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 Q E R T Y 5 U I O P C 1 P A S W D 6 F G Z H J 2 L Z K J H 7 L K F S D 3 W O U T I 8 D G H E M 4 Z E N Y R 9 G N J K L
A word is represented by only a set of numbers as given in any one of the alternatives. The sets of numbers given in the alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are number alternatives are represented by two classes of alphabets as shown in the given two matrices. The columns and rows of Matrix-I are numbered from 0 to 4 and that of Matrix-II are numbered from 5 to 9. A letter from these matrices can be represented first by its row and next by its column, for example, ‘Q’ can be represented by 03, 40, 59 etc and ‘C’ can be represented by 11, 78 etc. Similarly, you have to identify the set for the word ‘COPPER’.  Matrix I    Matrix II   0 1 2 3 4   5 6 7 8 9 0 A H W Q I 5 N S K G Q 1 B C D L F 6 M R F T O 2 J G K O P 7 J W P C L 3 E F A Z R 8 E I M Z J 4 Q I J N B 9 C H A U D