# DST Unit 4 – Graph and Tree questions

## Topic : Graph & Graph Traversal (Key Note and Questions)

Key Note:

• 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.

### Questions

1. What is a graph? Describe various types of graph. Briefly explain few applications of graph.
2. Discuss the various types of representation of graph.
3. Write a note on graph traversal.
4. Explain BFS graph traversal with example.
5. Explain DFS graph traversal with example.
6. Write the difference between BFS and DFS graph traversal.

## Topic : Spanning Tree (Key Note and Questions)​

Key Note:

• 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.

### Questions

1. Write a note on spanning tree and minimum spanning tree.
2. Write the Prim’s algorithm to find the minimal spanning tree.
3. Write the Kruskal’s algorithm to find minimum spanning tree.
4. Write and explain Dijkstra’s algorithm for finding shortest path.
5. Write down Warshall’s algorithm for finding shortest path . Give example.