Graf lwn Pokok
Graf dan Pokok digunakan dalam struktur data. Sudah tentu terdapat beberapa perbezaan antara Graf dan Pokok. Satu set bucu yang mempunyai hubungan binari dipanggil graf manakala pepohon ialah struktur data yang mempunyai set nod yang dipautkan antara satu sama lain.
Graf
Graf ialah set item yang disambungkan dengan tepi dan setiap item dikenali sebagai nod atau bucu. Dalam erti kata lain, graf boleh ditakrifkan sebagai set bucu dan terdapat hubungan binari antara bucu ini.
Dalam pelaksanaan graf, nod dilaksanakan sebagai objek atau struktur. Tepi boleh diwakili dengan cara yang berbeza. Salah satu caranya ialah setiap nod boleh dikaitkan dengan tatasusunan tepi insiden. Jika maklumat itu hendak disimpan dalam nod dan bukannya tepi maka tatasusunan bertindak sebagai penunjuk kepada nod dan juga mewakili tepi. Salah satu kelebihan pendekatan ini ialah nod tambahan boleh ditambah pada graf. Nod sedia ada boleh disambungkan dengan menambahkan elemen pada tatasusunan. Tetapi terdapat satu kelemahan kerana masa diperlukan untuk menentukan sama ada terdapat kelebihan antara nod.
Cara lain untuk melakukan ini ialah dengan mengekalkan tatasusunan dua dimensi atau matriks M yang mempunyai nilai Boolean. Kewujudan tepi dari nod i hingga j ditentukan oleh entri Mij. Salah satu kelebihan kaedah ini ialah untuk mengetahui sama ada terdapat sebarang tepi antara dua nod.
Pokok
Tree juga merupakan struktur data yang digunakan dalam sains komputer. Ia serupa dengan struktur pokok dan mempunyai satu set nod yang dipautkan antara satu sama lain.
Nod pokok mungkin mengandungi syarat atau nilai. Ia juga boleh menjadi pokok sendiri atau ia boleh mewakili struktur data yang berasingan. Sifar atau lebih nod hadir dalam struktur data pokok. Jika nod mempunyai anak maka ia dipanggil nod induk kanak-kanak itu. Paling banyak boleh ada satu induk nod. Laluan ke bawah terpanjang dari nod ke daun ialah ketinggian nod. Kedalaman nod diwakili oleh laluan ke akarnya.
Dalam pokok, nod paling atas dipanggil nod akar. Nod akar tidak mempunyai ibu bapa kerana ia adalah yang paling atas. Dari nod ini, semua operasi pokok bermula. Dengan menggunakan pautan atau tepi, nod lain boleh dicapai dari nod akar. Nod tahap paling bawah dipanggil nod daun dan mereka tidak mempunyai anak. Nod yang mempunyai bilangan nod anak dipanggil nod dalam atau nod dalaman.
Perbezaan antara graf dan pokok:
• Pokok boleh digambarkan sebagai kes graf khusus tanpa gelung dan litar sendiri.
• Tiada gelung dalam pokok manakala graf boleh mempunyai gelung.
• Terdapat tiga set dalam graf iaitu tepi, bucu dan set yang mewakili hubungannya manakala pokok terdiri daripada nod yang bersambung antara satu sama lain. Sambungan ini dirujuk sebagai tepi.
• Dalam pepohon terdapat banyak peraturan yang menerangkan cara sambungan nod boleh berlaku manakala graf tidak mempunyai peraturan yang menentukan sambungan antara nod.
