Spanning Tree :

Spanning tree is a subgraph of a graph having all vertices but n-1 edges (n= number of vertices), so that there is no cycle formed by those edges and the graph must be connected.
Pasted image 20240504213637.png

Minimum Cost Spanning Tree :

Kruskal's Algorithm :

See video

Prim's Algorithm :

Pasted image 20240504214040.png

  • First select the 2 nodes with minimum cost. (here 1 and 6)
  • Then select the node which is connected to any node of the new graph and which has the least cost.
  • repeat the process until you have selected all the nodes.

Graph Traversal :

Breadth First Search : BFS

  • Similar to level order in binary tree. Here we may not get a binary tree but just a tree instead.
  • See RKV Sir DSA Notes

Depth First Search : DFS

  • See Video
    Pasted image 20240511135218.png
    Pasted image 20240511141041.png
Interactive Graph
Table Of Contents
Spanning Tree :
Minimum Cost Spanning Tree :
Kruskal's Algorithm :
Prim's Algorithm :
Graph Traversal :
Breadth First Search : BFS
Depth First Search : DFS