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