Google         youtube            psv            สพม.11

กราฟแบบมัลติลิสต์

ในโครงสร้างกราฟแบบมัลติลิสต์ประกอบด้วย สองส่วนคือ ไดเร็กทอรี่ของโหนดและเซ็ตลิ้งค์ลิสต์ของเอจ แต่ละค่าในไดเร็กทอรี่คือแต่ละโหนดที่อยู่ในกราฟ ดังนั้น ค่าในไดเร็กทอรี่สำหรับโหนด i  จะชี้ไปยังลิ้งค์ลิสต์ที่เชื่อมต่อไปยังโหน ดที่เชื่อมติดกับโหนด iลิ้งค์ลิสต์เป็นเรคคอร์ดประกอบด้วยสองลิสต์ติดกันใช้ เป็นโหนดกัวและโหนดท้ายของเอจ ดังในรูปที่ 10.15 เป็นโครงสร้างของแต่ละเอจที่มี Edge(Vi,Vj)

โครงสร้างของแต่ละเอจจาก Vi  ไปยัง Vj

การ ใช้กราฟแบบมัลติลิสต์ตัวอย่างในรูปที่ 10.16 ซึ่งเป็นกราฟไม่มีทิศทางจากรูปที่ 10.7 และนอกจากจะเป็นกราฟแบบมัลติลิสต์แล้ว ยังมีลักษณะเป็นเซ็ตของเอจ {(1,2),(2,2),(2,3),(4,3),(3,5),(3,6)} ใน รูป (a) หรืออีกแบบหนึ่งเป็นเซ็ตของเอจ {(2,1),(2,2),(2,3),(3,4),(5,3), (3,6)} ในรูป (b)

สำหรับในกรณีของกราฟทิศทาง ถ้าหากนำมาใช้เป็นกราฟแบบมัลติลิสต์จะมีการปรับเปลี่ยนน้อยในการแยกแยะความแตกต่างของแต่ละเอจ

การวิ่งตามเส้นทางในกราฟ

แอ ปพลิเคชั่นที่เขียนขึ้นมาเมื่อใช้งานกราฟส่วนใหญ่ต้องเข้าไปเรียกใช้งานใน แต่ละโหนด เช่น การพิมพ์รายการกิจกรรมในระบบการบริหารจัดการโครงการ การแสดงผลระยะทางระหว่างเมือง เทคนิคพื้นฐานการวิ่งตามเส้นทางในกราฟ (Graph Traversal)ที่จะกล่าวถึง คือ การวิ่งตามแนวกว้างก่อน (Breadth – first) และการวิ่งตามแนวลึกก่อน (Depth – first)

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

การวิ่งตามแนวกว้างก่อน

การ วิ่งตามเส้นทางในกราฟตามแนวกว้างก่อน (Breath – first Traversal) หรือการค้นหาตามแนวกว้างก่อน (Breath – first Traversal) เริ่มด้วยการเลือกมาหนึ่งโหนดเป็นตำแหน่งเริ่มต้นและทำเครื่อง หมายว่าวิ่งผ่านมาแล้ว จากนั้นวิ่งไปยังโหนดทุกโหนดที่ติดกับโหนดนี้และยังไม่วิ่งผ่านและทำเครื่อง หมาย ทำเช่นนี้จะกระทั่งวิ่งผ่านทุก ๆ โหนดที่มีอยู่ในกราฟ การวิ่งตามแนวกว้างในกราฟจากรูปที่ 10.13 ผลจากการวิ่งไปยังแต่ละโหนดจะมีลำดับเป็น 1,2,3,4,5,6,7,8 หรือมีลำดับ เป็น 1,3,2,6,5,4,7,8 ก็ได้ ขึ้นอยู่กับการเลือกโหนดที่จะวิ่งผ่านทางด้านซ้ายหรือขวาก่อน

อัลกอริ ทึมการวิ่งตามเส้นทางในแนวกว้างก่อนจะใช้โครงสร้างข้อมูลคิวเพื่อเก็บโหน ดที่วิ่งผ่านไปแล้วในแต่ละระดับของกราฟ แต่ละโหนดที่เก็บในคิวจะใช้สำหรับวิ่งไปยังโหนดติดกันที่ยังไม่ได้วิ่งไป ทำจนวิ่งผ่านทุกโหนดในกราฟและสิ้นสุดลงเมื่อคิวว่าง อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างก่อนดังในตารางที่ 10.1

อัลอกอริทึมการวิ่งตามเส้นทางในกราฟตามแนวกว้างก่อน

ใน การวิ่งตามเส้นทางในแนวกว้างก่อนมีการวิ่งผ่านโหนดที่เป็นระดับต่อ ระดับ (Level – by – Lavel) โดยแต่ละโหนดระดับเดียวกันจะถูกเก็บไว้ในคิวเพื่อกลับมาเรียกใช้งาน ได้หลังจากการทำงานในระดับนี้เสร็จสิ้นลง ต่อจากนั้นวิ่งไปยังโหนดระดับถัดไปที่เชื่อมต่อกับโหนดเหล่านี้ ลักษณะของอัลกอริทึมเป็นการทำงานที่วนซ้ำแบบเดิม (Iterative) ที่หัวข้อที่ 3 และ 4 เมื่อนำการวิ่งตามเส้นทางในแนวกว้างกับกราฟทิศทางในรูปที่ 10.17 จะมีขั้นตอนหรือระดับเป็น ดังนี้

ตัวอย่างกราฟทิศทางกับเส้นทางการวิ่ง

1.       ในระดับแรกเริ่มต้นว่างผ่านที่โหนด A และเก็บในคิวได้ {A}

2.       ดึงโหนด A จากคิว เพื่อหาโหนดที่เชื่อมกันและวิ่งผ่านทุกโหนดพร้อมเก็บลงในคิวได้ {B,D,E}

A,B,D,E

3.    ดึงโหนด B จากคิว เพื่อหาโหนดที่เชื่อมกันและวิ่งผ่านทุกโหนดพร้อมเก็บลงในคิวได้

{D,E,F}

A,B,D,E,F

4.    ดึงโหนด D จากคิว เพื่อหาโหนดที่เชื่อมกันและวิ่งผ่านทุกโหนดพร้อมเก็บลงในคิวได้

{E,F,C,H}

A,B,D,E,F,C,H

5.    ดึงโหนด E จากคิว เพื่อหาโหนดที่เชื่อมกันคือ H ซึ่งวิ่งผ่านไปแล้ว ในคิวจะได้

{F,C,H}

A,B,D,E,F,C,H

6.    ดึงโหนด F จากคิว เพื่อหาโหนดที่เชื่อมกันและวิ่งผ่านทุกโหนดพร้อมเก็บลงในคิวได้

{C,H,I,G}

A,B,D,E,F,C,H,I,G

เมื่อ ดึงโหนดที่เหลือในคิวเพื่อหาโหนดที่เชื่อมต่อกันจะพบแต่โหนดที่วิ่งผ่านไป แล้วและคิวว่างจึงจบการทำงาน ก็จะได้โหนดที่ถูกวิ่งผ่านเรียงตามลำดับในแนวกว้างก่อนคือ A, B, D, E, F, C, H, I, G ถ้าให้โหนด B เริ่มต้นก่อน โหนดที่ถูกวิ่งผ่านเรียงตามลำดับในแนวกว้างก่อน คือ B, F, I, G, H, C, D

การวิ่งตามแนวลึกก่อน

ขณะ ที่การวิ่งตามเส้นทางในแนวกว้างก่อนมีการวิ่งผ่านโหนดเป็นระดับต่อระดับ แต่การวิ่งตามแนวเส้นทางในแนวลึกก่อน(Depth – first Traversal) หรือการค้นหาตามแนวลึกก่อน (Depth – first Search) จะเริ่มจากโหนดแรกวิ่งผ่านตามเส้นทางเพื่อไปยังโหนดสุดท้ายซึ่งไม่ สามารถวิ่งต่อไปได้อีก จากนั้นถอยกลับเพื่อวิ่งผ่านต่อไปยังเส้นทางอื่นที่อยู่ติดกันในโหนดก่อน หน้านี้และวิ่งจนครบทุกโหนดในกราฟ การวิ่งตามแนวลึกในกราฟจากรูปที่ 10.13 ผลจากการวิ่งไปยังแต่ละโหนดจะมีลำดับเป็น 1,2,4,8,5,7,3,6 หรือมีลำดับ เป็น 1,3,6,7,8. 2,5,4 ก็ได้ขึ้นกับการเลือกโหนดที่จะวิ่งผ่านทางด้านซ้ายหรือขวาก่อน

ขณะ ที่อัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างก่อนใช้การทำงานที่วนซ้ำแบบเดิม ส่วนการวิ่งตามเส้นทางในแนวลึกก่อนใช้การทำงานแบบเรียกตัวเองทำงานหรือรี เคอร์ซีฟ (Recursive) อัลกอริทึมการวิ่งตามเส้นทางในแนวลึกก่อนดังในตาราง ที่ 10.2

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

1.       เริ่มต้นวิ่งผ่านที่โหนด A

2.       ใช้รีเคอร์ซีฟวิ่งผ่านโหนด B และเก็บโหนดในสแตก {E,D}

A, B

3.       ใช้รีเคอร์ซีฟวิ่งผ่านโหนด F และเก็บโหนด G ในสแตก {E,D,G}

A, B,F

4.        ใช้รีเคอร์ซีฟวิ่งผ่านโหนด I

A, B, F, I

5.        ใช้รีเคอร์ซีฟวิ่งผ่านโหนด H

A, B, F, I, H

6.     ถอยกลับมาที่โหนด F ดึงโหนด G จากสแตก {E,D} และใช้รีเคอร์ซีฟวิ่งผ่านโหนด G

A, B, F, I, H, G

7.    ใช้รีเคอร์ซีฟวิ่งผ่านโหนด C

A, B, F, I, H, G, C

8.    ใช้รีเคอร์ซีฟวิ่งผ่านโหนด D

A, B, F, I, H, G, C, D

9.      ถอยกลับไปเรื่อย ๆ มาที่โหนด A ดึงโหนด D  จากสแตกแต่วิ่งผ่านไปแล้วจึงดึงโหนด E จากสแตก {} และใช้รีเคอร์ซีฟวิ่งผ่านโหนด E

A, B, F, I, H, G, C, D, E

การ นำอัลกอริทึมแบบรีเคอร์ซีฟมาใช้มีการทำงานเป็นช่วง ๆ ตามที่เรียกตัวเองมาใช้ การทำงานจะสิ้นสุดลงที่โหนดแรกเมื่อตอนเริ่มต้นโดยไม่มีโหนดเหลือในสแตกก้จ ะได้โหนดที่ถูกวิ่งผ่านเรียงตามลำดับในแนวลึกก่อน คือ A, B, F, I, H, G, C, D, E ถ้าเริ่มต้นที่โหนด B จะมีโหนดที่ถูกวิ่งผ่านเรียงตามลำดับในแนวลึกก่อน คือ B, F, I, H, G, C, D ส่วนโหนด A และ E ไม่สามารถวิ่งไปได้ เมื่อใช้อัลกอริทึมแบบรีเคอร์ซีฟจะมีการสร้างสแตกขึ้นมาทำงานให้อัตโนมัติ แต่ถ้าเปลี่ยนเป็นใช้การวนซ้ำแบบเดิมเช่นเดียวกับการวิ่งตามแนวกว้างต้อง สร้างสแตกและจัดการเอง

อัลกอริทึมที่นำมาใช้ในการค้นหาตามแนวลึกมัก ถูกนำมาใช้งานบ่อยกับกราฟทิศทาง เช่น ต้องการทราบว่าแต่ละโหนดในกราฟสามารถวิ่งไปถึงโหนดอื่น ๆ ได้หรือไม่ (Reachability)  จากที่ผ่านมาทราบว่าเมื่อเริ่มต้นที่โหนด B จะ ไม่สามารถวิ่งไปถึงโหนด Aและ E ได้

ตัวอย่างการใช้กราฟหาเส้นทางที่สั้นที่สุด

ปัญหา ซึ่งเป็นที่รู้จักคือการหาเส้นทางที่สั้นที่สุด (Routing Problem) เช่นการส่งข้อมูลในเครือจข่ายให้เร็วที่สุด การเลือกเส้นทางการบินระหว่างเมืองการส่งสินค้าทางรถยนต์ที่ต้องรวดเร็วและ ประหยัดน้ำมัน การออกแบบอัลกอริทึมเพื่อค้นหาเส้นทางที่สั้นที่สุด (Shortest Path Algorithm) จะนำอัลกอริทึมการวิ่งตามเส้นทางในแนวกว้างมาปรับปรุงและใช้กับ กราฟที่เอจมีน้ำหนักได้เป็นอัลกอริทึมดังในตารางที่ 10.3

ตารางที่ 10.3 อัลกอริทึมการหาเส้นทางที่สั้นที่สุดในกราฟ

4.2 สำหรับทุก ๆ โหนด W ที่เชื่อมต่อกับโหนด N ให้ทำดังนี้a.       เก็บค่าระยะทางที่สั้นที่สุดของโหนด W ห่างจากโหนดต้นทางb.       ถ้าโหนด W ยังไม่ถูกวิ่งผ่าน

b.1 วิ่งไปที่โหนด W ทำเครื่องหมายวิ่งผ่านแล้ว

b.2 เก็บโหนด W ไว้ในคิว

อัล กอริทึมที่มีประสิทธิภาพในการหาเส้นทางที่สั้นที่สุดในกราฟ เรียกว่า อัลกอริทึมของดิจสตรา (Dijkatra’s Algorithm) เป็นการหาเส้นทางที่สั้นที่สุดของโหนดหนึ่งไปยังโหนดอื่น ๆ โดยใช้น้ำหนักของเอจ เรียกว่า ระยะทางสั้นที่สุด (Shortest Distance) ในอัลกอริทึมมีการใช้อาร์เรย์ Distance เพื่อเก็บระยะทางของแต่ละ โหนดที่ห่างจากโหนดเริ่มต้น กำหนดค่าสูงสุด(Infinity) ให้กับทุกสมาชิก ใช้อาร์เรย์ Path บอกให้ทราบว่าโหนดนี้มาจากเส้นทางของโหนดใดและอาร์เร ย์ Visited บอกให้ทราบว่าโหนดนี้มีการวิ่งผ่านไปแล้ว ทั้งสามอาร์เรย์อาจนำมารวมเป็นอาร์เรย์ 2 มิติ การทำงานของอัลกอริทึมนี้เมื่อใช้กับกราฟทิศทางในรูปที่ 10.18 จะมีขั้นตอนดังนี้

กราฟทิศทางกับการหาเส้นทางที่สั้นที่สุด

1.       วิ่ง ผ่านที่โหนด V เป็นโหนดเริ่มต้น กำหนดค่า distance[0] = 0, Path[0] = 0, visited[0] = 1  ได้เป็นรูปที่ 10.19 (a) และเก็บโหนด V ลงในคิวลำดับความสำคัญ (Priority Queue) = {V} เพื่อโหนดที่มีระยะทางสั้นที่สุดถูกใช้งานก่อน

2.       ดึงโหน ด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด V และ V จะได้ว่าระยะทาง จาก V ถึง V คือ distance[0] + ระยะทางระหว่าง V กับ V = 0 + 2 = 2 ระยะทางจาก V ถึง V คือ distance[0] + ระยะทางระหว่าง V กับ V = 0 + 9 = 9

เมื่อเปรียบเทียบกับค่าเดิมพบว่าน้อยกว่าก็เก็บแทนในอาร์เร ย์ distance[1] และ     distance[5] เป็นรูปที่ 10.19 (b) Path[1], Path[5] = 0, visited[1], visited[5] = 1 เก็บโหนด V และ V ลงคิว = {V , V}

3.       ดึงโหนด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด V , V , V  จะได้ว่า

ระยะทางจาก V ถึง V คือ distance[1] + ระยะทางระหว่าง V กับ V = 2 + 8 = 10

ระยะทางจาก V ถึง V คือ distance[1] + ระยะทางระหว่าง V กับ V = 2 + 15 = 17

ระยะทางจาก V ถึง V คือ distance[1] + ระยะทางระหว่าง V กับ V = 2 + 6 = 8

เมื่อ เปรียบเทียบกับค่าเดิมพบว่าน้อยกว่าก็เก็บแทนในอาร์เรย์ distance[2], distance[3], distance[5] เป็นรูปที่ 10.19 (c) Path[2], Patch[3], Patch[5], = 1 visited[1], visited[3] = 1 และเก็บลงคิว = {V,V,V}

4.       ดึง โหนด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด  V จะได้ว่า ระยะทางจาก V ถึง V คือ distance[5] + ระยะทาง Vกับ V = 8 + 3 = 11 เมื่อเปรียบเทียบกับค่าเดิมพบว่าน้อยกว่าก็เก็บแทนในอาร์เร ย์ distance[4] เป็นรูปที่ 10.19 (d) Path[4] = 5 visited[4] = 1 และเก็บลงคิว = { V,V,V}

5.       ดึงโหนด V  ออกจากคิวหาโหนดที่ เชื่อมติดกันคือโหนด V จะได้ว่า ระยะทางจาก  V ถึง V คือ distance[2] + ระยะทางระหว่าง V กับ V = 10 + 1 = 11 ค่าที่ได้เมื่อเปรียบเทียบกับค่าเดิมพบว่าน้อยกว่าก็เก็บแทนในอาร์เร ย์ distance[3] เป็นรูปที่ 10.19 (e) Path[3] = 2 และคิว = {V,V} เนื่องจาก V ถูกวิ่งผ่านไปแล้วจึงไม่เก็บลงในคิวอีก

6.       ดึง โหนด V ออกจากคิวหาโหนดที่เชื่อมติดกันคือโหนด V , V จะได้ว่า ระยะทางจาก V ถึง V คือ distance[4] + ระยะทางระหว่าง V = 11 + 7 = 18 ระยะทางจาก V ถึง V คือ distance[4] + ระยะทางระหว่าง V กับ V = 11 + 3 = 14

ค่าที่ได้เมื่อเปรียบเทียบพบว่ามากกว่าค่าเดิมจึงไม่เก็บลงในอาร์เรย์เป็นรูปที่ 10.19 (f) และคิว = {V}

7.       ดึงโหนด V ออกจากคิวหาโหนดแต่ไม่มีเชื่อมติดกับโหนดใด และคิวว่างจึงจบการทำงาน

จาก ตัวอย่างเป็นการหาเส้นทางที่สั้นที่สุดโดยการเริ่มที่โหนด V  ไปหาโหนดใด ๆ ในกราฟระยะทางทราบได้จากอาร์เรย์distance ส่วนเส้นทางทราบได้จากอาร์เร ย์ Path เช่น ต้องการทราบเส้นทางที่สั้นที่สุดระหว่างโหนด V กับ V พบว่าระยะทางที่สั้น ที่สุด คือ 11 และมีเส้นทาง คือ V à V à V à V และมื่อเขียนเป็นโปรแกรมจะได้ดังในตารางที่ 10.4 คือ

ตารางที่ 10.4 ตัวอย่างโปรแกรม Graph.c

#include <stdio.h>

#include <stdilib.h>

#include <conio.h>

#include “prioritQ.h”

#define NODES 6

Main () {

              priorityQueues pque;

               int adjMatrix[NODES] [NODES] = {  {0,  2,  0,  0,  0,  9},

                                                                             {0,  0,  8,  15,  0,  6},

                                                                                          {0,  0,  0,  1,  0,  0},

                                                                                         {0,  0,  0,  0,  0,  0},

                                            {0,  0,  7,  3,  0,  9},

                                                                                                {0,  0,  0,  0,  3,  0}

                                                                                };

                     int distance [NODES] = {0,  100,  100,  100,  100,  100};

                     int path [NODES] = {0,  9,  9,  9,  9,  9};

                     int visited [NODES] = {1,  0,  0,  0,  0,  0};

                     pque = createPriorityQueue (  )  ;

                     Insert (  0 ,  0  ,  pque  );

                     While (! isEmpty (pque) ) {

                                  node = Remove (pque);

                                  for (I = 0; i< NODES, i++)

                                    if(adjMatrix[node] [i] > (distance [node]+adjMatrix[node] [i] )){

                                     distance[i] = distance[node]+adjMatrix[node][i];

                                       path[i] = node;

                                        }

                                        If(visited[i] = = 0) {

                                                  Insert(I, distance[i], pque);

                                                  Visited[i] = 1;

                                        }

                             }

             }

             For(I = 1; i< NODES; i++){

                           node  = i;

                           printf(“From node %d”, node);

                            while(node ! = 0) {

                                      node = path[node];

                                      printf(“- ->%d”,node);

                              }

                              Printf(“Distance = %d\n”,distance[i]);

                     }

                   free(pque);

                   getch();

             }

 

จาก ตัวอย่างโปรแกรมจะใช้กราฟทิศทางในรูปที่ 10.18 สร้างเป็นแมตทริกติดกันชื่อ adjMatrix เก็บค่าระยะทางโหนดที่เชื่อมติดกัน สร้างอาร์เรย์ distance, Path, visited ไว้เก็บค่าระยะทาง เส้นทางที่สั้นที่สุด และถูกวิ่งผ่านตามลำดับ เมื่อมีการวิ่งผ่านไปยังโหนดใดจะมีการเก็บระยะทางที่สั้นที่สุดโดยเปรียบ เทียบค่าเดิมที่ได้จากเส้นทางอื่นก่อนพร้อมกับเปลี่ยนเส้นทางให้ถูกต้อง ดังนี้

If(distance[i]>(distance[node]+adjMatrix[node][i])){

distance[i]=distance[node]+adjMatrix[node][i];

path[i]=node;

}

ใน ขั้นตอนท้ายเป็นการแสดงเส้นทางที่มีระยะทางที่สั้นที่สุดของแต่ละโหนดไปหา โหนดเริ่มต้น ในอัลกอริทึมนี้มีการใช้คิวลำดับความสำคัญที่ให้ค่าน้อยกว่าสำคัญกว่า จึงเขียนเป็น prioritQ.h ดังในตารางที่ 10.5 และเรียกมาใช้งานดังนี้

ตารางที่ 10.5 ตัวอย่างโปรแกรม priortQ.h

#define True 1

#define False 0

Struct queue{

                                int Priority[50];

                                int Item[50]

                                int maxsize;

                                int front;

                                int rear;

};

typedef struct queue Queue;

typedefr Queue*priorityQueues;

priorityQueues createPriorityQueue(){

                priorityQueues newQueue=malloc(sixeof(Queue));

                newQueue->maxsixe=50;

                newQueue->front=0;

                newQueue->rear=-1;

                return newQueue;

 

}

int isEmpty(priorityQueues q){

                it(q->rear < q->front)

                                return True;

                return False;

}

void Insert(int val, int pr, priorittyQueues q){

                int i;

                if(q->rear+1 < q->maxsize)

                                if(isempty(q)){

                                q->front=0;

                                q->rear=0;

                                q->Priority[q->reare]=pr;

                                q->Item[q->rear]=val;

                }

                else {

                                q->rear++;

                                for(i=q->rear; (i>q->front)&&(q->priority[i-1]>pr); i–){

                                                q->Item[i]=q->Item[i-1];

                                                q->priority[i]=q->Priority[i-1];

                                }

                                q->Item[i]=val;

                                q->Priority[i]=pr;

                }

                                else

                                                printf(“Queue is full !!!\n”);

}

int Remove(priorityQueues q){

                int val;

                if(isWmpty (q)){

                                printf(“Queue is empty !!!\n”;

                                return -1;

                }

                val= q->Item[q->front]);

                q->front++;

                return val;

 

 

{

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s