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

Aoy เมื่อ 16:14, 20 กันยายน 2552

2009-09-20T16:14:51Z

Aoy เมื่อ 07:55, 16 กันยายน 2552

2009-09-16T07:55:10Z

125.25.20.207 เมื่อ 07:53, 16 กันยายน 2552

2009-09-16T07:53:24Z

Aoy เมื่อ 07:30, 16 กันยายน 2552

2009-09-16T07:30:14Z

Aoy: หน้าที่ถูกสร้างด้วย 'สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ pos…'

2009-09-16T07:26:50Z

หน้าที่ถูกสร้างด้วย 'สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ pos…'

หน้าใหม่

สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ post มา ซึ่งอะเรย์ pre จะบอกถึงเวลาที่ node นั้น ๆ เริ่มต้นถูกสำรวจ ส่วนอะเรย์ post จะบอกถึงเวลาที่ node นั้น ๆ สำรวจเสร็จ ดังนั้นเราจะได้ว่า node <math> u, v \, </math> สอง node ใด ๆ ถ้า pre ของ u มากกว่า pre ของ v แสดงว่า node u ถูกสำรวจก่อน node v (มิเช่นนั้นก็กลับกัน) ส่วนถ้า post ของ u มากกว่า post ของ v ก็จะได้ว่า การสำรวจ u เสร็จทีหลังการสำรวจ v นอกจากนี้การสังเกตว่า topological ordering คือการนำ node ในกราฟมาเรียงลำดับจากซ้ายไปขวา แล้ว edge ทุก edge ในกราฟจะชี้จากซ้ายไปขวา พิจารณา edge ที่ชี้จาก u ไป v ใน DAG ใด ๆ จะได้ว่า post ของ u ต้องมากกว่า post ของ v เสมอ (ความจริงจากข้อย่อย 6.1) ดังนั้น ถ้าเราทำการหา DFSALL แล้วทำการ order node จาก node ที่มีค่า post มากไปน้อย เราก็จะได้ topological ordering ตามที่เราต้องการ

@@ แถว 47: / แถว 47: @@
      DFSALL()
      for i = 1 to n do
-         pring order[i]
+         print order[i]
 </geshi>

@@ แถว 2: / แถว 2: @@
 จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
 <geshi lang="c">
@@ แถว 23: / แถว 25: @@
      post[u] = clock
      order[j] = u // อะเรย์ order เก็บลำดับของการเรียงที่เราต้องการ
-    j = j-1 //การใส่ลำดับของ node นี้จะใส่จากหลังมาหน้า
+        j = j-1 //การใส่ลำดับของ node นี้จะใส่จากหลังมาหน้า
      clock = clock + 1
+}

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:53, 16 กันยายน 2552
แถว 1:		แถว 1:
	สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ post มา ซึ่งอะเรย์ pre จะบอกถึงเวลาที่ node นั้น ๆ เริ่มต้นถูกสำรวจ ส่วนอะเรย์ post จะบอกถึงเวลาที่ node นั้น ๆ สำรวจเสร็จ ดังนั้นเราจะได้ว่า node <math> u, v \, </math> สอง node ใด ๆ ถ้า pre ของ u มากกว่า pre ของ v แสดงว่า node u ถูกสำรวจก่อน node v (มิเช่นนั้นก็กลับกัน) ส่วนถ้า post ของ u มากกว่า post ของ v ก็จะได้ว่า การสำรวจ u เสร็จทีหลังการสำรวจ v นอกจากนี้การสังเกตว่า topological ordering คือการนำ node ในกราฟมาเรียงลำดับจากซ้ายไปขวา แล้ว edge ทุก edge ในกราฟจะชี้จากซ้ายไปขวา พิจารณา edge ที่ชี้จาก u ไป v ใน DAG ใด ๆ จะได้ว่า post ของ u ต้องมากกว่า post ของ v เสมอ (ความจริงจากข้อย่อย 6.1) ดังนั้น ถ้าเราทำการหา DFSALL แล้วทำการ order node จาก node ที่มีค่า post มากไปน้อย เราก็จะได้ topological ordering ตามที่เราต้องการ (มีข้อสังเกตอีกอย่างคือ เนื่องจากค่าในอะเรย์ post เป็นค่าของเวลา และเมื่อทำการบันทึกค่าของเวลาที่ node ใด ๆ ถูกสำรวจเสร็จแล้ว เราจะทำการเพิ่มค่าของตัวแปร clock ขึ้นอีกหนึ่ง จึงทำให้ค่าของอะเรย์ post เหล่านี้ไม่ซ้ำกันในแต่ละช่อง ดังนั้นถ้าเราเรียงตามค่า post ก็จะไม่มี node สอง node ใด ๆ อยู่ในลำดับซ้ำกันนั่นเอง)		สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ post มา ซึ่งอะเรย์ pre จะบอกถึงเวลาที่ node นั้น ๆ เริ่มต้นถูกสำรวจ ส่วนอะเรย์ post จะบอกถึงเวลาที่ node นั้น ๆ สำรวจเสร็จ ดังนั้นเราจะได้ว่า node <math> u, v \, </math> สอง node ใด ๆ ถ้า pre ของ u มากกว่า pre ของ v แสดงว่า node u ถูกสำรวจก่อน node v (มิเช่นนั้นก็กลับกัน) ส่วนถ้า post ของ u มากกว่า post ของ v ก็จะได้ว่า การสำรวจ u เสร็จทีหลังการสำรวจ v นอกจากนี้การสังเกตว่า topological ordering คือการนำ node ในกราฟมาเรียงลำดับจากซ้ายไปขวา แล้ว edge ทุก edge ในกราฟจะชี้จากซ้ายไปขวา พิจารณา edge ที่ชี้จาก u ไป v ใน DAG ใด ๆ จะได้ว่า post ของ u ต้องมากกว่า post ของ v เสมอ (ความจริงจากข้อย่อย 6.1) ดังนั้น ถ้าเราทำการหา DFSALL แล้วทำการ order node จาก node ที่มีค่า post มากไปน้อย เราก็จะได้ topological ordering ตามที่เราต้องการ (มีข้อสังเกตอีกอย่างคือ เนื่องจากค่าในอะเรย์ post เป็นค่าของเวลา และเมื่อทำการบันทึกค่าของเวลาที่ node ใด ๆ ถูกสำรวจเสร็จแล้ว เราจะทำการเพิ่มค่าของตัวแปร clock ขึ้นอีกหนึ่ง จึงทำให้ค่าของอะเรย์ post เหล่านี้ไม่ซ้ำกันในแต่ละช่อง ดังนั้นถ้าเราเรียงตามค่า post ก็จะไม่มี node สอง node ใด ๆ อยู่ในลำดับซ้ำกันนั่นเอง)
		+
		+	จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
		+
		+	<geshi lang="c">
		+	DFS(u)
		+	{
		+	j = n
		+	pre[u] = clock
		+	clock = clock + 1
		+	explored[u] = 1
		+
		+	for i = 1 to d[u] do
		+	{
		+	v = a[u][i]
		+	if explored[v] = 0 then
		+	{
		+	parent[v] = u
		+	DFS(v)
		+	}
		+	}
		+
		+	post[u] = clock
		+	order[j] = u // อะเรย์ order เก็บลำดับของการเรียงที่เราต้องการ
		+	j = j-1 //การใส่ลำดับของ node นี้จะใส่จากหลังมาหน้า
		+	clock = clock + 1
		+	}
		+	</geshi>
		+
		+
		+	<geshi lang="c">
		+	DFSALL()
		+	{
		+	for u = 1 to n do
		+	if explored[u] = 0 then
		+	{
		+	parent[u] = 0
		+	DFS(u)
		+	}
		+	}
		+	</geshi>
		+
		+	<geshi lang="c">
		+	Topological_DFSALL()
		+	DFSALL()
		+	for i = 1 to n do
		+	pring order[i]
		+	</geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:30, 16 กันยายน 2552
แถว 1:		แถว 1:
−	สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ post มา ซึ่งอะเรย์ pre จะบอกถึงเวลาที่ node นั้น ๆ เริ่มต้นถูกสำรวจ ส่วนอะเรย์ post จะบอกถึงเวลาที่ node นั้น ๆ สำรวจเสร็จ ดังนั้นเราจะได้ว่า node <math> u, v \, </math> สอง node ใด ๆ ถ้า pre ของ u มากกว่า pre ของ v แสดงว่า node u ถูกสำรวจก่อน node v (มิเช่นนั้นก็กลับกัน) ส่วนถ้า post ของ u มากกว่า post ของ v ก็จะได้ว่า การสำรวจ u เสร็จทีหลังการสำรวจ v นอกจากนี้การสังเกตว่า topological ordering คือการนำ node ในกราฟมาเรียงลำดับจากซ้ายไปขวา แล้ว edge ทุก edge ในกราฟจะชี้จากซ้ายไปขวา พิจารณา edge ที่ชี้จาก u ไป v ใน DAG ใด ๆ จะได้ว่า post ของ u ต้องมากกว่า post ของ v เสมอ (ความจริงจากข้อย่อย 6.1) ดังนั้น ถ้าเราทำการหา DFSALL แล้วทำการ order node จาก node ที่มีค่า post มากไปน้อย เราก็จะได้ topological ordering ตามที่เราต้องการ	+	สังเกตว่าหลังจากการรัน DFSALL แล้วจะได้ อะเรย์ pre และ post มา ซึ่งอะเรย์ pre จะบอกถึงเวลาที่ node นั้น ๆ เริ่มต้นถูกสำรวจ ส่วนอะเรย์ post จะบอกถึงเวลาที่ node นั้น ๆ สำรวจเสร็จ ดังนั้นเราจะได้ว่า node <math> u, v \, </math> สอง node ใด ๆ ถ้า pre ของ u มากกว่า pre ของ v แสดงว่า node u ถูกสำรวจก่อน node v (มิเช่นนั้นก็กลับกัน) ส่วนถ้า post ของ u มากกว่า post ของ v ก็จะได้ว่า การสำรวจ u เสร็จทีหลังการสำรวจ v นอกจากนี้การสังเกตว่า topological ordering คือการนำ node ในกราฟมาเรียงลำดับจากซ้ายไปขวา แล้ว edge ทุก edge ในกราฟจะชี้จากซ้ายไปขวา พิจารณา edge ที่ชี้จาก u ไป v ใน DAG ใด ๆ จะได้ว่า post ของ u ต้องมากกว่า post ของ v เสมอ (ความจริงจากข้อย่อย 6.1) ดังนั้น ถ้าเราทำการหา DFSALL แล้วทำการ order node จาก node ที่มีค่า post มากไปน้อย เราก็จะได้ topological ordering ตามที่เราต้องการ (มีข้อสังเกตอีกอย่างคือ เนื่องจากค่าในอะเรย์ post เป็นค่าของเวลา และเมื่อทำการบันทึกค่าของเวลาที่ node ใด ๆ ถูกสำรวจเสร็จแล้ว เราจะทำการเพิ่มค่าของตัวแปร clock ขึ้นอีกหนึ่ง จึงทำให้ค่าของอะเรย์ post เหล่านี้ไม่ซ้ำกันในแต่ละช่อง ดังนั้นถ้าเราเรียงตามค่า post ก็จะไม่มี node สอง node ใด ๆ อยู่ในลำดับซ้ำกันนั่นเอง)