418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 5 - ประวัติรุ่นแก้ไข

Aoy เมื่อ 17:38, 16 กันยายน 2552

2009-09-16T17:38:12Z

Aoy: หน้าที่ถูกสร้างด้วย 'อ.วัฒนา'

2009-09-09T10:27:06Z

หน้าที่ถูกสร้างด้วย 'อ.วัฒนา'

หน้าใหม่

อ.วัฒนา

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:38, 16 กันยายน 2552
แถว 1:		แถว 1:
−	อ.~~วัฒนา~~	+	แนวคิด เนื่องจากกราฟที่ให้มาเป็นกราฟแบบมีทิศทาง ดังนั้นเมื่อเรารัน DFS แล้วเราก็จะได้ edge แบบต่าง ๆ มา คือเป็น tree edge, back edge, forward edge และ cross edge ซึ่งตามนิยามเราจะได้ว่า back edge คือ edge ที่พุ่งออกจาก vertex ไปหาบรรพบุรุษของมัน นั่นก็คือ พุ่งกลับไปหา vertex ที่เคยสำรวจไปแล้วนั่นเอง ดังนั้นถ้ากราฟมี back edge เราก็สามารถสรุปได้ว่ากราฟมี cycle นั่นเอง นั่นแสดงว่าโจทย์ข้อนี้เราก็ทำการรัน DFS แล้วหาว่ามี back edge หรือไม่ ถ้ามีก็ทำการพิมพ์ cycle นั้นออกมา
		+
		+	นำแนวคิดข้างต้นไปเขียนเป็น pseudocode ได้ดังนี้
		+
		+	อัลกอริทึม CheckCycle จะทำการตรวจสอบว่ามี cycle อยู่ในกราฟหรือไม่ ถ้ามีจะทำการพิมพ์ออกมา โดยเรียก FindCycle และ PrintCycle ที่มีการทำงานเหมือนกับข้อ 3.2
		+	<geshi lang="c">
		+	CheckCycle()
		+	DFS(u)
		+	flag = 0
		+	for each u in V
		+	{
		+	for each edge (u,v) in E
		+	{
		+	if pre[v] < pre[u]< post[u] < post[v] then
		+	{
		+	flag = 1
		+	FindCycle(u,v)
		+	}
		+	}
		+	}
		+	</geshi>
		+
		+	เวลาการทำงานของ CheckCycle จะเป็นเวลาของ DFS บวกกับเวลาที่แต่ละ node ทำการตรวจสอบ edge ที่ติดกับมันว่าเป็น back edge หรือไม่ บวกกับเวลาของ FindCycle บวกกับเวลาของ PrintCycle ซึ่งเหมือนกับการวิเคราะห์ในข้อ 3.2 ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math> O(\|V\|+\|E\|) </math>