กราฟเทียบกับต้นไม้
กราฟและต้นไม้ใช้ในโครงสร้างข้อมูล มีความแตกต่างบางอย่างระหว่างกราฟและแผนภูมิ ชุดของจุดยอดที่มีความสัมพันธ์แบบไบนารีเรียกว่ากราฟในขณะที่ต้นไม้เป็นโครงสร้างข้อมูลที่มีชุดของโหนดที่เชื่อมโยงถึงกัน
กราฟ
กราฟคือชุดของรายการที่เชื่อมต่อกันด้วยขอบและแต่ละรายการเรียกว่าโหนดหรือจุดยอด กล่าวอีกนัยหนึ่ง กราฟสามารถกำหนดเป็นชุดของจุดยอด และมีความสัมพันธ์แบบไบนารีระหว่างจุดยอดเหล่านี้
ในการใช้งานกราฟ โหนดจะถูกนำไปใช้เป็นวัตถุหรือโครงสร้าง ขอบสามารถแสดงได้หลายวิธีวิธีหนึ่งคือแต่ละโหนดสามารถเชื่อมโยงกับอาร์เรย์ขอบของเหตุการณ์ได้ หากข้อมูลถูกเก็บไว้ในโหนดแทนที่จะเป็นขอบ อาร์เรย์จะทำหน้าที่เป็นตัวชี้ไปยังโหนดและเป็นตัวแทนของขอบด้วย ข้อดีอย่างหนึ่งของวิธีนี้คือสามารถเพิ่มโหนดเพิ่มเติมลงในกราฟได้ โหนดที่มีอยู่สามารถเชื่อมต่อได้โดยการเพิ่มองค์ประกอบลงในอาร์เรย์ แต่มีข้อเสียอยู่อย่างหนึ่งเพราะต้องใช้เวลาในการพิจารณาว่ามีขอบระหว่างโหนดหรือไม่
วิธีอื่นในการทำเช่นนี้คือเก็บอาร์เรย์สองมิติหรือเมทริกซ์ M ที่มีค่าบูลีน การมีอยู่ของ edge จากโหนด i ถึง j ถูกระบุโดยรายการ Mij ข้อดีอย่างหนึ่งของวิธีนี้คือการค้นหาว่ามีขอบระหว่างสองโหนดหรือไม่
ต้นไม้
Tree ยังเป็นโครงสร้างข้อมูลที่ใช้ในวิทยาการคอมพิวเตอร์อีกด้วย คล้ายกับโครงสร้างของต้นไม้และมีชุดของโหนดที่เชื่อมโยงกัน
โหนดของต้นไม้อาจมีเงื่อนไขหรือค่านอกจากนี้ยังสามารถเป็นต้นไม้ของตัวเองหรือสามารถแสดงโครงสร้างข้อมูลที่แยกจากกัน มีโหนดเป็นศูนย์หรือมากกว่าในโครงสร้างข้อมูลแบบต้นไม้ หากโหนดมีลูก จะเรียกว่าโหนดแม่ของเด็กนั้น มีพาเรนต์ของโหนดได้ไม่เกินหนึ่งโหนด เส้นทางลงที่ยาวที่สุดจากโหนดไปยังใบไม้คือความสูงของโหนด ความลึกของโหนดแสดงโดยเส้นทางไปยังรูท
ในต้นไม้ โหนดบนสุดเรียกว่าโหนดรูท โหนดรูทไม่มีพาเรนต์เนื่องจากเป็นโหนดบนสุด จากโหนดนี้ การดำเนินการทรีทั้งหมดจะเริ่มต้นขึ้น โดยใช้ลิงก์หรือขอบ โหนดอื่นสามารถเข้าถึงได้จากโหนดรูท โหนดระดับล่างสุดเรียกว่าโหนดปลายสุดและไม่มีลูก โหนดที่มีจำนวนโหนดย่อยเรียกว่าโหนดภายในหรือโหนดภายใน
ความแตกต่างระหว่างกราฟและต้นไม้:
• ต้นไม้สามารถอธิบายได้ว่าเป็นกรณีพิเศษของกราฟที่ไม่มีลูปและวงจรในตัวเอง
• ต้นไม้ไม่มีลูปในขณะที่กราฟสามารถมีลูปได้
• มีสามชุดในกราฟ เช่น ขอบ จุดยอด และชุดที่แสดงถึงความสัมพันธ์ ในขณะที่ต้นไม้ประกอบด้วยโหนดที่เชื่อมต่อถึงกัน การเชื่อมต่อเหล่านี้เรียกว่าขอบ
• ในแผนผังมีกฎมากมายที่ระบุว่าการเชื่อมต่อของโหนดสามารถเกิดขึ้นได้อย่างไร ในขณะที่กราฟไม่มีกฎที่กำหนดการเชื่อมต่อระหว่างโหนด