กราฟและการแทนค่า

กราฟเป็นโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น นี่แสดงถึงข้อมูลโดยใช้โหนด และความสัมพันธ์โดยใช้ขอบ กราฟ G มีสองส่วน จุดยอดและขอบ จุดยอดจะแสดงโดยใช้ชุด V และขอบแสดงเป็นชุด E ดังนั้นสัญลักษณ์กราฟคือ G(V,E) มาดูตัวอย่างกันเพื่อให้ได้แนวคิด

ในกราฟนี้มีจุดยอดห้าจุดและขอบห้าจุด ขอบถูกชี้นำ ตัวอย่างเช่น หากเราเลือกจุดยอดที่เชื่อมระหว่างจุดยอด B และ D จุดยอดต้นทางคือ B และปลายทางคือ D ดังนั้นเราสามารถย้าย B ไปที่ D ได้ แต่ไม่สามารถย้ายจาก D ไปที่ B

กราฟไม่เป็นเชิงเส้น และไม่มีโครงสร้างปกติ เพื่อแสดงกราฟในหน่วยความจำ มีสไตล์ที่แตกต่างกันเล็กน้อย รูปแบบเหล่านี้คือ −

• การแสดงเมทริกซ์ที่อยู่ติดกัน
• การแสดงรายการขอบ
• การแสดงรายการที่อยู่ติดกัน

การแสดงเมทริกซ์ที่อยู่ติดกัน

เราสามารถแสดงกราฟโดยใช้เมทริกซ์ Adjacency เมทริกซ์ที่กำหนดคือเมทริกซ์ที่อยู่ติดกัน เป็นเมทริกซ์เลขฐานสอง สี่เหลี่ยมจัตุรัส และจากแถวที่ ith ถึงคอลัมน์ที่ j หากมีขอบ ตำแหน่งนั้นจะถูกทำเครื่องหมายเป็น 1 เมื่อเราพยายามแสดงกราฟแบบไม่มีทิศทางโดยใช้เมทริกซ์ที่อยู่ติดกัน เมทริกซ์จะสมมาตร

การแสดงรายการขอบ

กราฟสามารถแสดงโดยใช้อาร์เรย์หนึ่งมิติได้เช่นกัน นี้เรียกว่ารายการขอบ ในการนำเสนอนี้มีขอบอยู่ห้าขอบ สำหรับแต่ละขอบ องค์ประกอบแรกคือต้นทาง และส่วนที่สองคือปลายทาง สำหรับการแสดงกราฟแบบไม่บอกทิศทาง จำนวนองค์ประกอบในรายการขอบจะเพิ่มเป็นสองเท่า

การแทนรายการที่อยู่ติดกัน

นี่เป็นการแสดงกราฟอีกประเภทหนึ่ง เรียกว่ารายการที่อยู่ติดกัน การแสดงนี้ขึ้นอยู่กับรายการที่เชื่อมโยง ในแนวทางนี้ แต่ละโหนดจะมีรายการโหนดซึ่งเชื่อมต่อโดยตรงกับจุดยอดนั้น ที่ส่วนท้ายของรายการ แต่ละโหนดจะเชื่อมต่อกับค่า Null เพื่อบอกว่าเป็นโหนดสุดท้ายของรายการนั้น