Thuật toán của Tarjan cho các thành phần được kết nối mạnh mẽ

Thuật toán Tarjan được sử dụng để tìm các thành phần được kết nối chặt chẽ của một biểu đồ có hướng. Nó chỉ yêu cầu một truyền tải DFS để triển khai thuật toán này.

Sử dụng DFS traversal, chúng ta có thể tìm thấy cây DFS của khu rừng. Từ cây DFS, các thành phần được kết nối mạnh mẽ được tìm thấy. Khi tìm thấy gốc của cây con như vậy, chúng ta có thể hiển thị toàn bộ cây con. Cây con đó là một thành phần được kết nối mạnh mẽ.

Đầu vào và Đầu ra

 Đầu vào:Ma trận kề của đồ thị. 0 1 1 01 0 0 0 00 1 0 0 00 0 0 0 10 0 0 0 0 Đầu vào:Các thành phần được kết nối mạnh mẽ:431 2 0 

Thuật toán

findComponent (u, disk, low, stack, stackItemFlag)

Đầu vào: Nút bắt đầu, thời gian khám phá, mức thấp, đĩa sẽ giữ thời gian khám phá của đỉnh và nút thấp sẽ chứa thông tin về các cây con. Ngăn xếp để giữ các đỉnh và một mảng cờ khác để theo dõi nút nào nằm trong ngăn xếp.

Đầu ra: Hiển thị SCC.

 Begin time:=0 // giá trị của thời gian sẽ không được khởi tạo cho các lệnh gọi hàm tiếp theo set disk [u]:=time + 1 và low [u]:=time + 1 time:=time + 1 push u thành ngăn xếp stackItemFalg [u]:=true cho tất cả đỉnh v liền kề với u, nếu v không được phát hiện, thì fincComponent (v, đĩa, thấp, ngăn xếp, ngăn xếpItemFalg) low [u] =tối thiểu của thấp [u] và low [v] else nếu stackItemFalg [v] là true, thì low [u]:=low of low [u] và disk [v] done poppedItem:=0 nếu low [u] =disk [u], sau đó u không ở trên cùng ngăn xếp, do poppedItem:=đầu của ngăn xếp hiển thị poppedItem stackItemFlag [poppedItem]:=false pop item from stack done poppedItem:=top of stack display poppedItem stackItemFlag [poppedItem]:=false pop item from stackEnd  

  strongConComponent (biểu đồ)  
 

  Đầu vào &, dấu trừ;  Biểu đồ đã cho. 
 

  Đầu ra -  Tất cả các thành phần được kết nối mạnh mẽ. 
 
 Begin ban đầu đặt tất cả các mục trong mảng đĩa thành chưa được khám phá cho tất cả các phần tử có giá trị thấp đến φ và đánh dấu không có mục nào được lưu trữ vào ngăn xếp cho tất cả nút i trong biểu đồ, nếu đĩa [i] chưa được phát hiện, thì findComponent ( i, disk, low, stack, stackItemFlag) Kết thúc 
 
 Ví dụ 
 
 #include  #include  #define NODE 5 using namespace std; int graph [NODE] [NODE] ={{0, 0, 1, 1, 0}, {1, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0 , 0, 0, 1}, {0, 0, 0, 0, 0}}; int min (int a, int b) {return (a  &stk, bool stkItem []) { static int time =0; đĩa [u] =low [u] =++ thời gian; // thời gian phát hiện sớm nhất và giá trị thấp là 1 stk.push (u); stkItem [u] =true; // gắn cờ là u trong ngăn xếp for (int v =0; v  stk; for (int i =0; i  
 Đầu ra 
 
 431 2 0