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

โครงสร้างข้อมลู แบบ กราฟ (Graph) โดยนายรอสดี แวหะยี สาขาวชิ าเทคโนโลยีสารสนเทศ วิทยาลัยการอาชพี ปตั ตานีสานักงานคณะกรรมการการอาชวี ศึกษา

โครงสร้างข้อมลู แบบกราฟ (Graph) กราฟ (Graph) เปน็ โครงสรา้ งขอ้ มลู แบบไมใ่ ชเ่ ชงิเส้นอีกชนิดหน่ึง กราฟเป็นโครงสร้างข้อมูลท่ีมีการนาไปใช้ในงานท่ีเกี่ยวข้องกับการแก้ปัญหาท่ีค่อนข้างซับซ้อน เช่น การวางข่ายงานคอมพิวเตอร์ การวิเคราะห์เส้นทางวกิ ฤติ และปัญหาเส้นทางท่สี ้ันทส่ี ุด เปน็ ตน้

ตวั อยา่ ง ab B F G cA de C DE V = a,b,c,d,e E = {ab,ac,ad,be,ce,cd,edV = {A,B,C,D,E,F,G}E = {AB,AC,AD,CD,CF,DE,EF,FG,EG}

โครงสรา้ งขอ้ มูลแบบกราฟ (Graph) ศพั ท์ทีเ่ กย่ี วข้อง1. เวอร์เทก (Vertex) หมายถงึ โหนด2. เอดจ (Edge) หมายถึง เส้นเช่ือมต่อระหว่างเวอร์เท็กซ์ บนกราฟ แบบ Undirected Graph3. Arc หมายถงึ เสน้ ที่เช่ือมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Directed Graph4. ดีกรี (Degree) หมายถึง จานวนเส้นเข้าและออก ของ โหนดแต่ละโหนด5. แอดจาเซนท์โหนด (Adjacent Node) หมายถงึ โหนดท่ีมกี ารเชือ่ มโยงกัน

โครงสร้างขอ้ มูลแบบกราฟ (Graph)

โครงสรา้ งขอ้ มูลแบบกราฟ (Graph)แอดจาเซนท์โหนด (Adjacent Node) A กบั B ใช่ D กบั F ไม่ใช่

โครงสร้างข้อมลู แบบกราฟ (Graph)เสน้ ทาง (Path) ใช้เรียกลาดับของ เวอร์เทก (Vertex) ท่ีเช่ือมต่อ กันจากจุดหน่ึงไปยังอีกจุดหนง่ึ (A,B,C,D,E) (A,B,E,F)

โครงสร้างข้อมูลแบบกราฟ (Graph) Cycle Path ทปี่ ระกอบด้วยอย่างน้อย 3 Vertex และ มจี ุดเรม่ิ ตน้ และสนิ้ สุดเดียวกันเช่น (B,C,E,B) (B,C,D,E,B)

โครงสรา้ งข้อมูลแบบกราฟ (Graph) ลูป (Loop)มเี พียง Arc เดียวและมจี ดุ เร่มิ ต้นและสนิ้ สุดเดียวกนั

โครงสรา้ งขอ้ มลู แบบกราฟ (Graph)Directed Graph : มีการกาหนดทิศทาง Strongly Connectedทกุ ๆ 2 Vertex มี Path ทัง้ ไปและกลับ(ทกุ โหนดในกราฟมีพาทตดิ ต่อถงึ กนั หมด)

โครงสรา้ งข้อมลู แบบกราฟ (Graph)• Weakly Connected : มอี ย่างน้อย 2 Vertex ทม่ี ี Path ใน ทิศทางเดียว (บางโหนดไม่สามารติดต่อไปยงั ทุกโหนด ในกราฟนน้ั ได้) A ไป G ไดใ้ น ทศิ ทางเดยี ว

สูตรหาจานวนเอดจ์ของกราฟสมบรู ณ์แบบมที ิศทาง = N *(N –1)จากภาพที่ (ข) ซงึ่ เป็นกราฟแบบมที ิศทาง และจานวนเวอร์เทกซ์ทม่ี ีท้งั หมดเทา่ กบั 4 เวอร์เทกซ์ จงึ คานวณหาจานวนเอดจ์ไดด้ งั น้ี สูตรหาจานวนเอดจ์ของกราฟมีทศิ ทาง = N * (N –1) = 4 * ( 4 – 1) =4*3 = 12 เส้น