ให้ G เป็นกราฟระบุทิศทาง (directed graph) และ S แทนกองซ้อน (stack) ที่ว่างเปล่า
While S ยังไม่ได้เก็บจุดยอดทุกจุด
เลือกจุดยอด v ที่ไม่อยู่ใน S แล้วทำ Depth-first search โดยเริ่มต้นที่ v จากนั้นทุกครั้งที่ Depth-first search เข้าไปถึงปม u จนเสร็จ ก็ให้ push u เข้าไปใน S
Pop จุดยอด v ออกมาจากกองซ้อน S แล้วทำ Depth-first search โดยเริ่มต้นที่ v จะพบว่าเซตของจุดยอดที่เข้าถึงได้จาก v จะเป็นส่วนประกอบที่เชื่อมกันแบบเข้มที่มี v อยู่ภายใน ดังนั้นก็จำจุดยอดเหล่านี้ไว้ และลบจุดยอดเหล่านี้ออกจากกราฟ G และกองซ้อน S
พิสูจน์ว่าขั้นตอนวิธีของโกสรชุนั้นใช้ได้จริง โดยพิสูจน์ว่าจุดยอด s และ t อยู่ในต้นไม้ค้นหาเชิงลึก (Depth-first search tree) ต้นเดียวกันในกราฟ G ก็ต่อเมื่อ s และ t นั้นอยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน
กรณีที่ 1 s และ t อยู่ในต้นไม้ค้นหาเชิงลึกคนละต้น
แสดงว่าเส้นเชื่อมใดๆ ระหว่างปมในต้นไม้ที่มี s กับปมในต้นไม้ที่มี t จะเป็นเส้นเชื่อมที่เชื่อมระหว่างต้นไม้ 2 ต้น เนื่องจากเส้นเชื่อมระหว่างต้นไม้สองต้นจะเดินทางไปได้ในทิศทางเดียวเท่านั้น จึงสรุปได้ว่า s และ t ไม่อยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน
กรณีที่ 2 s และ t อยู่ในต้นไม้ค้นหาเชิงลึกต้นเดียวกัน
กำหนดให้ r แทนรากของต้นไม้, G’ แทนทรานสโพสต์ของกราฟ G
มีทางเดิน (path) จาก s ไป r ในกราฟ G’ (เนื่องจากมีทางเดินจาก r ไป s ใน G)
r มีเลข postorder สูงกว่า s เมื่อทำการค้นหาเชิงลึกใน G’ (มิเช่นนั้น s จะต้องเป็นรากของต้นไม้)
r ต้องเป็นปมบรรพบุรุษของ s ในกราฟ G’ (เนื่องจาก 1 และ 2)
จะต้องมีทางเดินจาก r ไป s ใน G’ (เนื่องจาก 3)
มีทางเดินจาก r ไป s และจาก s ไป r ในกราฟ G (เนื่องจาก 1 และ 4)
s และ r นั้นอยู่ใน ส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน (เนื่องจาก 5)
ใช้เหตุผลเดียวกันในการพิสูจน์จุดยอด r และ t
จะได้ว่าถ้า s กับ r อยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน และ r กับ t อยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกัน แล้ว s กับ r ก็จะอยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกันด้วย
อ้างอิง
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd edition. The MIT Press, 2009. ISBN 0-262-03384-8.
แหล่งข้อมูลอื่น
A description and proof of Kosaraju's Algorithm
Good Math, Bad Math: Computing Strongly Connected Components
Java implementation at AlgoWiki.net
สิงหาคม 12, 2021
นตอนว, ของโกสรช, บทความน, อาจต, องการตรวจสอบต, นฉบ, ในด, านไวยากรณ, ปแบบการเข, ยน, การเร, ยบเร, ยง, ณภาพ, หร, อการสะกด, ณสามารถช, วยพ, ฒนาบทความได, งก, ามภาษา, ในบทความน, ไว, ให, านและผ, วมแก, ไขบทความศ, กษาเพ, มเต, มโดยสะดวก, เน, องจากว, เด, ยภาษาไทยย, งไม, บ. bthkhwamnixactxngkartrwcsxbtnchbb indaniwyakrn rupaebbkarekhiyn kareriyberiyng khunphaph hruxkarsakd khunsamarthchwyphthnabthkhwamidlingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudkhntxnwithikhxngoksrchu xngkvs Kosaraju s algorithm hrux khntxnwithikhxngoksrchu charir xngkvs Kosaraju Sharir algorithm epnkhntxnwithisahrbichha swnprakxbthiechuxmknaebbekhm khxngkrafrabuthisthang directed graph khntxnwithiniichpraoychncakhlkkhwamcringthiwa thransophskhxngkraf krafediywknthiesnechuxmthukesnklbthisthangcakkhxngedim camiswnprakxbthiechuxmknaebbekhm xnediywkbkrafnn enuxha 1 prawti 2 khntxnwithi 3 prasiththiphaphkarthangan 4 karphisucnkhntxnwithikhxngoksrchu 5 xangxing 6 aehlngkhxmulxunprawti aekikhinpi ph s 2521 oksrchu Sambasiva Rao Kosaraju sastracarysakhawithyakarkhxmphiwetxraehngmhawithyalycxnshxpkins chawxinediy idekhiynexksarwicy eruxngkhntxnwithikarkhanwnhaswnprakxbthiechuxmknaebbekhmkhxngkrafrabuthisthangxyangmiprasiththiphaph khntxnwithiniphayhlngidthukeriykwa khntxnwithikhxngoksrchu charir aetexksarwicydngklawimidthuktiphimph txmakhntxnwithinithukephyaephrodyxlefrd xaoh Alfred Aho cxhn hxpkhrxf John Hopcroft aelaecfefry xlaemn Jeffrey Ullman khntxnwithi aekikhxlkxruthumkhxngoksrchu charir nnmihlkkardngni ih G epnkrafrabuthisthang directed graph aela S aethnkxngsxn stack thiwangepla While S yngimidekbcudyxdthukcud eluxkcudyxd v thiimxyuin S aelwtha Depth first search odyerimtnthi v caknnthukkhrngthi Depth first search ekhaipthungpm u cnesrc kih push u ekhaipin S klbthiskhxngthukesnechuxmephuxcaid transpose khxngkraf While S imwang Pop cudyxd v xxkmacakkxngsxn S aelwtha Depth first search odyerimtnthi v caphbwaestkhxngcudyxdthiekhathungidcak v caepnswnprakxbthiechuxmknaebbekhmthimi v xyuphayin dngnnkcacudyxdehlaniiw aelalbcudyxdehlanixxkcakkraf G aelakxngsxn Shakich Breadth first search BFS aethn Depth first search kidphlxyangediywknprasiththiphaphkarthangan aekikhhakkrafthukekbkhxmulinrupaebb adjacency list emuxichxlkxruthumkhxngoksrchu charir caekidkaredinthangekhaipinkraf 2 khrng aelakar reverse krafxik 1 khrng aetenuxngcakeraich adjacency list ekbkhxmul eracasamarthsrangkraf reverse idkhnathiedinthangekhaipinkrafkhrngaerk thaihaethcringaelwkarewlakarthangancakhanwncakkaredinthangekhaipinkraf 2 khrngethann cungphbwaprasiththiphaphkhxngkhntxnwithiniethakb 8 V E esntrng emux V aethncanwncudyxd aela E aethncanwnesnechuxm sungthuxwaprasiththiphaphepn asymptotically optimal ephraaewlakarthangannntrngkbkhxbekhtlang lower bound ephraathuk khntxnwithicatxngtrwcsxbthukcudyxdkbesnechuxm dngnntamhlkkaraelwkhntxnwithiniepnkhntxnwithithingayaelamiprasiththiphaph aetinthangptibticamiprasiththiphaphtakwakhntxnwithikhxng Tarjan hruxkhntxnwithikhxng Gabow thisamarthhaswnprakxbthiechuxmknaebbekhmidodyedinthangekhaipinkrafephiyngaekhrxbediywthakrafthukekbkhxmulinrupaebb adjacency matrix khntxnwithicaichewlathangan O V2 karphisucnkhntxnwithikhxngoksrchu aekikhphisucnwakhntxnwithikhxngoksrchunnichidcring odyphisucnwacudyxd s aela t xyuintnimkhnhaechingluk Depth first search tree tnediywkninkraf G ktxemux s aela t nnxyuinswnprakxbthiechuxmknaebbekhmediywkn krnithi 1 s aela t xyuintnimkhnhaechinglukkhnlatnaesdngwaesnechuxmid rahwangpmintnimthimi s kbpmintnimthimi t caepnesnechuxmthiechuxmrahwangtnim 2 tn enuxngcakesnechuxmrahwangtnimsxngtncaedinthangipidinthisthangediywethann cungsrupidwa s aela t imxyuinswnprakxbthiechuxmknaebbekhmediywkn krnithi 2 s aela t xyuintnimkhnhaechingluktnediywknkahndih r aethnrakkhxngtnim G aethnthransophstkhxngkraf G mithangedin path cak s ip r inkraf G enuxngcakmithangedincak r ip s in G r mielkh postorder sungkwa s emuxthakarkhnhaechinglukin G miechnnn s catxngepnrakkhxngtnim r txngepnpmbrrphburuskhxng s inkraf G enuxngcak 1 aela 2 catxngmithangedincak r ip s in G enuxngcak 3 mithangedincak r ip s aelacak s ip r inkraf G enuxngcak 1 aela 4 s aela r nnxyuin swnprakxbthiechuxmknaebbekhmediywkn enuxngcak 5 ichehtuphlediywkninkarphisucncudyxd r aela t caidwatha s kb r xyuinswnprakxbthiechuxmknaebbekhmediywkn aela r kb t xyuinswnprakxbthiechuxmknaebbekhmediywkn aelw s kb r kcaxyuinswnprakxbthiechuxmknaebbekhmediywkndwyxangxing aekikhAlfred V Aho John E Hopcroft Jeffrey D Ullman Data Structures and Algorithms Addison Wesley 1983 Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Introduction to Algorithms 3rd edition The MIT Press 2009 ISBN 0 262 03384 8 aehlngkhxmulxun aekikhA description and proof of Kosaraju s Algorithm Good Math Bad Math Computing Strongly Connected Components Java implementation at AlgoWiki netekhathungcak https th wikipedia org w index php title khntxnwithikhxngoksrchu amp oldid 5882288, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
