คือว่ามีการบ้านครับ นั่งคิดมา 3 วัน คิดซูโดโค้ดยังไม่ออกเลยตึ้บมากเลยครับ
โจทย์คือมีกราฟให้มา(สมมุติเองตามสบาย) ให้หา spanning trees ทั้งหมดแล้วก็หา max spanning trees
ส่วนตัวเลยคิดว่าถ้าผมหา span ได้หมดก็คงหา max ได้แน่ๆเลยไม่ได้นั่งคิด max เลย
ตอนแรกผมสร้างกราฟโดยใช้คลาส graph กับ vertex ถึงจะมีเมธอดที่ทำไว้แล้วช่วยใช้งานได้บ้าง แต่ผมคิดไม่ออกเลยว่าจะหายังไง
ก็เลยไม่เอาคลาส graph แล้วเลยสร้างกราฟเป็น Array [][] เลย
ที่ผมพอจะคิดออกคือให้มันวิ่งเหมือน DFS ใน Array นี้ คือสมมุติเป็น 4*4
0 1 2 3
0 0 3 4 5
1 3 0 0 1
2 4 0 0 2
3 5 1 2 0
ถ้าวิ่งจากช่องแรกคือ 0 ก็จะเริ่มวิ่งไป 1 > 3 >2 ก็จะครบ พอครบก็ Backtrack กลับมาเชคเรื่อยๆจนครบทุกเคสที่เริ่มต้นด้วย 0
เงื่อนไขที่ต้องเชคก็น่าจะมีจุดที่ผ่านมาแล้ว แล้วก็จุดที่ weight เป็น 0 ถ้าจะทำให้ครบทุกจุดก็คงต้องเรียกแบบรีเคอซีฟ
แต่ทั้งหมดทั้งมวลผมก็ไม่สามารถเขียนแม้แต่ซูโดโค้ดออกมาได้เลย คิดไม่ออกบอกว่าจะให้วิ่งยังไง จะรีเคอซีฟยังไง
ใครพอจะแนะนำอะไรได้บ้างไหมครับมึนมากเลย มองอะไรไม่ออกเลยครับว่าจะโค้ดยังไง
ปล.ไม่อยากไปก๊อบโค๊ดคนอื่นรู้สึกไม่มีอะไรพัฒนาเลย ขอบคุณมากครับ
ช่วยไกด์ผมทีครับ หา Spanning Trees จาก GRAPH
โจทย์คือมีกราฟให้มา(สมมุติเองตามสบาย) ให้หา spanning trees ทั้งหมดแล้วก็หา max spanning trees
ส่วนตัวเลยคิดว่าถ้าผมหา span ได้หมดก็คงหา max ได้แน่ๆเลยไม่ได้นั่งคิด max เลย
ตอนแรกผมสร้างกราฟโดยใช้คลาส graph กับ vertex ถึงจะมีเมธอดที่ทำไว้แล้วช่วยใช้งานได้บ้าง แต่ผมคิดไม่ออกเลยว่าจะหายังไง
ก็เลยไม่เอาคลาส graph แล้วเลยสร้างกราฟเป็น Array [][] เลย
ที่ผมพอจะคิดออกคือให้มันวิ่งเหมือน DFS ใน Array นี้ คือสมมุติเป็น 4*4
0 1 2 3
0 0 3 4 5
1 3 0 0 1
2 4 0 0 2
3 5 1 2 0
ถ้าวิ่งจากช่องแรกคือ 0 ก็จะเริ่มวิ่งไป 1 > 3 >2 ก็จะครบ พอครบก็ Backtrack กลับมาเชคเรื่อยๆจนครบทุกเคสที่เริ่มต้นด้วย 0
เงื่อนไขที่ต้องเชคก็น่าจะมีจุดที่ผ่านมาแล้ว แล้วก็จุดที่ weight เป็น 0 ถ้าจะทำให้ครบทุกจุดก็คงต้องเรียกแบบรีเคอซีฟ
แต่ทั้งหมดทั้งมวลผมก็ไม่สามารถเขียนแม้แต่ซูโดโค้ดออกมาได้เลย คิดไม่ออกบอกว่าจะให้วิ่งยังไง จะรีเคอซีฟยังไง
ใครพอจะแนะนำอะไรได้บ้างไหมครับมึนมากเลย มองอะไรไม่ออกเลยครับว่าจะโค้ดยังไง
ปล.ไม่อยากไปก๊อบโค๊ดคนอื่นรู้สึกไม่มีอะไรพัฒนาเลย ขอบคุณมากครับ