Define graph and tree data structure. Explain breadth first traversal and depth first traversal with example.
Marks: 10Chapter: Unit 10: Graphs (5Hrs)
Chapter Study
BCA Semester 3 – Data Structure and Algorithms – Unit 10: Graphs (5Hrs)
Comprehensive questions and detailed answers for Unit 10: Graphs (5Hrs). Perfect for exam preparation and concept clarity.
5
Questions
45
Marks
Define graph and tree data structure. Explain breadth first traversal and depth first traversal with example.
MediumTHEORY10 marks2019(TU FOHSS Final)
What do you mean by MST? Explain Kruskal's algorithm with example.
HardTHEORY10 marks2021(TU FOHSS Final)
Describe Prim's algorithm to solve MST problem with suitable illustration.
MediumTHEORY5 marks2022(TU FOHSS Final)
How breadth first traversal and depth first traversal can be used for traversing a graph? Explain with example. Use Dijkstra's algorithm to find the shortest path from node A to all other nodes for the following graph.
DOT
1graph G {
2 layout=neato;
3 node [shape=circle, fixedsize=true, width=0.6];
4
5 // Node positions (x,y)
6 a [pos="0,1!"];
7 b [pos="2,2!"];
8 c [pos="2,1!"];
9 d [pos="2,0!"];
10 e [pos="4,2!"];
11 f [pos="4,1!"];
12 g [pos="4,0!"];
13
14 // Edges with weights
15 a -- b [label="1"];
16 a -- c [label="10"];
17 a -- d [label="5"];
18
19 b -- c [label="6"];
20 c -- d [label="1"];
21
22 b -- e [label="1"];
23 b -- f [label="7"];
24
25 c -- f [label="8"];
26 d -- f [label="5"];
27
28 e -- f [label="2"];
29 f -- g [label="20"];
30 d -- g;
31}
32
33HardTHEORY10 marks2023(TU FOHSS Final)
Explain the different ways to represent a graph. For the following graph use Prim’s algorithm to find a minimum spanning tree stating from the node 'A':
DOT
1graph G {
2 layout=neato;
3 node [shape=circle, fixedsize=true, width=0.6];
4 a [pos="0,1!"];
5 b [pos="2,0!"];
6 c [pos="2,2!"];
7 d [pos="4,0!"];
8 e [pos="4,2!"];
9 f [pos="6,1!"];
10 a -- b [label="4"];
11 a -- c [label="6"];
12 b -- c [label="2"];
13 c -- e [label="8"];
14 b -- e [label="9"];
15 e -- d [label="4"];
16 b -- d [label="3"];
17 e -- f [label="3"];
18 d -- f [label="1"];
19}HardTHEORY10 marks2024(TU FOHSS Final)
Showing 5 questions
Sample Questions
What do you mean by MST? Explain Kruskal's algorithm with example.
Marks: 10Chapter: Unit 10: Graphs (5Hrs)
Describe Prim's algorithm to solve MST problem with suitable illustration.
Marks: 5Chapter: Unit 10: Graphs (5Hrs)
How breadth first traversal and depth first traversal can be used for traversing a graph? Explain with example. Use Dijkstra's algorithm to find the shortest path from node A to all other nodes for th
Marks: 10Chapter: Unit 10: Graphs (5Hrs)
Explain the different ways to represent a graph. For the following graph use Prim’s algorithm to find a minimum spanning tree stating from the node 'A': dot graph G { layout=neato; node [shape
Marks: 10Chapter: Unit 10: Graphs (5Hrs)