Graphs

edg edg
A A
nod e e
e verte
x
B C D B C D

E F G E F G

Tree Graph

Size of a Graph :-
G = (V,E) = ( 7,12 )
 Type of edge :

1- directed : 1 2 <1,2
>
1< 2 , 1 >
< 1 , 2 > != 2 <2,1
>
2- undirected :

1 2 (1,2
(1,2)=(2,1) )
1 2 (2,1)
 Type of graphs (undirected edge):

1- complete / not complete graph :

 complete :

𝑛(𝑛 −1)
𝑚 =
2 A

𝑚 : # of edge .
B C
𝑛 : # of vertices .
3(3 −1)
3 ---
2
3=3
 not complete graph :

𝑛(𝑛 −1) A
𝑚 <
2

𝑚 : # of edge . B C

𝑛 : # of vertices . 3(3 −1)

2 ---
2
2<3
Eg:
A A

B C B C

D D

m(edge) = 4 m(edge) = 6
n(vertex) = 4 n(vertex) = 4
4(4−1) 4(4−1)
4 --- 6 ---
2 2
4<6 6=6
* not complete * complete
 Complete graph : there is an edge between any
two vertex .

A A

B C B C

D D

* not complete * complete

2- connected / not connected graph :

 connected :

𝑚 >= 𝑛 - 1 A

𝑚 : # of edge .
B c
𝑛 : # of vertices .
D

3 --- (4-1)
3= 3
*
 not connected : A
𝑚 <𝑛-1
B c
𝑚 : # of edge .

𝑛 : # of vertices . D

2 --- (4-1)
2< 3
* not
connected
 connected graph : I can visit any vertex from
any vertex .

A A

B C B C

D D

* not * connected
connected
Eg:
m(edge) = 6 A
n(vertex) = 4
4(4−1)
6 --- B C
2
6=6
* complete
D

m(edge) = 6
n(vertex) = 4
6 --- 4 - 1
6>3
* connected
Eg:
A
m(edge) = 3
n(vertex) = 4
3 ---
4(4−1) B C
2
3<6
* not complete D

m(edge) = 3
n(vertex) = 4
3 --- 4 - 1 Connected --->
3=3 complete??
* connected not connected --->
 Graphs Representation :
1- Adjacency Matrix (2D array )
* vertex – vertex

Eg: 1

1 2 3 4 2 4
1 1 1 0 1
2 1 0 1 0 3
3 0 1 0 1
4 1 0 1 0
Eg:
1 2 3 4 5 1
1 1 1 0 0 0
2 1 0 1 0 0
2 5
3 0 1 1 0 1
4 0 0 0 0 1
5 0 0 1 1 0 3

*Undirected graph : Symmetric

matrix 4

array[ i ][ j ] = array[ j ][ i ] = ( 0 or 1)
𝒏𝟐
(j >= i) :- O(𝒏𝟐 ) O( )
Eg:

1 2 3 4
1 1 1 0 0
1
2 0 0 1 1
3 0 0 0 0
4 1 0 1 0 2 4

*Directed graph :
3
Array[1][2] ≠ Array[2][1]
Array[2][4] ≠ Array[4][2]
• O(𝒏𝟐 )
2- Incidence matrix (2D array )
* vertex - edge

1 e4
e1 e2 e3 e4 e1
e2
1 1 1 0 1
2 4
2 1 0 1 0
3 0 1 1 0 e3
4 0 0 0 1 3
 3- Adjacency List ( linked list )
* vertex - vertex

0
1
1 2 3 4
NUL
2 1 3 L
NUL 2 4
2 L
3 1
NUL
4 1 5 L 3
NUL
5 4 L 5
NUL
Print :
1- Depth First Search (DFS) :
( vertex by vertex )
A

DFS(A) : A B C D E B D E
DFS(D) : D A B C E
DFS(E) : E A B C D
C
Eg:

DFS(A) : A B C D E F
DFS(D) : D A B C F E
B D F
DFS(C) : C B A D E F

C E
2- Breadth First Search (BFS) :
( level by level )

BFS(A) : A B C D E
BFS(D) : D A C B E B D E
BFS(E) : E A C B D

C
 A

BFS(A) : A B D F C E
BFS(D) : D A B C E F
B D F
BFS(C) : C B D A E F

C E
 1

2 3

BFS(1) : 1 2 3 4 5 6 7 4 5 6 7
DFS(1) : 1 2 4 5 3 6 7
Shortest Path :
* Dijkstra's Algorithm

2 24 3
9
1 18
14
2 6
6
30
11 4 19
15 5
5
6
20 16

7 44 8
 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞
1(0) 9 ∞ ∞ ∞ 14 15 ∞
2(9) 33 ∞ ∞ 14 15 ∞
6(14) 32 ∞ 44 15 ∞
7(15) 32 ∞ 35 59
3(32) ∞ 34 51
5(34) 45 50
4(45) 50
8(50)
what is the shortest path from vertex(1) to vertex(8) ?

1→6→3→5→8

what is the path length ? 50

Eg:

A 2 C 1
F
5 2
3
D
2
1
B 3

4
E
 A B C D E F
0 ∞ ∞ ∞ ∞ ∞
A(0) 3 2 5 ∞ ∞
C(2) 3 4 ∞ 3
B(3) 4 7 3
F(3) 4 5
D(4) 5
E(5)
what is the shortest path from vertex A to
vertex E ?
A→C→F→E
Minimum Spanning Trees :
Minimize the number of edge as much as
possible .

 Some applications:

Communication networks
Circuit design
Layout of highway systems
 1- Kruskal's Algorithm

b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(g,h) 1
h 1 g 2 f 0

b c d

a i e

h g f
 b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(g,h) 1
h 1 g 2 f 0
(c,i)

b c d

a i e

h g f
 b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(g,h) 1
h 1 g 2 f 0
(c,i)
(g,f)
b c d

a i e

h g f
 b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(g,h) 1
h 1 g 2 f 0
(c,i)
(g,f)
(a,b) b c d

a i e

h g f
 b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(g,h) 1
h 1 g 2 f 0
(c,i)
(g,f)
(a,b) b c d
(c,f)
a i e

h g f
 b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(g,h) 1
h 1 g 2 f 0
(c,i)
(g,f)
(a,b) b c d
(c,f)
(c,d) a i e

h g f
 b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(g,h) 1
h 1 g 2 f 0
(c,i)
(g,f)
(a,b) b c d
(c,f)
(c,d) a i e
(a,h)
h g f
 b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(g,h) 1
h 1 g 2 f 0
(c,i)
(g,f)
(a,b) b c d
(c,f)
(c,d) a i e
(a,h)
(d,e) h g f
 2- Prim’s Algorithm

b 8 7
ab c d
4 9
2 4
a 1
i 14 e
1
7 6
8
(a,b) 1
h 1 g 2 f 0

b c d

a i e

h g f
ab
c b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(a,b) 1
h 1 g 2 f 0
(b,c)

b c d

a i e

h g f
ab
ci b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(a,b) 1
h 1 g 2 f 0
(b,c)
(c,i)
b c d

a i e

h g f
abcif
b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(a,b) 1
h 1 g 2 f 0
(b,c)
(c,i)
(c,f) b c d

a i e

h g f
abcif
g b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(a,b) 1
h 1 g 2 f 0
(b,c)
(c,i)
(c,f) b c d
(f,g)
a i e

h g f
abcifg
h b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(a,b) 1
h 1 g 2 f 0
(b,c)
(c,i)
(c,f) b c d
(f,g)
(g,h) a i e

h g f
abcifg
hd b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(a,b) 1
h 1 g 2 f 0
(b,c)
(c,i)
(c,f) b c d
(f,g)
(g,h) a i e
(c,d)
h g f
abcifgh
de b 8 7
c d
4 9
2 4
1 14 e
a i
1
7 6
8
(a,b) 1
h 1 g 2 f 0
(b,c)
(c,i)
(c,f) b c d
(f,g)
(g,h) a i e
(c,d)
(d,e) h g f
Thanks