โครงสร้างข้อมูล - โครงสร้างข้อมูลกราฟ
กราฟคือการแสดงภาพชุดของวัตถุที่คู่ของวัตถุบางคู่เชื่อมต่อกันด้วยลิงก์ วัตถุที่เชื่อมต่อกันจะแสดงด้วยจุดที่เรียกว่าverticesและลิงก์ที่เชื่อมต่อจุดยอดนั้นเรียกว่า edges.
ปกติกราฟคือคู่ของเซต (V, E), ที่ไหน V คือเซตของจุดยอดและ Eคือชุดของขอบที่เชื่อมต่อจุดยอดทั้งคู่ ดูกราฟต่อไปนี้ -
ในกราฟด้านบน
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
โครงสร้างข้อมูลกราฟ
กราฟทางคณิตศาสตร์สามารถแสดงในโครงสร้างข้อมูล เราสามารถแสดงกราฟโดยใช้อาร์เรย์ของจุดยอดและอาร์เรย์สองมิติของขอบ ก่อนที่เราจะดำเนินการต่อไปเรามาทำความคุ้นเคยกับคำศัพท์สำคัญ ๆ -
Vertex- แต่ละโหนดของกราฟแสดงเป็นจุดยอด ในตัวอย่างต่อไปนี้วงกลมที่มีป้ายกำกับแสดงถึงจุดยอด ดังนั้น A ถึง G จึงเป็นจุดยอด เราสามารถแสดงโดยใช้อาร์เรย์ดังที่แสดงในภาพต่อไปนี้ ที่นี่ A สามารถระบุได้ด้วยดัชนี 0 B สามารถระบุได้โดยใช้ดัชนี 1 และอื่น ๆ
Edge- Edge แสดงเส้นทางระหว่างจุดยอดสองจุดหรือเส้นระหว่างจุดยอดสองจุด ในตัวอย่างต่อไปนี้เส้นจาก A ถึง B, B ถึง C และอื่น ๆ แทนขอบ เราสามารถใช้อาร์เรย์สองมิติแทนอาร์เรย์ได้ดังภาพต่อไปนี้ ที่นี่ AB สามารถแสดงเป็น 1 ที่แถว 0 คอลัมน์ 1 BC เป็น 1 ที่แถว 1 คอลัมน์ 2 และอื่น ๆ โดยเก็บชุดค่าผสมอื่น ๆ เป็น 0
Adjacency- โหนดหรือจุดยอดสองจุดอยู่ติดกันหากเชื่อมต่อกันผ่านขอบ ในตัวอย่างต่อไปนี้ B อยู่ติดกับ A, C อยู่ติดกับ B และอื่น ๆ
Path- เส้นทางแสดงลำดับของขอบระหว่างจุดยอดทั้งสอง ในตัวอย่างต่อไปนี้ ABCD แสดงเส้นทางจาก A ถึง D
การทำงานขั้นพื้นฐาน
ต่อไปนี้เป็นการดำเนินการหลักพื้นฐานของกราฟ -
Add Vertex - เพิ่มจุดยอดให้กับกราฟ
Add Edge - เพิ่มขอบระหว่างจุดยอดทั้งสองของกราฟ
Display Vertex - แสดงจุดยอดของกราฟ
หากต้องการทราบข้อมูลเพิ่มเติมเกี่ยวกับกราฟโปรดอ่านกราฟทฤษฎีการสอน เราจะเรียนรู้เกี่ยวกับการสำรวจกราฟในบทต่อ ๆ ไป