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

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