Park-Kachen
08 กันยายน 2552
DTS09-02-09-2552
โครงสร้างข้อมูลกราฟ
กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนี่งของกราฟโดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด
กราฟมีลักษณะเป็นเซ็ตของจุด (Point) และเซ็ตของเส้น (Line) ซึ่งแต่ละเส้นทำหน้าที่เชื่อมต่อจุดเข้าด้วยกัน แต่ละจุดเรียกว่าโหนด (Node) ของกราฟและเส้นเรียกว่าเอจ (Edge) บางครั้งเอจจะเรียกว่าอาร์ค (Arc) และโหนดเรียกว่าเวอร์ทิค (Vertice) โดยกำหนดให้กราฟ G มีเซ็ตของโหนดเป็น VG และเซ็ตของเอจเป็น EG เช่นในรูปที่ 10.1 VG ={a,b,c,d} และ EG = {1,2,3,4,5,6,7,8} จำนวนสมาชิกที่มีใน VG เรียกว่าออเดอร์ (Order) ของกราฟ ถ้าออเดอร์เท่ากับ 0 คือ กราฟไม่มีสมาชิกเรียกว่านัลกราฟ (Null Graph)
รูปที่ 10.1 ตัวอย่างกราฟที่มีจำนวนสมาชิกออเดอร์เท่ากับ 4 เอาของแต่ละโหนดจะพิจารณาจากการเชื่อมต่อกัน เช่น เอจ 4 เชื่อมโหนด c กับ d และกำหนดเป็น Path (c,d) โดยตำแหน่งของสมาชิกไม่มีความสำคัญ ดังนั้น กราฟในรูปที่ 10.1 จึงเท่ากับกราฟในรูปที่ 10.2 ต่อไปนี้
รูปที่ 10.2 ตัวอย่างกราฟที่เท่ากับกราฟในรูปที่ 10.1 โดยตำแหน่งของโหนดที่ต่างกัน ในการเชื่อมต่อกันระหว่างสองโหนดอาจมีได้หลาย ๆ เอจ เช่น เอจ 5, 6, และ 7 ซึ่งเป็น Path (b,d) ทั้งหมด เช่นกันไม่มีเอจที่เป็น Path(a,d) บางเอจเชื่อมต่อกันเพียงโหนดเดียวกับตัวเองคือเอจ 8 ที่เป็น Path(a,a) แบบวนลูป
กราฟ G จะเป็นกราฟเรียบง่าย (Simple Graph) ในรูปที่ 10.3 ต้องเป็นไปตามเงื่อนไข ดังนี้
ต้องไม่มีการวนลูปของเอจเกิดขึ้นใน EG หรือมี Path(V,V)
ต้องไม่มีเอจมากกว่าหนึ่งเชี่อมต่อกันระหว่างสองโหนด
รูปที่ 10.3 ตัวอย่างกราฟเรียบง่าย
กราฟ G ถ้าไม่ใช่กราฟเรียบง่ายเรียกว่า มัลติกราฟ (Multigraph)
กราฟ G จะเป็นกราฟต่อกัน (Connected Graph) ก็ต่อเมื่อไม่สามารถแยกออกเป็นสองกราฟ ยกเว้นมีการตัดเอจใดเอจหนึ่งออกไป ส่วนกราฟที่ไม่ต่อกันดังวนรูปที่ 10.4 มีโหนด f และ h ไม่ต่อกับโหนดอื่น
รูปที่ 10.4 ตัวอย่างกราฟที่ไม่ต่อกัน
เส้นทาง
เส้นทางในกราฟ (Path) เป็นการจัดลำดับของเอจที่มีตั้งแต่หนึ่งหรือมากกว่าทำการเชื่อมต่อระหว่างสองโหนด ซึ่งกำหนดเป็น P(Vi,Vj) คือ เส้นทางการเชื่อมระหว่างโหนด Vi กับ Vj และถ้า P(Vi,Vj) มีในกราฟก็จะต้องอยู่ใน EG ดังนั้น ลำดับของเอจจะอยู่ในรูปแบบต่อไปนี้ P(Vi,Vj) = (Vi,X1) (X1,X2) . . . (Xn-1,Xn) (Xn,Vj) และจะได้ความยาวของเส้นทางเป็นจำนวนเอจที่ประกอบรวมกัน จากกราฟเรียบง่ายในรูปที่ 10.3 จะได้เส้นทางระหว่างโหนด b กับ d ดังนี้เส้นทาง 1 P(b,d) = (b,c)(c,d) ความยาวเท่ากับ 2เส้นทาง 2 P(b,d) = (b,c)(c,b)(b,c)(c,d) ความยาวเท่ากับ 4เส้นทาง 3 P(b,d) = (b,d) ความยาวเท่ากับ 1เส้นทาง 4 P(b,d) = (b,c)(c,b)(b,d) ความยาวเท่ากับ 3 โดยทั่วไปเส้นทางที่ต้องการและสนใจเลือกใช้คือ เส้นทางที่วิ่งผ่านโหนดเพียงครั้งเดียวเท่านั้น ก็จะได้เฉพาะเส้นทาง 1 กับ 3 ส่วนเส้นทาง 2 มีการวิ่งผ่านโหนด b และ c สองครั้งและเส้นทาง 4 วิ่งผ่านโหนด b สองครั้ง นอกจากนี้ยังสนใจเฉพาะเอจที่ถูกวิ่งผ่านเพียงครั้งเดียวเช่นกัน เนื่องจากช่วยให้อัลกอริทึมไม้ต้องล่าช้าที่ต้องกลับไปทำงานในเส้นทางเดิม
posted by Park-Kachen at 06:48
0 Comments:
แสดงความคิดเห็น
<< Home