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

Aoy: /* ข้อย่อย 2 */

2009-09-16T17:25:21Z

ข้อย่อย 2

Aoy: /* ข้อย่อย 2 */

2009-09-16T17:20:00Z

ข้อย่อย 2

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

2009-09-16T17:04:52Z

Aoy: /* ข้อย่อย 1 */

2009-09-16T16:58:21Z

ข้อย่อย 1

Aoy: /* ข้อย่อย 1 */

2009-09-16T16:57:40Z

ข้อย่อย 1

Aoy: /* ข้อย่อย 1 */

2009-09-16T16:48:04Z

ข้อย่อย 1

Aoy: /* ข้อย่อย 1 */

2009-09-16T16:43:04Z

ข้อย่อย 1

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

2009-09-09T10:24:49Z

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

หน้าใหม่

== ข้อย่อย 1 ==
อ.วัฒนา
== ข้อย่อย 2 ==
อ.วัฒนา

@@ แถว 59: / แถว 59: @@
 DFS(b)
      flag = 0 // ให้ flag เป็นตัวแปรที่บอกว่ากราฟมี cycle ที่มี edge (a,b) อยู่หรือไม่
-    explored[b]=1
+        explored[b]=1
      for each edge (b,v) in E // สำหรับแต่ละ edge (b,v) ที่กำลังพิจารณา ในที่นี้คือมี edge ชี้จาก b ไป v
+     {
          if b = a and v = b // ถ้า node ต้นทางนั้นเป็น a และ node ปลายทางเป็น b จะได้ว่า edge ที่กำลังพิจารณาคือ edge ที่โจทย์กำหนดนั่นเอง
-−
+               {
           flag = 1
           FindCycle(b,v)
@@ แถว 98: / แถว 98: @@
          print (C[i],C[i+1])
 </geshi>

@@ แถว 52: / แถว 52: @@
 == ข้อย่อย 2 ==
-สังเกตว่าเมื่อเราพิจารณา edge <math> (u,v) \, </math> ใด ๆ การที่เราจะหาว่า edge ดังกล่าวอยู่ใน cycle หรือไม่ ก็มีสองวิธีการ คือเริ่มทำการ DFS จาก node <math> u \, </math> หรือไม่ก็ node <math> v \, </math> แต่การเริ่มจาก node <math> u \, </math> อาจได้ cycle ก็จริง แต่ cycle นั้นอาจไม่มี edge <math> (u,v) \, </math> อยู่ก็ได้ ดังนั้นเราควรเริ่มทำการหา DFS จาก node <math> v \, </math> ก่อน แล้วถ้ามันมี edge ย้อนกลับมาหา node <math> v \, </math> ก็จะได้ว่ากราฟมี cycle ที่มี edge <math> (u,v) \, </math> อยู่ด้วยนั่นเอง
+สังเกตว่าเมื่อเราพิจารณา edge <math> (a,b) \, </math> ใด ๆ การที่เราจะหาว่า edge ดังกล่าวอยู่ใน cycle หรือไม่ ก็มีสองวิธีการ คือเริ่มทำการ DFS จาก node <math> a \, </math> หรือไม่ก็ node <math> b \, </math> แต่การเริ่มจาก node <math> a \, </math> อาจได้ cycle ก็จริง แต่ cycle นั้นอาจไม่มี edge <math> (a,b) \, </math> อยู่ก็ได้ ดังนั้นเราควรเริ่มทำการหา DFS จาก node <math> b \, </math> ก่อน แล้วถ้ามันมี edge ย้อนกลับมาหา node <math> b \, </math> ก็จะได้ว่ากราฟมี cycle ที่มี edge <math> (a,b) \, </math> อยู่ด้วยนั่นเอง
 จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
 <geshi lang="c">
-DFS(u)
+DFS(b)
-     flag = 0
+    flag = 0 // ให้ flag เป็นตัวแปรที่บอกว่ากราฟมี cycle ที่มี edge (a,b) อยู่หรือไม่
-     exp
+    explored[b]=1
 </geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:04, 16 กันยายน 2552
แถว 52:		แถว 52:

	== ข้อย่อย 2 ==		== ข้อย่อย 2 ==
−	~~อ.วัฒนา~~	+	สังเกตว่าเมื่อเราพิจารณา edge <math> (u,v) \, </math> ใด ๆ การที่เราจะหาว่า edge ดังกล่าวอยู่ใน cycle หรือไม่ ก็มีสองวิธีการ คือเริ่มทำการ DFS จาก node <math> u \, </math> หรือไม่ก็ node <math> v \, </math> แต่การเริ่มจาก node <math> u \, </math> อาจได้ cycle ก็จริง แต่ cycle นั้นอาจไม่มี edge <math> (u,v) \, </math> อยู่ก็ได้ ดังนั้นเราควรเริ่มทำการหา DFS จาก node <math> v \, </math> ก่อน แล้วถ้ามันมี edge ย้อนกลับมาหา node <math> v \, </math> ก็จะได้ว่ากราฟมี cycle ที่มี edge <math> (u,v) \, </math> อยู่ด้วยนั่นเอง
		+
		+	จากแนวคิดข้างต้น นำมาเขียนเป็น pseudocode ได้ดังนี้
		+
		+	<geshi lang="c">
		+	DFS(u)
		+	flag = 0
		+	exp
		+	</geshi>

@@ แถว 32: / แถว 32: @@
           if a[u][i] != NIL
              flag = 1 // บอกว่ามี cycle ในกราฟ
-            PrintCycle(u,a[u][i])
+                        PrintCycle(u,a[u][i])
+         }
+     }

@@ แถว 6: / แถว 6: @@
 เขียน pseudocode ตามแนวคิดข้างต้น ได้ดังนี้
 <geshi lang="c">
 </geshi>

@@ แถว 1: / แถว 1: @@
 == ข้อย่อย 1 ==
-อ.วัฒนา
+แนวคิด สังเกตว่าถ้าเรารัน DFS เราก็จะได้ต้นไม้ที่ได้จากการสำรวจมาหนึ่งต้น ซึ่งจากคุณสมบัติของต้นไม้ จะไม่มี cycle แต่สำหรับข้อนี้กราฟของเราเป็น undirected graph ดังนั้นถ้ามี edge ที่อยู่ในกราฟ แต่ไม่อยู่ในต้นไม้ ก็แสดงว่า edge นั้นเชื่อมระหว่าง node ที่เคยสำรวจไปแล้ว ซึ่งจะได้ว่ามี cycle อยู่ในกราฟนั่นเอง
 == ข้อย่อย 2 ==
 อ.วัฒนา