Secara akademis, apa perbedaan mendasar antara struktur data Pohon dan Grafik? Lalu bagaimana dengan penelusuran berbasis pohon dan penelusuran berbasis grafik?
Apa perbedaan antara struktur data Pohon dan Grafik?
Jawaban (11)
Pohon hanyalah bentuk terbatas dari Grafik.
Pohon memiliki arah (hubungan induk/anak) dan tidak mengandung siklus. Mereka termasuk dalam kategori Grafik Asiklik Terarah (atau DAG). Jadi Pohon adalah DAG dengan batasan bahwa seorang anak hanya dapat memiliki satu orang tua.
Satu hal yang penting untuk diperhatikan, Pohon bukanlah struktur data rekursif. Mereka tidak dapat diimplementasikan sebagai struktur data rekursif karena keterbatasan di atas. Namun implementasi DAG apa pun, yang umumnya tidak bersifat rekursif, juga dapat digunakan. Implementasi Pohon pilihan saya adalah representasi peta terpusat dan non rekursif.
Grafik umumnya dicari luasnya terlebih dahulu atau kedalamannya terlebih dahulu. Hal yang sama berlaku untuk Pohon.
Daripada menjelaskan saya lebih suka menampilkannya dalam gambar.
Pohon dalam waktu nyata
Grafik dalam penggunaan kehidupan nyata
Ya, peta dapat divisualisasikan sebagai struktur data grafik.
Melihat mereka seperti ini membuat hidup lebih mudah. Pohon digunakan di tempat dimana kita mengetahui bahwa setiap node hanya memiliki satu orang tua. Namun graf dapat memiliki beberapa pendahulu (istilah induk umumnya tidak digunakan untuk graf).
Di dunia nyata, Anda dapat merepresentasikan hampir semua hal menggunakan grafik. Saya menggunakan peta, misalnya. Jika Anda menganggap setiap kota sebagai sebuah simpul, maka kota tersebut dapat dijangkau dari beberapa titik. Titik-titik yang menuju ke simpul ini disebut pendahulu, dan titik-titik yang akan dituju oleh simpul ini disebut penerus.
diagram rangkaian listrik, denah rumah, jaringan komputer atau sistem sungai adalah beberapa contoh grafik lainnya. Banyak contoh dunia nyata yang dapat dianggap sebagai grafik.
Diagram teknisnya bisa seperti ini
Pohon :
Grafik :
Pastikan untuk merujuk ke tautan di bawah ini. Itu akan menjawab hampir semua pertanyaan Anda tentang pohon dan grafik.
Referensi :
http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-lysis/
Wikipedia
Jawaban lain berguna, tetapi properti masing-masing tidak ada:
Grafik
Grafik tidak berarah, sumber gambar: Wikipedia
Grafik berarah, sumber gambar: Wikipedia
- Terdiri dari sekumpulan simpul (atau simpul) dan sekumpulan sisi yang menghubungkan beberapa atau seluruhnya
- Setiap sisi dapat menghubungkan dua simpul mana pun yang belum terhubung oleh sisi yang identik (dalam arah yang sama, dalam kasus graf berarah)
- Tidak harus terhubung (tepinya tidak harus menghubungkan semua simpul menjadi satu): sebuah graf tunggal dapat terdiri dari beberapa himpunan simpul yang tidak terhubung
- #P6#
#P7#
Pohon
- Suatu jenis grafik
- Verteks lebih sering disebut dengan “node”
- Tepi diarahkan dan mewakili hubungan "adalah anak dari" (atau "adalah orang tua dari").
- Setiap node (kecuali node root) mempunyai tepat satu parent (dan nol atau lebih anak)
- Memiliki tepat satu simpul "root" (jika pohon memiliki setidaknya satu simpul), yang merupakan simpul tanpa orangtua
- Harus terhubung
- Bersifat asiklik, artinya tidak memiliki siklus: "siklus adalah sebuah jalur [urutan AKA ] dari sisi dan simpul yang simpulnya dapat dijangkau dari dirinya sendiri"
Ada beberapa tumpang tindih dalam properti di atas. Secara khusus, dua properti terakhir tersirat oleh properti lainnya. Namun semuanya tetap patut diperhatikan.
Pohon adalah graf berbentuk khusus, yaitu graf terhubung minimal dan hanya memiliki satu jalur antara dua simpul mana pun.
Dalam graf bisa terdapat lebih dari satu jalur, yaitu graf dapat memiliki jalur (tepi) satu arah atau dua arah antar node
Anda juga dapat melihat detail lebih lanjut: http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/
Pohon sudah jelas: merupakan struktur data rekursif yang terdiri dari node dengan anak.
Peta (alias kamus) adalah pasangan kunci/nilai. Berikan kunci pada peta dan itu akan mengembalikan nilai terkait.
Peta dapat diimplementasikan dengan menggunakan pepohonan, saya harap hal itu tidak membingungkan Anda.
PEMBARUAN: Membingungkan "grafik" untuk "peta" sangat membingungkan.
Grafik lebih kompleks daripada pohon. Pohon menyiratkan hubungan orang tua/anak yang rekursif. Ada cara alami untuk melintasi pohon: kedalaman-pertama, lebar-pertama, tingkat-urutan, dll.
Grafik dapat memiliki jalur satu arah atau dua arah antar node, bersifat siklik atau asiklik, dll. Saya akan menganggap grafik menjadi lebih kompleks.
Saya pikir pencarian sepintas dalam teks struktur data yang layak (misalnya "Manual Desain Algoritma") akan memberikan informasi lebih banyak dan lebih baik daripada sejumlah jawaban SO. Saya akan merekomendasikan agar Anda tidak mengambil jalur pasif dan mulai melakukan riset sendiri.
Di pohon, setiap node (kecuali node root) memiliki tepat satu node pendahulu dan satu atau dua node penerus. Itu dapat dilintasi dengan menggunakan traversal In-order, Pre-order, Post-order, dan Breadth First. Pohon merupakan graf khusus yang tidak mempunyai siklus sehingga disebut DAG (Directed Acyclic Graph). Pohon adalah model hierarki.
Dalam graf, setiap node memiliki satu atau lebih node pendahulu dan node penerus. Grafik tersebut dilintasi dengan menggunakan algoritma Depth First Search (DFS) dan Breadth First Search (BFS). Grafik mempunyai siklus sehingga lebih kompleks daripada pohon. Grafik adalah model jaringan. Graf ada dua macam, yaitu graf berarah dan graf tidak berarah.
Pohon pada dasarnya adalah graf tidak berarah yang tidak mengandung siklus, sehingga dapat dikatakan bahwa pohon adalah bentuk graf yang lebih terbatas. Namun pohon dan grafik memiliki penerapan yang berbeda untuk mengimplementasikan berbagai algoritma dalam pemrograman. Misalnya grafik dapat digunakan untuk model peta jalan dan pohon dapat digunakan untuk mengimplementasikan struktur data hierarki apa pun.
Pohon adalah digraf sedemikian rupa sehingga:
a) dengan arah tepi dihilangkan, ia terhubung dan asiklik
- Anda dapat menghilangkan asumsi bahwa ini adalah asiklik
- Jika terbatas, Anda dapat menghilangkan asumsi bahwa itu terhubung
b) setiap simpul kecuali satu, akar, mempunyai derajat 1
c) akarnya memiliki derajat 0
- Jika jumlah simpulnya tidak terhingga, Anda dapat menghilangkan asumsi bahwa akar mempunyai derajat 0 atau asumsi bahwa simpul selain akar mempunyai derajat 1
Referensi: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf
Dalam matematika, grafik adalah representasi himpunan objek yang beberapa pasangan objeknya dihubungkan melalui tautan. Objek-objek yang saling berhubungan diwakili oleh abstraksi matematis yang disebut simpul, dan tautan yang menghubungkan beberapa pasang simpul disebut tepi.[1] Biasanya, suatu graf digambarkan dalam bentuk diagram sebagai sekumpulan titik-titik pada simpul-simpulnya, yang dihubungkan dengan garis-garis atau kurva-kurva pada sisi-sisinya. Grafik merupakan salah satu objek kajian dalam matematika diskrit.
satu simpul akar di pohon dan hanya satu induk untuk satu anak. Namun, tidak ada konsep simpul akar. Perbedaan lainnya adalah, pohon adalah model hierarki tetapi grafik adalah model jaringan.
Konsep sederhananya adalah Pohon tidak memiliki pembentukan siklus dan bersifat searah sedangkan Grafik membentuk siklus dan dalam beberapa kasus akan menjadi Dua Arah dan dalam kasus lain Searah.