Unit 4 Long answer Important Questions of Data Structure
graph ? Discuss various types of graphs. Briefly explain few applications of
Q2: What is
graph ? Discuss various terminologies used in graph.
Q3: Discuss the
various types of representation of graph.
adjacency multi lists.
Q5: Write a
short note on graph traversal.
*Q6: Write and
Explain DFS graph traversal algorithm.
algorithm to traverse a graph. Apply same algorithm for the graph given in Fig.
by considering node 1 as starting node.
BFS algorithm to find the shortest path form node A to J.
detail about the graph traversal techniques with suitable example.
the importance of various traversing techniques in graph along with its
connected component and strongly connected component. Write an algorithm to find strongly connected components.
Q10: What do you
mean by spanning tree and minimum spanning tree ?
Q11: Write down
Prim’s algorithm to find out minimal spanning tree.
minimum spanning tree. Find the minimal spanning tree for the following graph
using Prim’s algorithm.
Kruskal’s algorithm to find minimum spanning tree.
the following undirected graph.
a. Find the adjacency list
representation of the graph.
b. Find the minimum cost spanning tree
by Kruskal’s algorithm.
*Q14: Find the
minimum spanning tree for the following graph using
Prim’s and Kruskal’s algorithm.
Prim’s and Kruskal’s algorithm. Construct minimum spanning tree for the below given graph using Prim’s algorithm. (Source node =a)
Q17: Write down
Warshall’s algorithm for finding all pair shortest path.
*Q18: Write the
Floyd Warshall algorithm to compute the all pair shortest path. Apply the algorithm on following graph.
Q19: Write and
explain Dijkstra’s algorithm for finding shortest path.
Write and explain an algorithm for
finding shortest path between
any nodes of a given graph.
*Q20: Find out
the shortest path from node 1 to 4 in a given graph using Dijkstra shortest path algorithm.
Dijkstra’s algorithm for finding shortest path. Describe its working for the graph given below.
Describe Dijkstra algorithm with
*Q22: By considering vertex ‘1’ as source vertex, find the shortest paths to all other vertices in the
following graph using Dijkstra’s
algorithm. Show all the steps.