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

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

2009-09-16T03:55:52Z

2009-09-16T03:48:12Z

2009-09-16T03:43:51Z

อ.วัฒนา

2009-09-09T10:23:37Z

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

หน้าใหม่

== อ.วัฒนา ==

@@ แถว 5: / แถว 5: @@
 <geshi lang="c">
 DFS(u)
      for each node u in V
+     {
@@ แถว 11: / แถว 12: @@
              v= a[u][i]
              d[v] = d[v] + 1
-             add u in list of v
+             a[v][d[v]]= u  // add u in list of v
+         }
+     }
 </geshi>

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

	จากแนวคิดข้างต้น เขียนเป็น pseudocode ได้ดังนี้		จากแนวคิดข้างต้น เขียนเป็น pseudocode ได้ดังนี้
		+
		+	<geshi lang="c">
		+	DFS(u)
		+	for each node u in V
		+	{
		+	for i = 1 to d[u] do
		+	{
		+	v= a[u][i]
		+	d[v] = d[v] + 1
		+	add u in list of v
		+	}
		+	}
		+	</geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 03:43, 16 กันยายน 2552
แถว 1:		แถว 1:
−	~~== อ.วัฒนา ==~~	+	แนวคิด เราจะทำการพิจารณา node ทีละ node สมมติให้กำลังพิจารณาที่ node a แล้วดูว่า node a นั้นมี node อะไรอยู่ใน list ของมันบ้าง ถ้ามี เช่นมี node b อยู่ให้ทำการ เพิ่ม node a ใน list ของ node b แทน และทำการบวกจำนวน node ใน list ของ node b ขึ้นอีกหนึ่ง เมื่อทำแบบนี้จนครบทุก node จะได้ว่าเวลาการทำงานจะเป็น <math>O(\|V\|)</math> และสำหรับแต่ละ node จะทำการไล่ไปตาม list ของมัน ซึ่งจำนวนของ list ทั้งหมดใน directed graph จะมีเท่ากับจำนวน edge ในกราฟพอดี ดังนั้นเวลาการทำงานทั้งหมดจึงเป็น <math>O(\|V\|+\|E\|)</math>
		+
		+	จากแนวคิดข้างต้น เขียนเป็น pseudocode ได้ดังนี้