ขั้นตอนวิธีของทาร์จัน

ขั้นตอนวิธีของทาร์จัน (อังกฤษ: Tarjan's algorithm) คือขั้นตอนวิธีสำหรับการหา strongly connected components แต่ละ component บน directed graph ซึ่งถูกคิดค้นโดย โรเบิร์ด ทาร์จัน(Robert Tarjan)

connected graph คือ กราฟที่มีวิถีระหว่าง vertex ใดๆไปยังทุกๆ vertex ภายในกราฟ

strongly connected graph คือ directed graph ที่มีวิถีระหว่าง vertex ใดๆไปยังทุกๆ vertex ภายในกราฟ

strongly connected component คือ strongly connected graph ที่เป็นกราฟย่อยของกราฟใหญ่

แนวคิด

แนวคิดของขั้นตอนวิธีของทาร์จันจะเริ่มจาก vertex เริ่มต้น(v0) ซึ่งเป็น vertex เริ่มต้น ซึ่งสามารถเป็น vertex ใดๆก็ได้ภายในกราฟ จากนั้นจะเข้าถึง (traverse) แต่ละ vertex โดยใช้วิธีการ Depth-first search (DFS) เข้าสู่ adjacent vertex ต่อไป โดยจะไม่มีการ traverse vertex ซ้ำ, ตัวอย่างเช่น หาก vertex v1 ถูก traverse ไปแล้ว จะไม่มีการ traverse v1 ซ้ำอีกครั้ง , โดยการหา strongly connected components จะหาจากการระบุ vertex แรกที่พบจากการ Depth-first search ของแต่ละ strongly connected component โดยจะเรียก vertex ดังกล่าวว่า "root" (เนื่องจากการใช้ Depth-first search จะเป็นการเข้าถึงต้นไม้ย่อย (subtree) แต่ละต้นภายในกราฟ ดังนั้น vertex แรกที่อยู่ใน strongly connected component ที่พบจากการ Depth-first search จึงเป็น vertex ที่บอกว่า vertex ต่อไปอยู่ใน strongly connected component ด้วย จึงเรียก vertex ดังกล่าวว่า "root") แต่ปัญหาของ Tarjan's algorithm คือจะรู้ได้อย่างไรว่า vertex ใดเป็น root ของแต่ละ strongly connected component บ้าง จึงมีการใช้กองซ้อน (stack) และปม (Node) ในการช่วยแก้ไขปัญหาดังกล่าว

• การสร้างปม ซึ่งแต่ละปม จะแทนแต่ละ vertex โดยภายในปม จะเก็บข้อมูล 2 ตัว คือ

(int) index : เก็บหมายเลข vertex ซึ่งเป็นหมายเลขตัวแทน vertex แต่ละ vertex

(int) lowlink : เก็บหมายเลข vertex (index) ของ vertex ที่เป็น root ของ vertex นี้

• การใช้ stack จะมีการแบ่ง vertex ทั้งหมดของกราฟ ออกเป็น 2 ส่วน คือ

1. vertex ที่อยู่ใน stack : stack จะเก็บ vertex ต่างๆที่กำลังถูก traverse (เข้าถึง) ในขณะนี้

2. vertex ที่อยู่นอก stack : เป็น vertex ที่ถูก traverse เสร็จเรียบร้อยแล้ว หรือยังไม่ถูก traverse เลย

การทำงานขั้นตอนวิธีของทาร์จัน จะใช้วิธี Depth-first search แต่ละ vertex ไปยัง adjacent vertices ที่ยังไม่ถูก traverse ในรูปแบบของการ recursive โดยมีเงื่อนไขว่า [ให้ v คือ vertex ปัจจุบัน และ v' คือ adjacent vertex ของ v]

1. หากพบว่า adjacent vertex คือ vertex ที่ยังไม่ถูก traverse : ให้ traverse adjacent vertex นั้นก่อน จากนั้น set ค่า lowlink ของ vertex ปัจจุบันเป็นค่าที่น้อยกว่าระหว่างค่า lowlink ของ v กับค่า lowlink ของ v'

2. หากพบว่า adjacent vertex คือ vertex ที่กำลังถูก traverse หรืออยู่ภายใน stack : จะแสดงว่ามี cycle ภายในกราฟ ซึ่งทำให้เกิด strongly connected component , ให้ vertex ปัจจุบันมีค่า lowlink ของ vertex ปัจจุบันเป็นค่าที่น้อยกว่าระหว่างค่า lowlink ของ v กับค่า index ของ v'

รหัสเทียมแสดงการทำงานส่วนที่ 1

 1 for all (v' is adjacent to v) do // ทุก v' ที่เป็น adjacent vertex ของ v 2 if (v' is not traversed)  // v' ยังไม่ถูก traverse 3 tarjan(v')  // traverse v' 4 v.lowlink = min(v.lowlink, v'.lowlink) 5 elseif (v' in Stack)  // v' กำลังถูก traverse (ยังคงถูกเก็บอยู่ใน stack) 6 v.lowlink = min(v.lowlink, v'.index) 

เมื่อเสร็จสิ้นการทำงานดังกล่าวจะพบว่า หากมี strongly connected component ค่า lowlink จะมีค่าเป็นหมายเลขของ root vertex ของ strongly connected component นั้น ดังนั้นหาก vertex ใดมีค่า lowlink จะมีค่าเท่ากับหมายเลขของ vertex นั้น แสดงว่า vertex นั้นเป็น root ของ strongly connected component นั้น จึงทำการ pop vertex ใน stack ออกมาเพื่อแสดงผล (print) ว่ามี vertex ใดภายใน strongly connected component นี้บ้าง ซึ่งจะ pop ค่าออกมาจนกระทั่งพบ vertex ตนเอง จึงหยุด pop ค่าออกจาก stack

รหัสเทียมแสดงการทำงานส่วนที่ 2

 1 if (v.lowlink == v.index) // v เป็น SCC หรือไม่ 2 print "SCC : " 3 repeat 4 v' = stack.pop // ให้ v' เป็น vertex ที่ถูก pop ออกมาจาก stack 5 print v' // แสดงหมายเลข vertex v' ทางจอภาพ 6 until (v' == v) // หาก vertex ที่ถูก pop ออกมาเป็น vertex ตนเอง ให้หยุด pop 

ตัวอย่าง

• การอธิบายแนวคิดนี้ จะใช้สัญลักษณ์สีเพื่อประกอบความเข้าใจ ได้แก่

vertex สีขาว : แทน vertex ที่ยังไม่ถูก traverse

vertex สีเทา : แทน vertex ที่ยังกำลังถูก traverse ในขณะนี้ (อยู่ใน stack)

vertex สีดำ : แทน vertex ที่ยังถูก traverse เสร็จเรียบร้อยแล้ว

1.มีกราฟ G ที่มีทั้งหมด 7 vertices (v0 - v6)

 

2.เริ่มทำการ Depth-first search จาก v0 โดยเริ่มต้น index และ lowlonk ของแต่ละ vertex จะมีค่าเท่ากับหมายเลข vertex ของตนเอง ซึ่ง v0 จะมีค่า index และ lowlink เท่ากับ 0 จะเห็นว่าขณะนี้มีการ traverse v0 จึงให้ v0 เป็นสีเทา (push ลง stack)

 

3.ทำการ Depth-first search ไปยัง adjacent vertex ของ v0 นั่นคือ v1 และ v3 ตามลำดับ เริ่มจาก traverse v1 และ set ค่า ให้กับ index และ lowlink ให้เท่ากับหมายเลข vertex ของตนเอง

 

4.จากนั้น Depth-first search ไปยัง adjacent vertex ของ v1 นั่นคือ v2 เริ่มจาก traverse v2 และ set ค่า ให้กับ index และ lowlink ให้เท่ากับหมายเลข vertex ของตนเอง

 

5.จากนั้น Depth-first search ไปยัง adjacent vertex ของ v2 นั่นคือ v1 ซึ่งเป็น vertex ที่กำลังถูก traverse จึงเปรียบเทียบค่าน้อยกว่าระหว่างค่า lowlink ของ v2 กับค่า index ของ v1 ให้เป็นค่า lowlink ของ v2

 

6.v2 ไม่มี adjacent vertex อื่น จึงตรวจสอบว่า index กับ lowlink ของ v2 มีค่าเท่ากันหรือไม่ แน่นอนว่าไม่เท่ากัน การ Depth-first search จึงกลับไปที่ v1 และตรวจสอบในทำนองเดียวกัน พบว่า index กับ lowlink ของ v1 มีค่าเท่ากัน จึง pop vertex บนสุดออกมาจาก stack คือ v2 (กลายเป็นสีดำ) นำ v2 แสดงออกบนหน้าจอ (SCC : v2)

 

7.pop vertex ออกจาก stack จนกระทั่งพบว่า vertex ที่ pop ออกมาคือ vertex ปัจจุบัน (v1) จากนั้นหยุดการ pop (SCC : v2 , v1)

 

8.กลับมาพิจารณาการ Depth-first search adjacent vertex ถัดไปของ v0 คือ v3

 

9.ในทำนองเดียวกับ v0 , v3 จะทำการ Depth-first search ตามแต่ละ adjacent vertex คือ v4 และ v5 ตามลำดับ

 

10.v4 จะทำการ Depth-first search ตามแต่ละ adjacent vertex คือ v5 และ v6 ตามลำดับ

 

11.v5 จะทำการ Depth-first search ไปยัง v0 ซึ่งเป็น vertex ที่กำลังถูก traverse หรืออยู่ใน stack ขณะนี้ จึงทำการเปรียบเทียบค่าน้อยกว่าระหว่างค่า lowlink ของ v5 กับค่า index ของ v0 ให้เป็นค่า lowlink ของ v5

 

12.v5 ไม่มี adjacent vertex อื่น จึงกลับมาพิจารณา v4 และกำหนดค่า lowlink ของ v4 เป็นค่าที่น้อยกว่าระหว่างค่า lowlink ของ v4 กับค่า lowlink ของ v5

 

13.จากนั้น Depth-first search adjacent vertex ของ v4 ถัดไปคือ v6

 

14.v6 ไม่มี adjacent vertex ใดเลย และพบว่า index กับ lowlink ของ v6 มีค่าเท่ากัน จึง pop vertex บนสุดออกมาจาก stack และพบว่า vertex นั้นคือ v6 จึงแสดงผล strongly connected component ที่มีเพียง v6 เท่านั้นภายใน component นี้ (SCC : v6)

 

15.กลับมาพิจารณาที่ v4 พบว่าไม่พบ adjacent vertex อื่น จึงกลับไปพิจารณาที่ v3 โดย v3 จะเปรียบเทียบนำค่าที่น้อยกว่าระหว่างค่า lowlink ของ v3 กับค่า lowlink ของ v4 และนำมาใส่ในค่า lowlink ของ v3

 

16.v3 ที่มี adjacent vertex อื่นอีกคือ v5 แต่ v5 ที่ถูก traverse ไปแล้วจึงไม่ traverse v5 อีกครั้ง และกลับไปพิจารณาที่ v0 (ไม่มี adjacent vertex อื่นแล้ว) ซึ่งพบว่า index กับ lowlink ของ v0 มีค่าเท่ากัน จึง pop vertex ออกจาก stack จนกว่าจะเจอ vertex ตนเอง พร้อม print ค่า vertex ต่างๆออกมาแสดงเป็น strongly connected component อีกส่วนหนึ่ง (SSC : v5 , v4 , v3 , v0)

 

 

 

 

รหัสเทียมแสดงการทำงานทั้งหมด

 1 Input: Graph G = (V, E), Start node v0 2 index = 0   // DFS node number counter 3 S = empty   // An empty stack of nodes 4 tarjan(v0)  // Start a DFS at the start node 5 6 procedure tarjan(v) 7 v.index = index  // Set the depth index for v 8 v.lowlink = index 9 index = index + 1 10 S.push(v)  // Push v on the stack 11 forall (v, v') in E do // Consider successors of v 12 if (v'.index is undefined) // Was successor v' visited? 13  tarjan(v')  // Recurse 14  v.lowlink = min(v.lowlink, v'.lowlink) 15 elseif (v' in S) // Is v' on the stack? 16  v.lowlink = min(v.lowlink, v'.index) 17 if (v.lowlink == v.index) // Is v the root of an SCC? 18 print "SCC:" 19 repeat 20  v' = S.pop 21  print v' 22 until (v' == v) 

รหัสแสดงการทำงานของภาษาจาวา

 1 import java.util.ArrayList; 2 public class Tarjan { 3 private int index = 0; 4 private ArrayList<Node> stack = new ArrayList<Node>(); 5 private ArrayList<ArrayList<Node>> SCC = new ArrayList<ArrayList<Node>>(); 6 7 public ArrayList<ArrayList<Node>> executeTarjan(AdjacencyList graph){ 8  SCC.clear(); 9  index = 0; 10  stack.clear(); 11  if(graph != null){ 12  List<Node> nodeList = new ArrayList<Node>(graph.getSourceNodeSet()); 13  if(nodeList != null){ 14  for (Node node : nodeList){ 15   if(node.index == -1){ 16   tarjan(node, graph); 17   } 18  } 19  } 20  } 21  return SCC; 22 } 23 24 private ArrayList<ArrayList<Node>> tarjan(Node v, AdjacencyList list){ 25  v.index = index; 26  v.lowlink = index; 27  index++; 28  stack.add(0, v); 29  for(Edge e : list.getAdjacent(v)){ 30  Node n = e.to; 31  if(n.index == -1){ 32  tarjan(n, list); 33  v.lowlink = Math.min(v.lowlink, n.lowlink); 34  }else if(stack.contains(n)){ 35  v.lowlink = Math.min(v.lowlink, n.index); 36  } 37  } 38  if(v.lowlink == v.index){ 39  Node n; 40  ArrayList<Node> component = new ArrayList<Node>(); 41  do{ 42  n = stack.remove(0); 43  component.add(n); 44  }while(n != v); 45  SCC.add(component); 46  } 47  return SCC; 48 } 49 } 

อ้างอิง

1. I. S. Duff Computer Science and Systems Division, Building 8.9, AERE Harwell, Didcot, Oxfordshire, OX11 ORA, England