CoE KKU

ปัญหาที่จะกล่าวถึงต่อไป คือการหา minimum spanning tree ใน undirected graph กล่าวอย่างไม่เป็นทางการแล้ว minimum spanning tree ของ undirected graph G ก็คือ tree ที่สร้างจาก edge ของกราฟที่เชื่อมต่อ vertices ทั้งหมดของ G โดยที่มี cost รวมต่ำสุด จะมี minimum spanning tree จากกราฟได้ก็ต่อเมื่อกราฟ G นั้นต้องเป็นกราฟแบบ connected เท่านั้น ถึงแม้ว่าอัลกอริทึมที่ดีจะต้องสามารถรายงานได้ในกรณีที่กราฟไม่เป็นแบบ connected ในระหว่างการทำงานของมันก็ตาม ในที่นี้เราให้ความสนใจเฉพาะที่มันเป็นกราฟแบบ connected เท่านั้น ภาพด้านล่างของรูปที่ 9.46 เป็น minimum spanning tree ของรูปกราฟแบบ undirected ด้านบน จะเห็นได้ว่าจำนวน edges ใน minimum spanning tree คือ |V| – 1 เท่านั้น ที่เรากล่าวว่า minimum spanning tree เป็น tree ก็เนื่องจากมันเป็น acyclic, มันเป็น spanning เนื่องจากมันครอบคลุมทุก vertex และเป็น minimum เนื่องจากมันประกอบด้วยจำนวน edge ที่น้อยที่สุดที่ยังครอบคลุมทุก vertex ได้

สำหรับ spanning tree T ใด ๆ แล้ว การเพิ่ม edge e หนึ่งเข้าไปใน T ก็จะทำให้เกิด cycle ขึ้น และถ้าเอา edge ใด ๆ ใน cycle ออกก็จะทำให้มันกลับเป็น spanning tree ดังเดิม Cost ของ spanning tree จะลดลงถ้าหากว่า e มี cost ต่ำกว่า cost ของ edge ที่ถูกเอาออกไปนั้น ถ้าการเพิ่มเติม edge ลงในทรีในระหว่างที่ทำการสร้าง spanning tree อยู่นั้นใช้เฉพาะ edge ที่มีค่า cost ต่ำที่สุดที่ไม่ก่อให้เกิด cycle ในทรี ก็จะทำให้ได้ทรีที่มี cost เป็นค่าต่ำสุดที่ไม่สามารถปรับปรุงให้ดีกว่าได้อีก อัลกอริทึมพื้นฐานในการแก้ปัญหา minimum spanning tree ที่จะกล่าวถึงในที่นี้มีสองอัลกอริทึม และทั้งสองก็เป็น greedy algorithm

วิธีหนึ่งที่ใช้ในการคำนวณหา minimum spanning tree คือการเพิ่มขนาดของทรีเป็นขั้น ๆ (stage) ต่อเนื่อง โดยในแต่ละขั้น เราจะเลือกโนดหนึ่งให้เป็นโนดรากและเพิ่ม edge และโนดของมันเข้าไปในทรี

ณ เวลาหนึ่งในอัลกอริทึม เราจะมีเซตของ vertices ที่ได้รวมอยู่ในทรีแล้วส่วน vertex นอกนั้นไม่นับรวมอยู่ในทรี และในการทำงานแต่ละ stage ก็จะเป็นการค้นหา vertex ใหม่เพื่อที่รวมเข้ากับทรีด้วยการเลือก edge (u, v) ที่ cost ของ (u, v) นั้นน้อยที่สุดในบรรดา edges ทั้งหมดที่มี u อยู่ใน tree และมี v ไม่อยู่ใน tree รูปที่ 9.47 แสดงการทำงานของอัลกอริทึมในการสร้าง minimum spanning tree ที่เริ่มจาก v1 เริ่มต้นมี v1 เป็น root ในทรีโดยที่ยังไม่มี edges ใด ๆ อยู่ การทำงานต่อไปแต่ละขั้นตอนจะเป็นการเพิ่ม edge หนึ่งและ vertex หนึ่งลงใน tree

โดยเนื้อแท้แล้ว Prim's algorithm นั้นเหมือน ๆ กันกับ Dijkstra's algorithm ที่ใช้ในการหา shortest path กล่าวคือในแต่ละ vertex จะเก็บค่า dv และ pv และตัวระบุสถานะ known หรือ unknown โดยที่ dv คือ ค่าน้ำหนักของ edge ที่สั้นที่สุดที่เชื่อมต่อ v ไปยัง vertex ที่เป็น known และ pv คือ vertex ตัวสุดท้ายที่ทำให้เกิดการเปลี่ยนแปลงใน dv ส่วนที่เหลือของอัลกอริทึมก็เป็นเช่นเดิมยกเว้นเกณฑ์ในการปรับเปลี่ยนค่าของ dv เนื่องจากนิยามของมันต่างกันใน 2 อัลกอริทึม เกณฑ์ที่ใช้ในปัญหาเวลานี้คือ หลังจากการเลือก vertex v แล้ว vertex w ที่เป็น adjacent vertex กับ v และยังเป็น unknown ให้กำหนดค่า dw = min(dw, cw,v)

รูปที่ 9.48 ตารางแสดงสถานะเริ่มต้นของการทำงานของ Prim's algorithm

รูปที่ 9.48 เป็นตารางแสดงสถานะเริ่มต้นของการทำงาน เลือก v1 และปรับปรุง v2, v3, และ v4 ผลที่เกิดขึ้นในตารางแสดงในรูปที่ 9.49 แสดงตารางผลการทำงานที่ได้

รูปที่ 9.49 ตารางแสดงสถานะหลังจาก v1 เป็น known

ต่อมาเลือก v4 เป็น vertex ต่อไปและพบว่าทุก vertex เป็น adjacent กับ v4 แต่ไม่ต้องตรวจสอบ v1 เนื่องจากมันผ่านการทำงานแล้ว (คือ known) v2 ไม่เปลี่ยนแปลงเพราะว่ามันมี dv = 2 และ edge cost จาก v4 ไป v2 คือ 3 (ซึ่งมากกว่าค่าเดิมคือ 2) ที่เหลือนอกนั้นต้องมีการปรับเปลี่ยน รูปที่ 9.50

รูปที่ 9.50 ตารางแสดงสถานะหลังจาก v4 เป็น known

ต่อไปเลือก vertex v2 ซึ่งไม่มีผลใด ๆ ต่อระยะทาง จากนั้นเลือก v3 ซึ่งมีผลต่อระยะของ v6, ทำให้ได้ผลดังรูปที่ 9.51

รูปที่ 9.51 ตารางแสดงสถานะหลังจาก v2 และ v3 เป็น known

รูปที่ 9.52 เป็นผลจากการเลือก v7 ซึ่งทำให้มีการปรับเปลี่ยน v6 และ v5

รูปที่ 9.52 ตารางแสดงสถานะหลังจาก v7 เป็น known

ต่อไปเลือก v6 แล้วตามด้วย v5 เป็นอันจบการทำงานของอัลกอริทึม

รูปที่ 9.53 ตารางแสดงสถานะหลังจาก v6 และ v5เป็น known (อัลกอริทึมจบการทำงาน)

รูปที่ 9.53 แสดงตารางสุดท้ายที่ได้ edges ที่ปรากฏใน spanning tree สามารถอ่านได้จากตารางซึ่งก็คือ (v2, v1), (v3, v4), (v4, v1), (v5, v7), (v6, v7), (v7, v4) และค่า cost รวมคือ 16

การทำงานของอัลกอริทึมนี้ก็เหมือนกันกับ Dijkstra's algorithm ดังนั้นสิ่งที่กล่าวมาแล้วในการวิเคราะห์ Dijkstra's algorithm ก็ใช้ได้กับอัลกอริทึมนี้ เนื่องจาก Prim's algorithm ใช้สำหรับ undirected graphs ดังนั้นในการเขียนโปรแกรมจะต้องไม่ลืมกำหนดให้แต่ละ edge ปรากฏอยู่ใน adjacency lists สองครั้งด้วย ถ้าไม่ใช้ heap อัลกอริทึมนี้มี running time เป็น O (|V|2) ซึ่งเหมาะสมกับ dense graphs, และเป็น O (|E| log |V|) ถ้าใช้ binary heaps ซึ่งเหมาะกับ sparse graphs

อีกวิธีของอัลกอริทึมที่เป็น greedy algorithm เช่นกัน คือจะทำการเลือก edges ไปเรื่อย ๆ เรียงลำดับตาม weight จากที่มีค่าน้อยที่สุดขึ้นไปและจะนำ edge นั้นไปใช้ในทรีถ้ามันไม่ก่อให้เกิดการวนรอบ (cycle) การทำงานของอัลกอริทึมกับกราฟในตัวอย่างที่แล้วแสดงในรูปที่ 9.54

รูปที่ 9.54 การทำงานของ Kruskal's algorithm

กล่าวอีกอย่างหนึ่ง Kruskal's algorithm จะทำการสร้างกลุ่มของทรีขึ้น เรียกว่า forest โดยเริ่มต้น forest ประกอบด้วยทรีที่มีโนดเดียวจำนวน |V| ทรี การเพิ่ม edge เข้าไปหนึ่ง edge จะเป็นการควบรวมทรีสองทรีเข้าเป็นทรีเดียว เมื่อจบการทำงานของอัลกอริทึมก็จะเหลือทรีอยู่ 1 ทรีและเป็น minimum spanning tree รูปที่ 9.55 แสดงลำดับการเพิ่ม edge ลงใน forest ในระหว่างการทำงานของอัลกอริทึมและจะหยุดทำงานเมื่อมี edge พอเพียง การตัดสินใจที่จะยอมรับ edge หรือไม่ก็สามารถทำได้ด้วยการใช้โครงสร้างข้อมูล union/find algorithm ในบทที่ผ่านมา

สิ่งที่ใช้ในการตัดสินใจระหว่างกระบวนการทำงานคือ vertices 2 vertices เป็นสมาชิกของเซตเดียวกันก็ต่อเมื่อพวกมันเชื่อมต่อกันอยู่ใน spanning forest ที่มีอยู่ขณะนั้น นั่นหมายความว่าในตอนเริ่มต้นการทำงานนั้นแต่ละ vertex เป็นสมาชิกของเซตของมันเอง ถ้าหากว่า u และ v อยู่ในเซตเดียวกันแล้วเราก็จะปฏิเสธ edges ของมันเนื่องจากมันเชื่อมต่อกันอยู่แล้วและถ้าเพิ่ม edge (u, v) เข้าไปใหม่อีกก็จะทำให้เกิด cycle ขึ้น และถ้าไม่เป็นดังที่กล่าวมานี้ก็จะยอมรับ edge นั้นและจะทำงาน union กับเซตทั้งสองที่มี u และมี v เป็นสมาชิก จะเห็นได้ว่า หลังจากที่ได้เพิ่ม edge (u, v) ลงใน spanning forest แล้ว ถ้ามี vertex w เชื่อมต่ออยู่กับ u และ vertex x เชื่อมต่ออยู่กับ v ก็หมายความว่า w และ x ต้องมีการเชื่อมต่อกันแล้วทั้งนี้เนื่องจากพวกมันเป็นสมาชิกของเซตเดียวกัน

เราสามารถทำการจัดเรียงขนาดของ edge เพื่อทำการเลือกแต่การใช้วิธีการสร้าง heap ด้วยเวลาเป็น linear น่าเป็นวิธีที่ดีกว่า และการ deleteMin ทำให้ได้ edge เรียงตามลำดับ weight รูปที่ 9.56 แสดง Method kruskal ใช้ในการหา minimum spanning tree

public void kruskal( )
{
	    int edgesAccepted;
	    DistjSet 	s;
	    PriorityQueue 	h;
	    Vertex 	u, v;
	    SetType  uset, vset;
	    Edge 	e;
/*1*/   h = readGraphIntoHeapArray( );
/*2*/	h.buildHeap();
/*3*/	s = new DisjSet( NUM_VERTICES );
/*4*/   edgesAccepted = 0;
/*5*/   while ( edgesAccepted < NUM_VERTICES - 1 )
	    {
/*6*/        e = h.deleteMin( H );  /*e = (u, v) */
/*7*/     	 uset = s.find( u );
/*8*/        vset = s.find( v );
/*9*/   	 if ( uset != vset )
		     {
/*10*/    	    /* accept the edge */
/*11*/      	edgesAccepted++;
/*12*/ 		    s.union( uset, vset );
		     }
	    }
}

รูปที่ 9.56 Pseudocode ของ Kruskal's algorithm

อัลกอริทึมมี worst-case running time เป็น $O(|E|\ log\ |E|)$ ซึ่งเป็นการทำงานของ heap เป็นส่วนใหญ่ และจะเห็นว่าเนื่องจาก $|E| = O(|V|^2)$ ดังนั้น running time ก็คือ $O(|E|\ log\ |V|)$