# ขั้นตอนวิธีของโกสรชุ
ประวัติ 

ในช่วงคริสต์ศตวรรษที่ 14 ดินแดนโอะกินะวะมีการติดต่อค้าขายกับจีนแผ่นดินใหญ่มาอย่างต่อเนื่องตั้งแต่อดีต ก่อให้เกิดการแลกเปลี่ยนวัฒนธรรม ความรู้แขนงต่าง ๆ รวมถึงศิลปะการป้องกันตัว โอะกินะวะมีศิลปะการต่อสู้พื้นถิ่นของตนเองอยู่แล้ว และเมื่อผสมผสานกับทักษะจากมวยใต้ของจีน จึงพัฒนาขึ้นเป็นศิลปะป้องกันตัวรูปแบบใหม่ ซึ่งต่อมารู้จักกันในชื่อ "คาราเต้"

ชาวโอะกินะวะเรียกศิลปะนี้ว่า โทเต้ (唐手 Tode) หมายถึง "มือจีน" ในภาษาโอะกินะวะ ขณะที่ในภาษาญี่ปุ่นเรียกว่า โอะกินะวะเต้ (沖縄手 Okinawa Te) ซึ่งหมายถึง "มือแห่งโอะกินะวะ"

โอะกินะวะเต้แบ่งออกเป็นสามสำนักหลัก โดยตั้งชื่อตามเมืองที่เป็นศูนย์กลางของวิชานั้น ๆ ได้แก่:

ชูริเต้ (Shuri-te 首里手)

นาฮาเต้ (Naha-te 那覇手)

โทมาริเต้ (Tomari-te 泊手)

แต่ละสำนักมีจุดเด่นและแนวทางการฝึกฝนเฉพาะตัว ซึ่งภายหลังได้กลายเป็นรากฐานของสายคาราเต้ต่าง ๆ ในประเทศญี่ปุ่น

 ชูริเต้ มวยแห่งเมืองชูริ (Shuri-te 首里手) 

โซคอน มัทสุมูระ (Sokon Matsumura) ผู้เชี่ยวชาญแห่งชูริเต้ ได้เดินทางไปศึกษาศิลปะการต่อสู้ที่จีนแผ่นดินใหญ่ และนำทักษะจากมวยสิงอี้ฉวนกลับมาประยุกต์ใช้ในการพัฒนาชูริเต้ในโอะกินะวะ

ต่อมา โชกิ โมโตบุ (Shoki Motobu) อีกหนึ่งผู้เชี่ยวชาญในสำนักชูริเต้ ได้มีโอกาสแลกเปลี่ยนวิชากับ T'ung Gee Hsing (ถง จี๋ซิง) ผู้สืบทอดมวยสิงอี้และปากั้ว ซึ่งได้อพยพมาอาศัยอยู่ในโอะกินะวะ

ในปี ค.ศ. 1922 ฟูนาโกชิ กิชิน (Funakoshi Gichin) ลูกศิษย์ของ อังโก อิโตสึ (Anko Itosu) แห่งสำนักชูริเต้ ได้เดินทางไปเผยแพร่คาราเต้ที่โตเกียว โดยได้รับการสนับสนุนจาก จิกาโร่ คาโนะ (Jigoro Kano) ผู้ก่อตั้งยูโดสายโคโดกัน (Kodokan Judo) ต่อมา บรรดาศิษย์ของฟูนาโกชิได้ตั้งชื่อรูปแบบการฝึกของเขาว่า โชโต (Shoto 松涛) ตามนามปากกาของฟูนาโกชิ และตั้งชื่อโดโจของเขาว่า โชโตกัน (Shotokan 松涛館) ซึ่งกลายเป็นหนึ่งในสายคาราเต้ที่แพร่หลายไปทั่วโลก

 ประวัติ 
ในปี พ.ศ. 2521 โกสรชุ (Sambasiva Rao Kosaraju) ศาสตราจารย์สาขาวิทยาการคอมพิวเตอร์แห่งมหาวิทยาลัยจอนส์ฮอปกินส์ ชาวอินเดีย ได้เขียนเอกสารวิจัย เรื่องขั้นตอนวิธีการคำนวณหาส่วนประกอบที่เชื่อมกันแบบเข้มของกราฟระบุทิศทางอย่างมีประสิทธิภาพ ขั้นตอนวิธีนี้ภายหลังได้ถูกเรียกว่า ขั้นตอนวิธีของโกสรชุ-ชารีร์ แต่เอกสารวิจัยดังกล่าวไม่ได้ถูกตีพิมพ์ ต่อมาขั้นตอนวิธีนี้ถูกเผยแพร่โดยอัลเฟร็ด อาโฮ (Alfred Aho) จอห์น ฮอปครอฟ (John Hopcroft) และเจฟเฟรย์ อัลแมน (Jeffrey Ullman)

 ขั้นตอนวิธี 
อัลกอรึทึมของโกสรชุ-ชารีร์ นั้นมีหลักการดังนี้
 ให้ G เป็นกราฟระบุทิศทาง (directed graph) และ S แทนกองซ้อน (stack) ที่ว่างเปล่า
 While S ยังไม่ได้เก็บจุดยอดทุกจุด
 เลือกจุดยอด v ที่ไม่อยู่ใน S แล้วทำ Depth-first search โดยเริ่มต้นที่ v จากนั้นทุกครั้งที่ Depth-first search เข้าไปถึงปม u จนเสร็จ ก็ให้ push u เข้าไปใน S
 กลับทิศของทุกเส้นเชื่อมเพื่อจะได้ transpose ของกราฟ
 While S ไม่ว่าง
 Pop จุดยอด v ออกมาจากกองซ้อน S แล้วทำ Depth-first search โดยเริ่มต้นที่ v จะพบว่าเซตของจุดยอดที่เข้าถึงได้จาก v จะเป็นส่วนประกอบที่เชื่อมกันแบบเข้มที่มี v อยู่ภายใน ดังนั้นก็จำจุดยอดเหล่านี้ไว้ และลบจุดยอดเหล่านี้ออกจากกราฟ G และกองซ้อน S
 หากใช้ Breadth-first search (BFS) แทน Depth-first search ก็ได้ผลอย่างเดียวกัน

 ประสิทธิภาพการทำงาน 
หากกราฟถูกเก็บข้อมูลในรูปแบบ adjacency list เมื่อใช้อัลกอรึทึมของโกสรชุ-ชารีร์ จะเกิดการเดินทางเข้าไปในกราฟ 2 ครั้ง และการ reverse กราฟอีก 1 ครั้ง แต่เนื่องจากเราใช้ adjacency list เก็บข้อมูล เราจะสามารถสร้างกราฟ reverse ได้ขณะที่เดินทางเข้าไปในกราฟครั้งแรก ทำให้แท้จริงแล้วการเวลาการทำงานจะคำนวณจากการเดินทางเข้าไปในกราฟ 2 ครั้งเท่านั้น จึงพบว่าประสิทธิภาพของขั้นตอนวิธีนี้เท่ากับ Θ(V+E) (เส้นตรง) เมื่อ V แทนจำนวนจุดยอด และ E แทนจำนวนเส้นเชื่อม ซึ่งถือว่าประสิทธิภาพเป็น asymptotically optimal เพราะเวลาการทำงานนั้นตรงกับขอบเขตล่าง (lower bound) เพราะทุกๆ ขั้นตอนวิธีจะต้องตรวจสอบทุกจุดยอดกับเส้นเชื่อม ดังนั้นตามหลักการแล้วขั้นตอนวิธีนี้เป็นขั้นตอนวิธีที่ง่ายและมีประสิทธิภาพ แต่ในทางปฏิบัติจะมีประสิทธิภาพต่ำกว่าขั้นตอนวิธีของ Tarjan หรือขั้นตอนวิธีของ Gabow ที่สามารถหาส่วนประกอบที่เชื่อมกันแบบเข้มได้โดยเดินทางเข้าไปในกราฟเพียงแค่รอบเดียว

ถ้ากราฟถูกเก็บข้อมูลในรูปแบบ adjacency matrix ขั้นตอนวิธีจะใช้เวลาทำงาน O(V2)

 การพิสูจน์ขั้นตอนวิธีของโกสรชุ 
พิสูจน์ว่าขั้นตอนวิธีของโกสรชุนั้นใช้ได้จริง โดยพิสูจน์ว่าจุดยอด 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 ก็จะอยู่ในส่วนประกอบที่เชื่อมกันแบบเข้มเดียวกันด้วย