Graphs in Data Structure

DS – Module 3 – Non Linear Data Structures – Graphs
🞂 What is Graph?
🞂 Representation of Graph
⮩ Matrix representation of Graph
⮩ Linked List representation of Graph

🞂 Elementary Graph Operations
⮩ Breadth First Search (BFS)
⮩ Depth First Search (DFS)
⮩ Spanning Trees
⮩ Minimal Spanning Trees
⮩ Shortest Path


#3130702 (DS) ⬥ Unit 3 – Non-Linear Data
Dr. Pradyumansinh U. Jadeja
Structure (Tree Part-1)

,Basic Notations of Graph Theory

1 2 x1 1 1
x3 x1 x
v v
x2 x2
1 (a) 2 2 3 2

x4 x5 x4 x5
4 4
1 2 5
(d) (f)
v v
1 (b) 2
x1 1 x3 x1 1 x
x2 x2
2 3 2
1 2

v v x4 x5 x4
4 x5
4
1 (c) 2
(e) (g)
#3130702 (DS) ⬥ Unit 3 – Non-Linear Data
Dr. Pradyumansinh U. Jadeja
Structure (Tree Part-1)

,Basic Notations of Graph Theory
🞂 Consider diagrams shown in above figure
🞂 Every diagrams represent Graphs
🞂 Every diagram consists of a set of points which are shown by dots or circle
sometimes labelled V1, V2, V3… OR 1,2,3…

🞂 In every diagrams, certain pairs of such points are connected by lines or arcs
🞂 Note that every arc start at one point and ends at another point




#3130702 (DS) ⬥ Unit 3 – Non-Linear Data
Dr. Pradyumansinh U. Jadeja
Structure (Tree Part-1)

, Basic Notations of Graph Theory
🞂 Graph
⮩ A graph G consist of a non-empty set V called the set of nodes (points, vertices) of the gr
which is the set of edges and a mapping from the set of edges E to a set of pairs of elements o
⮩ It is also convenient to write a graph as G=(V,E)
⮩ Notice that definition of graph implies that to every edge of a graph G, we can associate a pair
the graph. If an edge X Є E is thus associated with a pair of nodes (u,v) where u, v Є V then w
edge x connect u and v

🞂 Adjacent Nodes
⮩ Any two nodes which are connected by an edge in a graph are called adjacent nodes




#3130702 (DS) ⬥ Unit 3 – Non-Linear Data
Dr. Pradyumansinh U. Jadeja
Structure (Tree Part-1)