## 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

- What is a graph? Describe various types of graph. Briefly explain few applications of graph.
- Discuss the various types of representation of graph.
- Write a note on graph traversal.
- Explain BFS graph traversal with example.
- Explain DFS graph traversal with example.
- 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

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