โครงสร้างข้อมูล - โครงสร้างข้อมูลกราฟ

กราฟคือการแสดงภาพชุดของวัตถุที่คู่ของวัตถุบางคู่เชื่อมต่อกันด้วยลิงก์ วัตถุที่เชื่อมต่อกันจะแสดงด้วยจุดที่เรียกว่า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 - แสดงจุดยอดของกราฟ

หากต้องการทราบข้อมูลเพิ่มเติมเกี่ยวกับกราฟโปรดอ่านกราฟทฤษฎีการสอน เราจะเรียนรู้เกี่ยวกับการสำรวจกราฟในบทต่อ ๆ ไป