MODULE 4- TREES AND GRAPHS
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
Scanned by CamScanner
T\ ~ ~--v- ¼ ~ t--~•ol "-J
("0 ~ ·o l~(.._,._/ (t.,,•tk ,SCr ,, ~--l, )
fit'
\:) f' . l ) [-"' ~ Q \ C l ""' t ~Q_)
; / l--,1' J.,.
I ,
(1) r\ :,,.S-
.[ 11 2-1 \'-{,S~
(lJ@) m~ G)ob ~ ~
;\ I-"' I '\ /~
\1 t'L/ ~ s\ 1 1
r,1 ft'-l,s} 1,,\.-\ t~,( [t,1_ ✓ ·q ~ n.
~
1
~ ~ lj + 0~ 0 c" + -i:_ 2-.) t \S~ I J +
\~ +- S-- -t- y -t S--- t. t ~ ;: ½L,
'
I
'
JI\~
- C I 1--
i.... 5'
3
l½
~ 5'
tt ,.._ -
~ \ \ I
_____
~r~i~I
,
....___ l~S T
I, ;; [4s, r; ,_) 1 ,, tr1 •~ "l.
14 ~
'® 'y
T \'
I r-o...,i.... _c. J- r;/ S2-/ 'f >/ 4-'r/ C2../ C 1
l-- ~ L '?.GJ '&) 2-'i-) 7J",, 6~ Y!{"'/ 3S' 1
-36
~ \
~@) ~ - ' ~ . 'CJ H.1 :i,s, 5C 5'5":, C<t_, /5'
1
t 1 ; [. rz 1 "J.--C1 2-¾; 12-/ '.l.f'/ sc, 4-r/ If-"! 55-::,
1
c2:, c4,, 7 r ~
~ _,.,,Ei0 ~
A
1, , +r M rr
) ,
Ct, ,~,7'F'
@ ?,t-/ 31 :W- ~, ~
(0 ~
I
/
(bl ~ "\ /
{j_i) b;) ,c1,",)<: \ J r- i' )
/.<', C';. s-.r
l l ,., ~ \.. O
l) )
I"\
P'O)
t..·- '!;7.I J- (,J 'i ~ J 11-
1
3~r) ~ ( f.
I t, ~ [ '-6 ,fs1 4-1 1 n I n /; "1 7 5 ~
t I
26
~~"" Q J,,~o;c-+ tv~
~
. ,\ ;_ ,, 'l 1 z S'l ;; ~ lj, I 1
1)
co
..
1
,
' I 1-- 2 lf- S C 7
--f l l f t 1 £
\ - - - -
t
. . c,-..)e....:v~ ~I)(\
<; \ :: ~ ( ~ I 1 $t :_. f S_, ½ ~
w ,
!
1
0
t ?- J 4- ~ G 7 C-
t 1 I 3 -t S-- S-
' I
- l
,.
\ 2- J q-- s- ( 7 6 j
t
3 I ~ 5 17
~ --i \ I \
r-- -
. ,
.l I 1 ,
: 1~ ~,-cR . ~ LI_,_,_'"" 0!/E .
.,.
t~ i,~~l·'°' C,r-0 ,. J
l. ~ C, 1 pc,¥rtCr· 1 > .c:o ~ ; c par,v-J-Cn)
3
V •0 $ i ~ b""\,L"""o, (i ,-t- i', i.-i J)
t p"'~ en:: j;
1,
~r11-:1 . LA-~~ :--'
\Jo;~ we..,...'~lA~o<\ (t~ ,•> ,' r-'t j)
[ f1 ~·.,, Ll:i'. -8>4f L,,:tt: ""'t/J ;. o..,,.c/ J) t ! ~L ~?f
r::t:. w e . , _ ~ ""v-t._ • P" ..,,,+ c, 'J ~ - eo ,,_/-,[, 7 y .u
fa._~ 5'7
~ - G o ~ Cj J 1:'
I
I ,
.
1
,_,r 1£,.., P ::.- P"' ~ Cr J t P"' ~ Ct) ;
~t (f"~C'J::, _p,.~CJ]) ., . -·
-f>o ~ Ci17 ; j; ~ t<\~CJ.. J IJ:i-, l'Q_CJ ~vl:-1/
'P°'~9 1 ~ ~f ~
~
L PC<~ c5) ~ (; I~ rr-c)ez r' ~ N_i.j ~j o/
l fl>' ..,.vJ- CI) _, &'..,...e,
r
Je.1.-~b<\ T"r<->-J
- @) T,"""""--~ 1"'°:J
~
®
u, ~ 1 'V-'--j Ct-t
'·f,...·- J
L-,,M,,- T~ . ( ..-""' f~'--}
0
s '. 7 J
!L
1--;, t
f" ti ., i
' (
"'l"~, ~ ~ ry-........._"''-1
...
,
~
I ~
-ix~ "4 - pliJ--1
~ ~ - wl~,-,J ~ Jk ~
\Lq-, - l,J~,..,, \ tJ:;:, ~ -
~ 1¥-'-= ( ~,°'~'"' ~).
j
\
\0
-J ~L,., e tt ~~-- tJl-~·c.~ "'IC o..C"½ -IJ th-- i"y-~Jr f'•"=~
~ (,.)~~c{~.__,..ef t'--j l.,\ ✓ 1 J_, . { ~ --. alt .,...._c.__/, L'->'--.'c '-.,
{"'; ,i,:-c.,':)• oJ-. (?__?l f -<:,r-~t { (y>.i I ' " ( <-- l ; C,, ~t--_' ~ h <.,/ -:J
Wi1",.~.J l"'(H.it.t, I
GRAPHS
GRAPHS
GRAPHS
• A graph G is defined as follows:
G=(V,E)
V(G): a finite, nonempty set of vertices
E(G): a set of edges (pairs of vertices)
UNDIRECTED GRAPH
• When the edges in a graph have no direction, the graph is called undirected
DIRECTED GRAPH(DIGRAPH)
• When the edges in a graph have a direction, the graph is called directed (or digraph)
Adjacent nodes: two nodes are adjacent if they are connected by an edge
• Path: a sequence of vertices that connect two nodes in a graph
• Complete graph: a graph in which every vertex is directly connected to every other
vertex
What is the number of edges in a complete directed graph with N vertices?
N * (N-1)
• What is the number of edges in a complete undirected graph with N vertices?
N * (N-1) / 2 O( N 2 )
• Weighted graph: a graph in which each edge carries a value
REPRESENTATION OF GRAPH(REFER CLASS NOTES)
• USING ADJACECY MATRIX
• USING ADJACENCY LINKED LIST
Depth-First-Search (DFS)
• What is the idea behind DFS?
Visit one adjacent node at a time which is not visited.
Backtracking is used
Follows 2 ordering(pushing sequence and popping Sequence are different)
Back Edges are used to track the visited edges.
– Travel as far as you can down a path
– Back up as little as possible when you reach a "dead end" (i.e., next vertex
has been "marked" or there is no next vertex)
• DFS can be implemented efficiently using a stack
void dfs(int v)
{
int i;
reach[v]=1;
for(i=1;i<=n;i++)
{
if(a[v][i] && !reach[i])
{
printf("\n %d->%d",v,i);
count++;
dfs(i);
}
}
BFS(BREADTH FIRST SEARCH)
Visit ALL adjacent node at a time and add those to queue which is not
visited.
Backtracking is not used
Follows 1 ordering(inserting sequence and deleting Sequence are same)
cross Edges are used to track the visited edges.
– Travel as far as you don’t have adjacent nodes
• BFS can be implemented efficiently using a Queue.
#include <stdio.h>
#include <stdlib.h>
int a[20][20],q[20],visited[20],reach[10], n, i, j, f=0,r= -1,count=0;
void bfs(int v)
{
for(i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}
11th LAB PROGRAM: -
1) Design, Develop and Implement a Program in C for the following
operations on Graph(G) of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph
using BFS method
c. Check whether a given graph is connected or not using DFS method
#include <stdio.h>
#include <stdlib.h>
int a[20][20],q[20],visited[20],reach[10],n,i,j,f=0,r= -1,count=0;
void bfs(int v)
{
for(i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}
void dfs(int v)
{
int i;
reach[v]=1;
for(i=1;i<=n;i++)
{
if(a[v][i] && !reach[i])
{
printf("\n %d->%d",v,i);
count++;
dfs(i);
}
}
void main()
{
int v, choice;
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
for(i=1;i<=n-1;i++)
reach[i]=0;
printf("\n Enter graph data in matrix form:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("1.BFS\n 2.DFS\n 3.Exit\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
if((v<1)||(v>n))
{
printf("\n Bfs is not possible");
}
else
{
printf("\n The nodes which are reachable from
%d:\n",v);
for(i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i);
}
break;
case 2:
dfs(1);
if(count==n-1)
printf("\n Graph is connected");
else
printf("\n Graph is not connected");
break;
case 3:
exit(0);
}
Output
linux:~/dslab #gedit
bfs.c linux:~/dslab
#gcc bfs.c
linux:~/dslab # ./a.out
Enter the number of
vertices:5 Enter graph
data in matrix form: 0
1010
10101
01010
10100
01000
1.BFS
2.DFS
3.Exit
1->2
2->3
3->4
2->5
Graph is connected
Enter the number of
vertices:5
Enter graph data in
matrix form: 0 1 0 1 0
10100
01010
10100
00000
1.BFS
2.DFS
3.Exit
1->2
2->3
3->4
Graph is not connected
Enter the number of vertices:5
Enter graph data in
matrix form: 0 1 1 0 0
00010
00000
00100
00100
1.BFS
2.DFS
3.Exit
Enter the starting vertex:1
The nodes which are
reachable from 1: 2 3 4
Enter graph data in
matrix form: 0 1 1 0 0
00010
00000
00100
00100
1.BFS
2.DFS
3.Exit
Enter the
starting vertex:0
BFS is not
possible
