Struktur Data (SAK 1107)
Tutorial 8
JAWAPAN
- Diberikan graf seperti
dibawah:-
Berikan;
- Matriks kejiranan
|
|
a
b c d e f g h I j |
|
a |
0
0 1 1 1 1 0 0 0 0 |
|
b |
0
0 0 0 0 0 0 0 0 0 |
|
c |
0
1 0 0 0
0 0 0 0 0 |
|
d |
0
0 0 0 0 0 0 0 1 0 |
|
e |
0
0 0 1 0 0 0
1 0 0 |
|
f |
0
0 0 0 0 0 0 0 0 0 |
|
g |
0
0 0 0 0 0 0 0 0 0 |
|
h |
0
0 0 0 0 0 0 0 0 1 |
|
i |
0
0 0 0 0 0 0 0 0 0 |
|
J |
0
0 0 0 0 0 0
0 0 0 |
- Bucu
A B C
D E F
G
- Tepi
(C,B) (A,C) (A,D) (A,F)
(A,E) (E,G) (E,H) (H,D) (H,J) (D,I)
- Laluan Bukan Kitaran
A C B
- Laluan Mudah
(A E H D I)
- Laluan bukan mudah
(I D A C B)
- Senarai kejiranan
F E D C
A
B
C
D
E
F
G
H
I
J
- Berdasarkan graf soalan (1), senaraikan bucu-bucu mengikut kaedah
yang diberikan. Apabila ziarah bucu yang baru, ziarah dahulu bucu yang
terdahulu di susunan abjad.
i.
Penyusunan/
carian dalam dahulu (depth-first search) bermula bucu A
- ACBDEFGHIJ
ii penyusuran / carian lebar dahulu
(breadth-first search) bermula bucu A
- ACBFDIEGHJ
Lakarkan graf
bagi matriks kejiranan dibawah:
|
|
A |
B |
C |
D |
|
A |
0 |
1 |
1 |
1 |
|
B |
1 |
0 |
0 |
1 |
|
C |
1 |
0 |
0 |
0 |
|
D |
1 |
1 |
0 |
0 |
- Jawab soalan –soalan di bawah berdasarkan kepada graf di bawah:-
i. Binakan matriks kejiranan dan senarai kejiranan
|
|
0
1 2 3 4 5 |
|
0 |
0
1 0 1 0
0 |
|
1 |
0
0 0 0 1 0 |
|
2 |
0
0 0 0 0
0 |
|
3 |
0
1 0 0 0 0 |
|
4 |
0
0 1 0 0 0 |
|
5 |
0
0 1 0 0 0 |
0
1
2
3
4
5
3. Diberikan
tepi nilai jarak bagi suatu graf berarah seperti berikut:-
Tepi Jarak
(1,2) 30
(1,4) 50
(1,5) 40
(1,6) 100
(2,3) 40
(3,5) 10
(3,6) 30
(4,3) 10
(5,4) 20
(5,6) 70
Lukiskan bentuk graf tersebut:-
30
100
40
40 50
30 70
10
10
20