ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมเกี่ยวกับกราฟ/เฉลยข้อ 8"
ไปยังการนำทาง
ไปยังการค้นหา
Cardcaptor (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย 'สมมติว่า <math>u \,</math> เป็น vertex และให้ <math>v_1, v_2, \ldots, v_k \,</math> เป็นลู…') |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 1 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 1: | แถว 1: | ||
สมมติว่า <math>u \,</math> เป็น vertex และให้ <math>v_1, v_2, \ldots, v_k \,</math> เป็นลูกของ <math>u \,</math> เราจะได้ว่า | สมมติว่า <math>u \,</math> เป็น vertex และให้ <math>v_1, v_2, \ldots, v_k \,</math> เป็นลูกของ <math>u \,</math> เราจะได้ว่า | ||
| − | : <math>z[u] = \ | + | : <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"> | <geshi lang="c"> | ||
| แถว 14: | แถว 14: | ||
if explored[v] = 0 then | if explored[v] = 0 then | ||
DFS(v) | DFS(v) | ||
| − | if z[v] | + | if z[v] > z[u] then |
z[u] = z[v] | z[u] = z[v] | ||
} | } | ||
} | } | ||
</geshi> | </geshi> | ||
| + | |||
| + | การหาค่า <math>z[u] \,</math> ของ vertex <math>u \,</math> ทั้งหมดทำได้โดยการรัน <math>\mathrm{DFS}(r) \,</math> ซึ่งทำงานในเวลา <math>O(|V| + |E|) \,</math> ตามต้องการ | ||
รุ่นแก้ไขปัจจุบันเมื่อ 14:02, 16 กันยายน 2552
สมมติว่า เป็น vertex และให้ เป็นลูกของ เราจะได้ว่า
![{\displaystyle z[u]=\max(z[v_{1}],z[v_{2}],z[v_{3}],\ldots ,z[v_{k}],x[u])\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/44da75996559c4785d846c48139b32bfdd020897)
ฉะนั้นเราสามารถหาค่า สำหรับทุก vertex โดยการปรับปรุง ใหม่ เพื่อให้หลังจาก ทำงานเสร็จแล้ว จะมีค่าถูกต้อง ดังต่อไปนี้
![{\displaystyle z[u]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f2ac6efb4a39063e386f18979feced82c4d5ab15)
<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>
การหาค่า ของ vertex ทั้งหมดทำได้โดยการรัน ซึ่งทำงานในเวลา ตามต้องการ
