CoE KKU

topological sort คือลำดับของ vertices ใน directed acyclic graph ที่ถ้ามี path หนึ่งจาก $v_i$ ไปยัง $v_j$, แล้ว $v_j$ มีลำดับที่ตามหลัง $v_i$

กราฟในรูปที่ 9.3 ใช้แทนโครงสร้างความต่อเนื่องของรายวิชา directed edge (v, w) บ่งชี้ว่าจะต้องเรียนและสอบผ่านวิชา v ให้ได้ก่อนจึงจะสามารถลงทะเบียนเรียนวิชา w ได้ ลำดับ topological ordering ของรายวิชาเหล่านี้ คือลำดับของรายวิชาที่เป็นไปตามข้อกำหนดเงื่อนไขรายวิชา (prerequisite)

แน่นอนว่าลำดับของ vertex แบบ topological ordering จะเป็นไปไม่ได้เลยสำหรับกราฟที่มี cycle เนื่องจาก vertices v และ w ในเส้นทาง cycle นั้นมีลำดับที่ v มาก่อน w และมี w มาก่อน v ก็ได้เช่นกัน ยิ่งกว่านั้นลำดับของ vertex ไม่จำเป็นต้องเป็นมีเพียงแบบเดียว (unique) กราฟรูปที่ 9.4, มีลำดับ $v1, v2, v5, v4, v3, v7, v6$ และมีลำดับ $v1, v2, v5, v4, v7, v3, v6$ ที่ลำดับทั้งสองแบบล้วนเป็น topological orderings

อัลกอริทึมอย่างง่ายในการหา topological ordering คือ เริ่มต้นด้วยการหา vertex ที่ไม่มี incoming edges และกำหนดให้มันเป็น vertex เริ่มต้น แล้วให้พิมพ์ชื่อ vertex นี้พร้อมกับย้ายมันพร้อมกับ edges ออกจากกราฟ จากนั้นก็ทำเช่นเดียวกันนี้กับส่วนที่เหลือในกราฟ

จากที่กล่าวมา เรากำหนดให้ indegree ของ vertex v คือจำนวนของ edges (u,v) ให้ทำการคำนวณค่า indegrees ของ vertices ทั้งหมดในกราฟ และถ้าหากว่าเรามีค่าของ indegree ของทุก vertex ได้รับการจัดเก็บไว้ใน indegree array และกราฟนั้นถูกจัดอยู่ใน adjacency list แล้ว เราก็สามารถใช้อัลกอริทึมในรูปที่ 9.5 เพื่อสร้าง topological ordering ของกราฟได้

void topsort() throws CycleFound 
{	vertex v, w;
	for ( int counter =  0; counter < NUM_VERTEX; counter++ )
	{	v = findNewVertexOfIndegreeZero( );
		if ( v == null )  throw new CycleFound();
		v.topNum = counter;
		for each w adjacent to v
		     w.indegree--;
	}
}

รูปที่ 9.5 Simple topological sort pseudocode

ฟังก์ชัน findNewVertexOfIndegreeZero เป็นเพียงการ scan ใน indegree array เพื่อหา vertex ที่มี indegree 0 และยังไม่ได้รับการกำหนดค่า topological number และฟังก์ชันจะให้ค่ากลับเป็น null กรณีที่ไม่พบ vertex ดังกล่าวซึ่งหมายความว่ากราฟนี้มี cycle

เนื่องจากฟังก์ชัน findNewVertexOfIndegreeZero ทำการ scan ไปในอะเรย์ของ vertices โดยที่การทำงานแต่ละครั้งใช้เวลา $O(|V|)$ และเนื่องจากมีการเรียกใช้เป็นจำนวน $|V|$ ครั้ง ดังนั้นมันจึงมี running time เป็น $O(|V|^2)$

จะเห็นได้ว่าสาเหตุที่มี running time ไม่ดีนั้นก็เนื่องมาจากการทำงานแบบ sequential scan ไปใน indegree array นั่นเอง ถ้าหากว่ากราฟเป็นแบบกระจาย (sparse) แล้วในการทำงานแต่ละรอบก็จะมี vertex จำนวนน้อยตัวที่มีการปรับเปลี่ยนค่า indegree เกิดขึ้น แต่ในการค้นหา vertex ที่มี indegree 0 เราก็ยังมีความเป็นไปได้ที่ยังคงต้องเข้าถึง vertex ทุกตัวในอะเรย์

เราสามารถปรับปรุงประสิทธิภาพได้ด้วยการนำ (unassigned) vertices ที่ยังไม่ได้รับการกำหนดหมายเลขทั้งหมดที่มี indegree เป็น 0 ไปไว้ในกล่องแยกต่างหาก ฟังก์ชัน findNewVertexOfIndegreeZero จะให้ค่ากลับเป็น (และย้ายออก) vertex จากกล่องดังกล่าว ขณะที่ทำการลดค่า indegrees ของ adjacent vertices ของมันนั้นเราจะตรวจค่าของมันและย้ายมันไปไว้ในกล่องดังกล่าวเมื่อค่า indegree ของมันลดลงเป็น 0

กล่องดังกล่าวข้างบนนั้น อาจจะใช้ stack หรือ queue ก็ได้ ในกรณีของเราจะใช้ queue โดยเริ่มต้นด้วยการคำนวณค่า indegree ของทุก ๆ vertex จากนั้นนำ vertices ที่มี indegree เป็น 0 ทั้งหมดไปไว้ใน queue ซึ่งเริ่มต้นเป็น queue ว่าง แล้วให้ทำการย้าย vertex v ออกจาก queue ตราบเท่าที่ queue ยังไม่เป็น queue ว่าง ขณะเดียวกันก็ให้ลดค่า indegrees ของ vextex ทุกตัวที่เป็น adjacent vertex กับ v และนำ vertex ไปเข้า queue ทันทีที่ indegree ของมันมีค่าเป็น 0 ลำดับของ vertex ที่เป็นแบบ topological ordering ที่จะได้ก็คือลำดับที่ vertices ถูก dequeue ออกมา รูปที่ 9.6 แสดงสถานะการทำงานแต่ละรอบ

pseudocode ของอัลกอริทึมแสดงในรูปที่ 9.7 โดยสมมุติให้มี adjacency list และค่า indegrees ของ vertices เรียบร้อยแล้ว และให้ vertex มีข้อมูลชื่อ topNum ซึ่งจะถูกกำหนดให้เป็น topological number ของมัน

เวลาที่ใช้ในการทำงานของอัลกอริทึมคือ $O(|E| + |V|)$ ถ้าใช้ adjacency lists ซึ่งจะเห็นได้จาก for loop ที่บรรทัดที่ 8 ที่มีการทำงานเพียงหนึ่งครั้งต่อหนึ่ง edge การทำงานของ queue เกิดขึ้นหนึ่งครั้งต่อหนึ่ง vertex, และการ initialization ก็ใช้เวลาตามแต่ขนาดของกราฟเช่นเดียวกัน

รูปที่ 9.6 ผลการทำ topological sort ของกราฟ 9.4

void  topSort( ) throws CycleFound 
{       Queue  q;  int counter;    vertex v, w;
/*1*/   q = new Queue( );
/*2*/   for each vertex v
/*3*/       if ( v.indegree ==  0 )
/*4*/           q.enqueue( v );
/*5*/   while ( !q.isEmpty() )
		{
/*6*/       v = q.dequeue( );
/*7*/       v.topNum = ++counter; /* assign next number */
/*8*/       for each w adjacent to v
/*9*/           if ( --w.indegree ==  0 )
/*10*/              q.enqueue( w );	   
        }
/*11*/  if  ( counter != NUM_VERTICES )
/*12*/      throw new CycleFound();
}

รูปที่ 9.7 Pseudocode ของ topological sort