ความแตกต่างระหว่าง Tree กับ Graph
เนื้อหา
ต้นไม้และกราฟมาอยู่ภายใต้หมวดหมู่ของโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้นซึ่ง tree มีวิธีที่มีประโยชน์มากในการแสดงความสัมพันธ์ระหว่างโหนดในโครงสร้างลำดับชั้นและกราฟตามรูปแบบเครือข่าย ต้นไม้และกราฟมีความแตกต่างจากความจริงที่ว่าโครงสร้างของต้นไม้ต้องเชื่อมต่อกันและไม่สามารถมีลูปได้ในขณะที่ในกราฟไม่มีข้อ จำกัด ดังกล่าว
โครงสร้างข้อมูลที่ไม่ใช่เชิงเส้นประกอบด้วยชุดขององค์ประกอบที่กระจายอยู่ในระนาบซึ่งหมายความว่าไม่มีลำดับดังกล่าวระหว่างองค์ประกอบตามที่มีอยู่ในโครงสร้างข้อมูลเชิงเส้น
-
- แผนภูมิเปรียบเทียบ
- คำนิยาม
- ความแตกต่างที่สำคัญ
- ข้อสรุป
แผนภูมิเปรียบเทียบ
| พื้นฐานสำหรับการเปรียบเทียบ | ต้นไม้ | กราฟ |
|---|---|---|
| เส้นทาง | มีเพียงจุดเดียวระหว่างจุดยอดทั้งสอง | อนุญาตให้มีมากกว่าหนึ่งเส้นทาง |
| โหนดรูท | มันมีรูตโหนดเดียว | กราฟไม่มีโหนดรูต |
| ลูป | ไม่อนุญาตให้ใช้ลูป | กราฟสามารถมีลูป |
| ความซับซ้อน | ซับซ้อนน้อยลง | ค่อนข้างซับซ้อนกว่า |
| เทคนิคการแวะผ่าน | สั่งซื้อล่วงหน้า, ในการสั่งซื้อและโพสต์สั่งซื้อ | การค้นหาแบบกว้างและแบบลึก |
| จำนวนขอบ | n-1 (โดยที่ n คือจำนวนโหนด) | ไม่ได้กำหนดไว้ |
| ประเภทของโมเดล | ตามลำดับชั้น | เครือข่าย |
ความหมายของต้นไม้
ต้นไม้ เป็นการรวบรวมข้อมูลรายการที่เรียกว่าโหนด เนื่องจากมีการกล่าวถึงข้างต้นว่า tree เป็นโครงสร้างข้อมูลที่ไม่ใช่เชิงเส้นซึ่งจัดเรียงรายการข้อมูลตามลำดับที่เรียง มันถูกใช้เพื่อแสดงโครงสร้างลำดับชั้นระหว่างองค์ประกอบข้อมูลที่หลากหลายและจัดระเบียบข้อมูลเป็นสาขาที่เกี่ยวข้องกับข้อมูล การเพิ่มขอบใหม่ในทรีทำให้เกิดลูปหรือวงจร
มีต้นไม้หลายชนิดเช่นต้นไม้ไบนารี, ต้นไม้ค้นหาแบบไบนารี, ต้นไม้ AVL, ต้นไม้ไบนารีแบบเธรด, ต้นไม้ B, ฯลฯ การบีบอัดข้อมูล, การจัดเก็บไฟล์, การจัดการการแสดงออกทางคณิตศาสตร์และต้นไม้เกมเป็นบางส่วนของการประยุกต์ใช้ต้นไม้ โครงสร้างข้อมูล.
คุณสมบัติของต้นไม้:
- มีโหนดที่กำหนดที่ด้านบนของต้นไม้ที่เรียกว่ารูทของต้นไม้
- รายการข้อมูลที่เหลือจะถูกแบ่งออกเป็นชุดย่อยที่แยกกันเรียกว่าทรีย่อย
- ต้นไม้ขยายความสูงไปทางด้านล่าง
- ทรีต้องเชื่อมต่อซึ่งหมายความว่าจะต้องมีเส้นทางจากรูทหนึ่งไปยังโหนดอื่นทั้งหมด
- ไม่มีลูปใด ๆ
- ต้นไม้มีขอบ n-1
มีคำศัพท์ต่าง ๆ ที่เกี่ยวข้องกับต้นไม้เช่นโหนดเทอร์มินัลขอบระดับระดับความลึกฟอเรสต์เป็นต้นในบรรดาคำเหล่านั้นบางคำอธิบายไว้ด้านล่าง
- ขอบ - บรรทัดที่เชื่อมต่อสองโหนด
- ชั้น - ต้นไม้ถูกแบ่งออกเป็นระดับในลักษณะที่โหนดรูทอยู่ที่ระดับ 0 จากนั้นลูกที่อยู่ตรงนั้นจะอยู่ที่ระดับ 1 และชายด์ที่อยู่ในระดับที่ 2 เป็นต้นไปจนถึงเทอร์มินัลหรือโหนดใบไม้
- ระดับ - มันคือจำนวนของทรีย่อยของโหนดในทรีที่กำหนด
- ความลึก - เป็นระดับสูงสุดของโหนดใด ๆ ในแผนผังที่กำหนดและรู้จักกันในชื่อ ความสูง.
- โหนดเทอร์มินัล - โหนดระดับสูงสุดคือโหนดเทอร์มินัลในขณะที่โหนดอื่น ๆ ยกเว้นเทอร์มินัลและรูทโหนดเป็นที่รู้จักกันว่าโหนดที่ไม่ใช่เทอร์มินัล
ความหมายของกราฟ
กราฟ ยังเป็นโครงสร้างข้อมูลทางคณิตศาสตร์ที่ไม่ใช่เชิงเส้นซึ่งสามารถแสดงโครงสร้างทางกายภาพชนิดต่าง ๆ ได้ ประกอบด้วยกลุ่มจุดยอด (หรือโหนด) และชุดของขอบที่เชื่อมต่อจุดยอดทั้งสอง จุดยอดบนกราฟแสดงเป็นจุดหรือวงกลมและขอบแสดงเป็นส่วนโค้งหรือส่วนของเส้น ขอบถูกแทนด้วย E (v, w) โดยที่ v และ w คือคู่ของจุดยอด การเอาขอบออกจากวงจรหรือกราฟที่เชื่อมต่อจะสร้างกราฟย่อยที่เป็นต้นไม้
กราฟถูกแบ่งออกเป็นหมวดหมู่ต่าง ๆ เช่นกำกับกำกับไม่ใช่เชื่อมต่อไม่เชื่อมโยงง่ายและหลายกราฟ เครือข่ายคอมพิวเตอร์, ระบบการขนส่ง, กราฟเครือข่ายทางสังคม, วงจรไฟฟ้าและการวางแผนโครงการเป็นส่วนหนึ่งของการประยุกต์ใช้โครงสร้างข้อมูลกราฟ มันยังใช้ในเทคนิคการจัดการชื่อเป็น ฮึกเหิม เทคนิคการประเมินและทบทวนโปรแกรม CPM (วิธีการหาเส้นทางวิกฤต) ซึ่งวิเคราะห์โครงสร้างกราฟ
คุณสมบัติของกราฟ:
- จุดยอดในกราฟสามารถเชื่อมต่อกับจำนวนจุดยอดอื่น ๆ โดยใช้ขอบ
- ขอบสามารถถูกทิศทางหรือกำกับ
- ขอบสามารถรับน้ำหนักได้
ในกราฟเรายังใช้คำศัพท์ต่าง ๆ เช่นจุดยอด, เส้นทาง, วัฏจักร, องศา, กราฟที่เชื่อมต่อ, กราฟสมบูรณ์, กราฟถ่วงน้ำหนักและอื่น ๆ ลองทำความเข้าใจกับคำศัพท์เหล่านี้
- จุดยอดที่อยู่ติดกัน - จุดยอด a อยู่ติดกับจุดสุดยอด b หากมีขอบ (a, b) หรือ (b, a)
- เส้นทาง - เส้นทางจากจุดสุดยอดแบบสุ่ม w คือลำดับของจุดยอดที่อยู่ติดกัน
- วงจร - เป็นเส้นทางที่จุดแรกและจุดสุดท้ายเหมือนกัน
- ระดับ - มันคือจำนวนของการตกกระทบของขอบที่จุดยอด
- กราฟที่เชื่อมต่อ - หากมีเส้นทางจากจุดสุดยอดแบบสุ่มไปยังจุดสุดยอดอื่น ๆ กราฟนั้นจะเรียกว่ากราฟที่เชื่อมต่อ
- ในต้นไม้มีเพียงเส้นทางเดียวระหว่างจุดยอดสองจุดใด ๆ ในขณะที่กราฟสามารถมีเส้นทางเดียวและทิศทางสองทิศทางระหว่างโหนด
- ในทรีมีโหนดรูทหนึ่งโหนดและเด็กทุกคนสามารถมีพาเรนต์เดียวได้ เทียบกับในกราฟไม่มีแนวคิดของโหนดรูต
- ต้นไม้ไม่สามารถมีลูปและลูปได้เองในขณะที่กราฟสามารถมีลูปและลูปได้เอง
- กราฟมีความซับซ้อนมากขึ้นเนื่องจากสามารถมีลูปและลูปได้เอง ในทางตรงกันข้ามต้นไม้นั้นเรียบง่ายเมื่อเปรียบเทียบกับกราฟ
- ต้นไม้ถูกสำรวจโดยใช้เทคนิค pre-order, in-order และ post-order สำหรับการสำรวจกราฟเราใช้ BFS (การค้นหาครั้งแรกกว้าง) และ DFS (การค้นหาครั้งแรกลึก)
- ต้นไม้สามารถมีขอบ n-1 ในทางตรงกันข้ามในกราฟไม่มีจำนวนขอบที่กำหนดไว้ล่วงหน้าและขึ้นอยู่กับกราฟ
- ต้นไม้มีโครงสร้างแบบลำดับชั้นในขณะที่กราฟมีโมเดลเครือข่าย
ข้อสรุป
กราฟและต้นไม้เป็นโครงสร้างข้อมูลที่ไม่ใช่เชิงเส้นซึ่งใช้ในการแก้ปัญหาที่ซับซ้อนต่าง ๆ กราฟเป็นกลุ่มของจุดยอดและขอบที่ขอบเชื่อมต่อคู่ของจุดยอดในขณะที่ต้นไม้ถือเป็นกราฟที่เชื่อมต่อน้อยที่สุดซึ่งจะต้องเชื่อมต่อและเป็นอิสระจากลูป
