Graphs in c language

For PG students

1. Graphs in ‘C’ Language
By
Dr. C. Saritha
Lecturer in Electronics
SSBN Degree College, Anantapur

2. Data Structure
•Datastructureisaparticularwayof
sortingandorganizingdataina
computer.Sothatitcanbeused
efficiently.
•Differentkindsofdatastructuresare
suitedtodifferentkindsofapplications.

3. Types of Data Structure
•LinearDataStructure:Adatastructure
issaidtobelineardatastructureifits
elementsformasequence.
Ex:Array,Stack,Queueandlinkedlist.
•Non-LinearDataStructure:Elementsin
anon-lineardatastructuredonotform
asequence.
Ex:TreeandGraph.

4. Types of data structure
Data Structures
Linear Non-Linear
Arrays Linked lists Stack Queue Trees Graphs

5. Trees
•Atreeishierarchicalcollectionof
nodes.Oneofthenodes,knownasthe
root,isatthetopofthehierarchical.
•Eachnodecanhaveutmostonelink
comingintoit.
•Thenodewherethelinkoriginatesis
calledtheparentnode.Therootnode
hasnoparent.

6. Continue…
•Thelinksleavinganode(anynumber
oflinksareallowed)pointtochild
nodes.
A
B C D
EFGHIJ

7. Graphs
•Agraphisasetofnodes(alsocalled
vertices)andasetofarcs(alsocalled
edges).Asamplegraphisasfallows:
A
D
C
B
E

8. Edges & Vertices
•Eachnodeinagraphisknownasa
vertexofthegraph.
•TheEachedgeofagraphcontainstwo
vertices.

9. Types of Graphs
•TheGraphscanbeclassifiedintotwo
types.Theyare:
Undirectedgraphs
Directedgraph

10. Continue…
Undirectedgraphs:Inanundirected
graphtheorderofpairisunimportant.
Hencethepairs(v1,v2)and(v2,v1)
representsameedge.
Directedgraph:Inthistheorderofthe
verticesrepresentinganedgeis
important.Thispairisrepresentedas
<v1,v2>wherev1isthetailandv2is
headofv2.Thus<v1,v2>and<v2,v1>
representsdifferentedges.

11. Undirected graph
•Set of vertices={1,2,3,4,5}
•Set of edges= {(1,2),(1,3),(1,4),(2,3),
(2,4),(2,5),(3,4),(4,5)}
1
5
2
43

12. Directed Graphs
•Set of vertices={1,2,3}
•Set of edges= {<1,2>, <2,1>, <2,3>,
<3,2>}
1
2
3

13. Adjacent Vectors & Incident Edges
•Inanundirectedgraphif(v1,v2)isan
edgeinthesetofedges,thenthe
verticesv1andv2aresaidtobe
adjacentandtheedge(v1,v2)is
incidentonverticesv1andv2.
•If<v1,v2>isadirectededge,then
vertexv1issaidtobeadjacenttov2
whilev2isadjacentfromv1.
•Theedge<v1,v2>isincidenttov1and
v2.

14. Continue…
•Thevertex2inthe
shownundirected
graphisadjacentto
vertices1,3,4and
5.Theedgesincident
onvertex3are
(1,3),(2,3) and
(3,4).
1
5
2
43

15. Continue…
•Intheshown
directedgraphthe
edgesincidentto
vertex 2 are
<1,2>,<2,1>,<2,3>
and<3,2>.
1
2
3

16. Terminology of Graphs
•Weightedgraph:A
graphissaidtobe
weightedgraphif
it’sedgeshavebeen
assignedsomenon-
negativevalueas
weight.Aweighted
graphisknownas
network.
1
2
4
3
2
5
3
6

17. Continue…
•Degree:Inan
undirectedgraph,
thenumberofedges
connectedtoanode
iscalledthedegree
ofthatnode.Where
isindigraph,there
aretwodegreesfor
everynodetheyare
indegree and
outdegree.
1 2
4
3

18. Continue…
•Indegree: The
indegreeofnodeis
thenumberofedges
comingtothat
node.
•Outdegree:Theout
degreeofnodeis
thenumberofedges
goingoutsidethat
node.
1 2
4
3

19. Continue…
•Isolatednode:Ifanynodehasno
edgesconnectedwithanyothernode
thenitsdegreewillbezero(0)andit
willbecalledasisolatednode.
A
D
C
B
E

20. Continue…
•Source:Anode,
which has no
incomingedges,but
hasoutgoingedges,
iscalledasource.
1 2
43

21. Continue…
•Connectedgraph:
Anundirectedgraph
issaidtobe
connectedifthereis
apathfromany
nodeofgraphto
anyothernode.
A
D
C
B
E

22. Continue…
•Completegraph:An
undirectedgraph
willcontainn(n-1)/2
edgesiscalleda
complete graph
whereasinthecase
ofdigraphwill
contain n(n-1)
edges,wherenis
thetotalnumberof
nodesinthegraph.
1
2
3
1
2
3

23. Continue…
•Loop:Anedgewill
becalledlooporself
edgeifitstartsand
endsonthesame
node.
1
2
43

24. Breadth first search
•Thegeneralidea
behindabreadth
first traversal
beginningata
startingnodeAisas
following.Wefirst
examinethestarting
nodeA,andthenits
neighborsafterthat
theneighborsofits
neighbors. •A BDE CFG
A B
D E
C
GF

25. Depth first search
•InDepthfirstsearch
techniquealsowetake
onenodeasstarting
node.Thengotothe
path which from
startingnodeandvisit
allthenodeswhichare
inthepath.Whenwe
reachatthelastnode
thenwe traverse
anotherpathstarting
fromthatnode
T
K
N
Y
H A
U
O
THANK YOU