KYLE KEAN C.
ASTORGA
2-ITF
ICS2605 – GRAPHS
1.
0 1 2 3 4 5 6 7 8
0 0 1 0 1 0 0 0 0 1
1 1 0 0 0 0 0 0 1 0
2 0 0 0 1 0 1 0 1 0
3 1 0 1 0 1 0 0 0 0
4 0 0 0 1 0 0 0 0 1
5 0 0 1 0 0 0 1 0 0
6 0 0 0 0 0 1 0 0 0
7 0 1 1 0 0 0 0 0 0
8 1 0 0 0 1 0 0 0 0
Adjacency Matrix
KYLE KEAN C. ASTORGA
2-ITF
Adjacent List
0
→ 1
→ 3
→ 8
1
→ 0
→ 7
2
→ 3
→ 5
→ 7
3
→ 0
→ 2
→ 4
4
→ 3
→ 8
5
→ 2
→ 6
6
→ 5
→
7
→ 1
→ 2
8
→ 0
→ 4
BFS:
0 1 3 8 7 2 4 5 6
DFS:
0 1 7 2 5 6 3 4 8
KYLE KEAN C. ASTORGA
2-ITF
2.
1 → 7
2
→ 6
3
→ 1 → 5
4
→ 6
5
→ 2 → 4
6 → 8
7
→ 2 → 8
8
1 2 3 4 5 6 7 8
1 0 0 0 0 0 0 1 0
2 0 0 0 0 0 1 0 0
3 1 0 0 0 1 0 0 0
4 0 0 0 0 0 1 0 0
5 0 1 0 1 0 0 0 0
6 0 0 0 0 0 0 0 1
7 0 1 0 0 0 0 0 1
8 0 0 0 0 0 0 0 0
Adjacency Matrix
Adjacent List
KYLE KEAN C. ASTORGA
2-ITF
BFS:
1 7 2 8 6 3 5 4
DFS:
1 7 2 6 8 3 5 4
3.
KYLE KEAN C. ASTORGA
2-ITF
0
→ 1 → 3 → 5
1
→ 0 → 3 → 8
2
→ 5 → 7 → 8
3
→ 0 → 1 → 4 → 6
41
0 → 2 3 →
3 46 →
5 96 7 8 9
0 0 51 0 1 0 1
→ 0 → 2 → 60 0 0 0
1 1 0 0 1 0 0 0 0 1 0
6
2 0 0
→ 0
3 →
0
4
0
→
1
5
0 1 1 0
71
3 1 → 0 2 0 1 0 1 0 0 0
4 0 80 0 1 0 0
→ 1 → 2 → 91 0 0 1
5 1 0 1 0 0 0 1 0 0 0
9
6 0 0
→ 0
4 →
1
8
1 1 0 0 0 0
7 0 0 1 0 0 0 0 0 0 0
8 0 1 1 0 0 0 0 0 0 1
9 0 0 0 0 1 0 0 0 1 0
Adjacent Matrix
Adjacent List:
KYLE KEAN C. ASTORGA
2-ITF
BFS:
0 1 3 5 8 4 6 2 9 7
DFS:
0 1 8 2 7 9 4 6 3 5
4.
KYLE KEAN C. ASTORGA
2-ITF
2 3 5 7 8 9 10 11
2 0 0 0 0 0 0 0 0
3 0 0 0 0 1 0 1 0
5 0 0 0 0 0 0 0 1
7 0 0 0 0 1 0 0 1
8 0 1 0 1 0 1 0 0
9 0 0 0 0 1 0 0 1
10 0 1 0 0 0 0 0 1
11 1 0 0 0 0 1 1 0
Adjacent Matrix
KYLE KEAN C. ASTORGA
2-ITF
Adjacent
3
→ 8 → 10 List:
5
→ 11
7
→ 8 → 11
8
→ 9
9
10
11
→ 2 → 9 → 10
BFS:
2 3 8 10 9 5 11 7
DFS:
2 3 8 9 10 5 11 7
KYLE KEAN C. ASTORGA
2-ITF
5.
Adjacent Matrix
A B C D E F G
A 0 1 0 1 0 0 0
B 1 0 0 0 0 0 0
C 0 0 0 1 0 0 0
D 1 0 0 0 1 0 0
E 0 0 0 1 0 1 0
F 0 0 0 0 1 0 1
G 0 0 0 0 0 1 0
KYLE KEAN C. ASTORGA
2-ITF
A
→ B → D
Adjacent List :
B
→ A
C
→ D
D
→ A → E
E
→ D → F
F
→ E → G
G
→ F
BFS:
A B D C E F G
DFS:
A B D C E F G
