BIỂUDIỄNĐỒTHỊ
TRÊNMÁYTÍNH
CHƯƠNG2
TônQuangToại
KhoaCNTT,ĐạihọcNgoạingữ‐ TinhọcTP.HCM
Biểu diễn đồ thị bằng Matrận kề,matrận số
Biểu diễn đồ thị bằng Danh sách kề
Biểu diễn đồ thị bằng Danh sách cạnh
Nộidung
BIỂUDIỄNĐỒTHỊBẰNG
MATRẬNKỀ,MATRẬNTRỌNGSỐ
Đồthị G=(V,E)có nđỉnh ( )và mcạnh.
Matrận kề (adjacencymatrix)của Glà một
mảng 2chiều ,trong đó cho biết G
chứa những cạnh (i,j)haykhông
Matrận kề
𝑣𝑖,𝑗 󰇫1𝑛ế𝑢 𝑐ạ𝑛ℎ 󰇛𝑖,𝑗󰇜∈𝐸
0 𝑛ế𝑢 𝑐ạ𝑛ℎ 󰇛𝑖,𝑗󰇜∉𝐸
Ví dụ:Graphvô hướng
Matrận kề
0
2
1
4
5
3
012345
v=
0
1
2
3
4
5