DST Unit 4 – Graph and Tree questions

A Graph is a non-linear data structure that consist nodes and edges.
Two nodes are connected with the help of single edge.
Graph data structure can be represented using Adjacency Matrix and Adjacency List.
BFS stands for Breadth First Search is a Graph traversal Algorithm.
DFS stands for Depth First Search is also a Graph traversal algorithm.

Q1). What is a graph? Describe various types of graph. Briefly explain few applications of graph.
Q2). Discuss the various types of representation of graph.
Q3). Write a note on graph traversal.
Q4). Explain BFS graph traversal with example.
Q5). Explain DFS graph traversal with example.
Q6). Write the difference between BFS and DFS graph traversal.
Q7). Illustrate the importance of various traversing techniques in graph along with its application.

A spanning tree is a subset of any Graph G that contains all vertices minimum possible number of edges.
Spanning tree does not have any cycle as well as it is not disconnected.
Minimum spanning tree is a subset of graph that contains all vertices and the sum of edge weight that are connecting to vertices is minimum.
Prim’s and Kruskal Algorithm is used to find minimum spanning tree.

Q1). Write a note on spanning tree and minimum spanning tree.
Q2). Write the Prim's algorithm to find the minimal spanning tree.
Q3). Define spanning tree. Find the minimal spanning tree for the following graph using Prim's algorithm.
Q4). Write the Kruskal's algorithm to find minimum spanning tree.
Q5). Explain the time complexity of Prim's and Kruskal algorithm.
Q6). Write a note on path matrix.
Q7). How path matrix can be determined ? Explain the method.
Q8). Write and explain Dijkstra's algorithm for finding shortest path.
Q9). Write down Warshall's algorithm for finding shortest path . Give example.
Q10). Write a note on activity network.