Apa perbedaan antara struktur data Tree dan Graph?

144

Secara akademis, apa perbedaan mendasar antara struktur data Tree dan Graph? Dan bagaimana dengan pencarian berbasis pohon dan pencarian berbasis grafik?

search data-structures map tree pengguna918304
sumber

Jawaban:

154

Pohon hanyalah bentuk terbatas dari Grafik.

Pohon memiliki arah (hubungan induk / anak) dan tidak mengandung siklus. Mereka cocok dengan 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 ditunjukkan, Pohon bukanlah struktur data rekursif. Mereka tidak dapat diimplementasikan sebagai struktur data rekursif karena batasan di atas. Tetapi implementasi DAG apa pun, yang umumnya tidak rekursif, juga dapat digunakan. Implementasi Tree yang saya sukai adalah representasi peta terpusat dan tidak rekursif.

Grafik umumnya dicari lebarnya dulu atau kedalamannya dulu. Hal yang sama berlaku untuk Tree.

pengguna785287
sumber
8
Grafik sangat berguna dan dapat digunakan untuk memodelkan banyak hal. Banyak struktur data lain yang dapat dilihat sebagai grafik dengan batasan. Misalnya, daftar tertaut tunggal adalah kasus khusus DAG.
JR Garcia
7
@ user785287 apa yang Anda maksud dengan representasi peta terpusat ?
Geek
37
"Pohon bukanlah struktur data rekursif" itu menyesatkan dan salah. Sebuah pohon dapat direpresentasikan dengan struktur data non-rekursif (misalnya array edge; pohon penuh, seperti yang mendasari heap biner, dapat direpresentasikan dengan sangat kompak dalam sebuah array; ada representasi ringkas lainnya , dll.), tapi mungkin cara yang paling populer dan berguna untuk merepresentasikannya adalah menggunakan struktur berbasis penunjuk rekursif. Representasinya tidak unik untuk pohon yang tidak di-root, tetapi itu tidak penting.
j_random_hacker
3
Tidak terlalu. Pohon tidak selalu memiliki arah. en.wikipedia.org/wiki/Tree_(graph_theory) menunjukkan contoh pohon tanpa arah. Ini sering digunakan dalam konteks biologis.
Michal Palczewski
3
Pohon @ harshpatel991 tidak diarahkan dalam arti bahwa: "X dan Y berada dalam relasi orang tua-anak" tidak memiliki arah. Hubungan individu, "X adalah anak dari Y", dan "Y adalah anak dari X", adalah hubungan terarah. Arah menunjukkan hal itu; arah 'gerakan'. Di pohon, gagasan arah tidak benar-benar diperlukan kecuali jika bermakna (yang paling sering terjadi pada pohon). Setidaknya begitulah cara saya melihatnya.
Kostas Mouratidis
108

Dari pada menjelaskan, saya lebih suka menunjukkannya dalam gambar.

Pohon dalam waktu nyata

Pohon dalam waktu nyata

Grafik dalam penggunaan kehidupan nyata

Grafik waktu nyata

Ya, peta dapat divisualisasikan sebagai struktur data grafik.

Melihat mereka seperti ini membuat hidup lebih mudah. Pohon digunakan di tempat-tempat yang kita tahu bahwa setiap node hanya memiliki satu induk. Tetapi grafik dapat memiliki beberapa pendahulu (istilah induk umumnya tidak digunakan untuk grafik).

Di dunia nyata, Anda dapat merepresentasikan hampir semua hal menggunakan grafik. Saya menggunakan peta, misalnya. Jika Anda menganggap setiap kota sebagai simpul, itu dapat dicapai dari banyak titik. Titik-titik yang mengarah ke simpul ini disebut pendahulu dan titik-titik yang akan dituju simpul ini disebut penerus.

diagram sirkuit 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:

masukkan deskripsi gambar di sini

Grafik:

masukkan deskripsi gambar di sini

Pastikan untuk merujuk ke tautan di bawah ini. Itu akan menjawab hampir semua pertanyaan Anda tentang pohon dan grafik.

Referensi :

  1. http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541

  2. http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/

  3. Wikipedia

mk ..
sumber
10

Jawaban lain berguna, tetapi mereka kehilangan properti masing-masing:

Grafik

Grafik tidak berarah, sumber gambar: Wikipedia

Grafik terarah, sumber gambar: Wikipedia

  • Terdiri dari satu set simpul (atau simpul) dan satu set tepi yang menghubungkan beberapa atau semuanya
  • Setiap sisi dapat menghubungkan dua simpul yang belum terhubung dengan sisi yang identik (dalam arah yang sama, dalam kasus graf berarah)
  • Tidak harus terhubung (tepi tidak harus menghubungkan semua simpul bersama-sama): satu grafik dapat terdiri dari beberapa set simpul yang tidak terhubung

  • Bisa diarahkan atau tidak diarahkan (yang akan berlaku untuk semua tepi dalam grafik)
    Sesuai Wikipedia :

    Misalnya, jika simpul mewakili orang di sebuah pesta, dan ada tepi di antara dua orang jika mereka berjabat tangan, maka grafik ini tidak berarah karena setiap orang A dapat berjabat tangan dengan orang B hanya jika B juga berjabat tangan dengan A. Sebaliknya, jika ada sisi dari orang A ke orang B sesuai dengan A mengagumi B, maka grafik ini diarahkan, karena kekaguman tidak selalu timbal balik.

Pohon

Sumber gambar: Wikipedia

  • Suatu jenis grafik
  • Simpul lebih sering disebut "node"
  • Tepi diarahkan dan mewakili hubungan "adalah anak dari" (atau "adalah induk dari")
  • Setiap node (kecuali node root) memiliki tepat satu induk (dan nol atau lebih anak)
  • Memiliki tepat satu node "root" (jika pohon memiliki setidaknya satu node), yang merupakan node tanpa induk
  • Harus terhubung
  • Apakah asiklik, artinya tidak memiliki siklus : "siklus adalah jalur [urutan AKA] dari tepi dan simpul di mana simpul dapat dijangkau dari dirinya sendiri"

Ada beberapa tumpang tindih pada properti di atas. Secara khusus, dua properti terakhir diterapkan oleh properti lainnya. Tapi semuanya tetap penting untuk diperhatikan.

Bernhard Barker
sumber
Gambar membuatnya sangat mudah dimengerti!
Raghav Gupta
3

Dalam pohon, setiap node (kecuali node root) memiliki tepat satu node pendahulu dan satu atau dua node penerus. Ini dapat dilalui dengan menggunakan traversal In-order, Pre-order, Post-order, dan Breadth First. Pohon adalah jenis grafik khusus yang tidak memiliki siklus sehingga dikenal dengan DAG (Directed Acyclic Graph). Pohon adalah model hierarki.

Dalam grafik, setiap node memiliki satu atau lebih node pendahulu dan node penerus. Grafik dilintasi menggunakan algoritma Depth First Search (DFS) dan Breadth First Search (BFS). Grafik memiliki siklus sehingga lebih kompleks dari pada pohon. Grafik adalah model jaringan. Ada dua jenis grafik: grafik berarah dan grafik tidak berarah.

Fouad Boukredine
sumber
2

Pohon sudah jelas: mereka adalah struktur data rekursif yang terdiri dari node dengan turunan.

Peta (alias kamus) adalah pasangan kunci / nilai. Berikan peta kunci dan itu akan mengembalikan nilai yang terkait.

Peta dapat diimplementasikan menggunakan pohon, saya harap Anda tidak merasa bingung.

UPDATE: Membingungkan "grafik" untuk "peta" sangat membingungkan.

Grafik lebih kompleks daripada pohon. Pohon menyiratkan hubungan orang tua / anak rekursif. Ada cara alami untuk melintasi pohon: kedalaman-pertama, luas-pertama, tingkat-urutan, dll.

Grafik dapat memiliki jalur satu arah atau dua arah antar node, menjadi siklik atau asiklik, dll. Saya akan menganggap grafik lebih kompleks.

Saya pikir pencarian sepintas dalam teks struktur data yang layak (misalnya "Manual Desain Algoritma") akan memberikan informasi yang lebih banyak dan lebih baik daripada sejumlah jawaban SO. Saya akan merekomendasikan agar Anda tidak mengambil rute pasif dan mulai melakukan riset untuk diri Anda sendiri.

duffymo
sumber
1
Maaf, maksud saya grafik, saya mengetik peta.
pengguna918304
"Membingungkan" grafik "untuk" peta "sangat membingungkan." :)
cpz
1
Mengatakan "grafik lebih kompleks daripada pohon" sama seperti mengatakan "Burung gagak lebih terspesialisasi daripada burung". Bukankah kita seharusnya mengatakan bahwa "Semua pohon adalah grafik, tetapi tidak semua grafik adalah pohon"?
dudewad
Saya tidak peduli enam tahun kemudian. Tentunya Anda dapat menggunakan waktu Anda dengan lebih baik di sini.
duffymo
1

Pohon adalah digraf sedemikian rupa sehingga:

a) dengan arah tepi dihapus, itu terhubung dan asiklik

  1. Anda dapat menghapus asumsi bahwa itu asiklik
  2. Jika terbatas, Anda dapat menghapus asumsi bahwa itu terhubung

b) setiap simpul kecuali satu, akar, memiliki derajat 1

c) akar memiliki derajat 0

  1. Jika hanya ada banyak node yang terbatas, Anda dapat menghapus asumsi bahwa root memiliki nilai nol atau asumsi bahwa node selain root memiliki derajat 1

Referensi: http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

BPL
sumber
0

Dalam matematika, grafik adalah representasi dari sekumpulan objek yang beberapa pasang objeknya dihubungkan dengan link. Objek yang saling berhubungan diwakili oleh abstraksi matematika yang disebut simpul, dan tautan yang menghubungkan beberapa pasang simpul disebut tepi. [1] Biasanya, grafik digambarkan dalam bentuk diagram sebagai sekumpulan titik untuk simpul, digabungkan dengan garis atau kurva untuk tepinya. Grafik merupakan salah satu objek kajian dalam matematika diskrit.

Narender sharma
sumber
0

satu simpul akar di pohon dan hanya satu orang tua untuk satu anak. Namun, belum ada konsep root node. Perbedaan lainnya adalah, pohon adalah model hierarki, sedangkan grafik adalah model jaringan.

Rajan Kumar Kharel
sumber
0

Pohon pada dasarnya adalah graf tidak berarah yang tidak mengandung siklus, sehingga dapat dikatakan bahwa pohon merupakan graf yang lebih terbatas. Namun pohon dan grafik memiliki aplikasi 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.

patel dhruv
sumber