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

รหัสเทียมแสดงการทำงานส่วนที่ 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    }