Graph

Graph

1. กราฟคืออะไร

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

 2.ลักษณะของกราฟ

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

3. ชนิดของกราฟ

3.1กราฟแบบไม่มีทิศทาง (Undirected Graph) 

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

                     V(G)  = {a, b, c, d}

                     E(G)  =  {(a,b) , (b,c), (c,d), (d,b), (a,c)}

                                   หรือ

                     E(G)  =  {(b,a) , (c,b), (d,c), (b,d), (c,a)}

3.2 กราฟมีทิศทาง

ตัวอย่าง

                   V(G)  = {a, b, c, d}

                   E(G)  =  {<a,b> , <a,c>, <b,d>, <d,c>, <c,b>}

4 อินดีกรีและเอาท์ดีกรี  

(In-degree) หรือ ระดับขั้นเข้า คือ จำนวนของเอดจ์ที่เข้าไปยังเวอร์เทกซ์นั้น ๆ

(Out-degree) หรือ ระดับขั้นออกคือ จำนวนของเอดจ์ที่ออกจากเวอร์ 

เทกซ์นั้น ๆ 

ก.กราฟแบบไม่มีทิศทาง

ข.กราฟแบบมีทิศทาง

5. กราฟสมบูรณ์

•กราฟที่ทุกเวอร์เท็กซ์มีเอดจ์เชื่อมโยงไปยังเวอร์เท็กซ์ที่เหลือทั้งหมด

ในกราฟสมบูรณ์แบบไม่มีทิศทางสามารถคำนวณจำนวนเอดจ์ได้จาก  
N*(N-1)/2

ก.กราฟสมบูรณ์แบบไม่มีทิศทาง

สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบไม่มีทิศทาง 

          = (N * (N – 1)) / 2

ข.กราฟสมบูรณ์แบบมีทิศทาง

สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบมีทิศทาง  =  N * (N –1)

6.การแทนกราฟในหน่วยความจำได้ 2 แบบดั่งนี้

6.1การแทนกราฟด้วยอะเรย์สองมิติ

• adjacency matrix แบบไม่มีทิศทาง

   

• adjacency matrix แบบมีทิศทาง

6.2 การแทนกราฟด้วยลิ่งลิสต์

• adjacency list 

7. การท่องไปในกราฟ (Graph  traversal)

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

•Breath First

•Depth First
7.1 การท่องแบบกว้าง (Breadth  first  traversal)   วิธีนี้ทำโดยเลือกโหนดที่เป็นจุดเริ่มต้น  ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นทีละระดับ จนกระทั่งเยือนหมดทุกโหนดในกราฟ   ตัวอย่างแสดงเส้นทางการท่องแบบกว้างทีละโหนดตามลำดับ
ตัวอย่างเช่น

การท่องไปแนวกว้างก็จะได้ดั่งนี้ = R A B C D E F G H  I J K

7.2 การท่องแบบลึก (Depth first traversal) การทำงานคล้ายกับการท่องทีละระดับของทรี  โดยกำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีนั้นจนกระทั่งนำไปสู่ปลายวิถีนั้น   จากนั้น ย้อนกลับ (backtrack) ตามแนววิถีเดิมนั้น   จนกระทั่งสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่น ๆ เพื่อเยือนโหนดอื่น ๆ ต่อไปจนครบทุกโหนด

ตัวอย่างเช่น

การท่องไปแนวกว้างก็จะได้ดั่งนี้ = R C I B F A E D