KEMBAR78
Module 4 Graphs - Bfs Dfs | PDF
Scribd
Upload
26 views16 pages

Module 4 Graphs - Bfs Dfs

Uploaded by

n3004dsouza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
26 views16 pages

Module 4 Graphs - Bfs Dfs

Uploaded by

n3004dsouza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

MODULE-04

DATA STRUCTURES
GRAPHS
Three Sample Graph
GRAPH ABSTRACT DATA TYPES
BFS & DFS
Cont..
Example:
BFS
DFS
Spanning Trees
Spanning tree – sub graph of G(V,E) with no cycles.
Properties:
1. Spanning tree should connect all vertices of graph
2. If graph is n vertices then spanning tree should have n-1 edges.
3. Should not contain cycles.

Minimum Cost Spanning Tree:


Based on cost
Properties of a Spanning Tree:
✓A Spanning tree does not exist for a disconnected graph.
✓For a connected graph having N vertices then the number of edges in
the spanning tree for that graph will be N-1.
✓A Spanning tree does not have any cycle.
✓We can construct a spanning tree for a complete graph by removing E-
N+1 edges, where E is the number of Edges and N is the number of
vertices.
✓Cayley’s Formula: It states that the number of spanning trees in a
complete graph with N vertices is N^{N-2}
✓For example: N=4, then maximum number of spanning tree possible
=4^{4-2} = 16.

You might also like