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

Cardcaptor เมื่อ 14:02, 16 กันยายน 2552

2009-09-16T14:02:01Z

Cardcaptor เมื่อ 14:00, 16 กันยายน 2552

2009-09-16T14:00:41Z

Cardcaptor: หน้าที่ถูกสร้างด้วย 'สมมติว่า $u \,$ เป็น vertex และให้ $v_1, v_2, \ldots, v_k \,$ เป็นลู…'

2009-09-16T13:57:04Z

หน้าที่ถูกสร้างด้วย 'สมมติว่า <math>u \,</math> เป็น vertex และให้ <math>v_1, v_2, \ldots, v_k \,</math> เป็นลู…'

หน้าใหม่

สมมติว่า <math>u \,</math> เป็น vertex และให้ <math>v_1, v_2, \ldots, v_k \,</math> เป็นลูกของ <math>u \,</math> เราจะได้ว่า
: <math>z[u] = \min(z[v_1], z[v_2], z[v_3], \ldots, z[v_k], x[u]) \,</math>
ฉะนั้นเราสามารถหาค่า <math>z[u] \,</math> สำหรับทุก vertex <math>u \,</math> โดยการปรับปรุง <math>\mathrm{DFS} \,</math> ใหม่ดังต่อไปนี้

<geshi lang="c">
DFS(u)
{
explored[u] = 1
z[u] = x[u]

for i = 1 to d[u] do
{
v = a[u][i]
if explored[v] = 0 then
DFS(v)
if z[v] < z[u] then
z[u] = z[v]
}
}
</geshi>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 14:02, 16 กันยายน 2552
แถว 19:		แถว 19:
	}		}
	</geshi>		</geshi>
		+
		+	การหาค่า <math>z[u] \,</math> ของ vertex <math>u \,</math> ทั้งหมดทำได้โดยการรัน <math>\mathrm{DFS}(r) \,</math> ซึ่งทำงานในเวลา <math>O(\|V\| + \|E\|) \,</math> ตามต้องการ

@@ แถว 1: / แถว 1: @@
 สมมติว่า <math>u \,</math> เป็น vertex และให้ <math>v_1, v_2, \ldots, v_k \,</math> เป็นลูกของ <math>u \,</math> เราจะได้ว่า
-: <math>z[u] = \min(z[v_1], z[v_2], z[v_3], \ldots, z[v_k], x[u]) \,</math>
+: <math>z[u] = \max(z[v_1], z[v_2], z[v_3], \ldots, z[v_k], x[u]) \,</math>
-ฉะนั้นเราสามารถหาค่า <math>z[u] \,</math> สำหรับทุก vertex <math>u \,</math> โดยการปรับปรุง <math>\mathrm{DFS} \,</math> ใหม่ดังต่อไปนี้
+ฉะนั้นเราสามารถหาค่า <math>z[u] \,</math> สำหรับทุก vertex <math>u \,</math> โดยการปรับปรุง <math>\mathrm{DFS} \,</math> ใหม่ เพื่อให้หลังจาก <math>\mathrm{DFS}(u) \,</math> ทำงานเสร็จแล้ว <math>z[u] \,</math> จะมีค่าถูกต้อง ดังต่อไปนี้
 <geshi lang="c">
@@ แถว 14: / แถว 14: @@
          if explored[v] = 0 then
              DFS(v)
-         if z[v] < z[u] then
+         if z[v] > z[u] then
              z[u] = z[v]
+     }
+}
 </geshi>

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

Cardcaptor เมื่อ 14:02, 16 กันยายน 2552

Cardcaptor เมื่อ 14:00, 16 กันยายน 2552

Cardcaptor: หน้าที่ถูกสร้างด้วย 'สมมติว่า u \, เป็น vertex และให้ v_1, v_2, \ldots, v_k \, เป็นลู…'

Cardcaptor: หน้าที่ถูกสร้างด้วย 'สมมติว่า $u \,$ เป็น vertex และให้ $v_1, v_2, \ldots, v_k \,$ เป็นลู…'