youxiangtu.txt

这是强连通图的一个经典算法

{
求有向图的强连通分支，用邻接表实现图
                By starfish
           [e-mail]

运行实例如下（图的输入格式为 u ,v ,边权）：
Please input nodes count:8
Please input sides count:14
Please input Graph:
1 2 1
2 3 1
3 4 1
4 3 1
2 6 1
5 6 1
2 5 1
5 1 1
6 7 1
7 6 1
3 7 1
7 8 1
8 8 1
4 8 1
The strongly connected componets of the graph are:
1 5 2
3 4
6 7
8
}

program Strongly_Connected_Components;
const
MaxNodeCount=50;  {图的最大节点数目}

type
PNode=^TNode;
TNode=record
        vertex:integer;    {相邻顶点标号}
        SideInfo:integer;  {边的信息}
        next:PNode;        {下一个相邻顶点} 
      end;
TGraph=record  {用邻接表定义图}
         size:integer;  {图的结点个数}
         adjList:array [1..MaxNodeCount] of PNode;            
       end;  

var
G:TGraph;

procedure AddSide(var G:TGraph;u,v,w:integer);   {增加一条边}
var
p:PNode;
begin
new(p);
p^.vertex:=v;
p^.SideInfo:=w;
p^.next:=G.adjList[u];
G.adjList[u]:=p;
end;

procedure CreateGraph(var G:TGraph);
var
i,m,u,v,w:integer;
begin
write('Please input the node count:');readln(G.size);
if G.size>MaxNodeCount then 
 begin
  writeln('Error! Node count must <= ',MaxNodeCount,' !');
  halt;
 end;
for i:=1 to G.size do  {初始化图G}
  G.adjList[i]:=nil;
write('Please input sides count:');readln(m); {读入边的数目}
writeln('Please input Graph:');
for i:=1 to m do     {用邻接表方式读入图}
 begin
   readln(u,v,w);
   AddSide(G,u,v,w);   {增加一条边}
 end;   
end;


procedure transposition(Var G1,G2:TGraph); {求G1的转置矩阵放在G2中，复杂度为O(V+E)}
var
i:integer;
p,q:PNode;
begin
G2.size:=G1.size;
for i:=1 to G2.size do
 G2.adjList[i]:=nil;
for i:=1 to G1.size do
 begin
  p:=G1.adjList[i];
  while p<>nil do        {这个while循环对图G1进行转置}
   begin
    new(q);
    q^.vertex:=i;
    q^.SideInfo:=p^.SideInfo;
    q^.next:=G2.adjList[p^.vertex];
    G2.adjList[p^.vertex]:=q;
    p:=p^.next;   
   end; 
 end; 
end;


procedure Strongly_Connect(var G1:TGraph); {求有向图的强连通分支}
var
G2:TGraph;
visited:array[1..MaxNodeCount] of boolean;
ft:array [1..MaxNodeCount] of integer; {ft[i]记录在时刻i完成的节点标号}
time,i:integer;

procedure DFS_Search_1(var G:TGraph;v:integer);
var
p:PNode;
begin
visited[v]:=true;
p:=G.adjList[v];
while p<>nil do
 begin
  if (not visited[p^.vertex]) then DFS_Search_1(G,p^.vertex);
  p:=p^.next;
 end;
inc(time); 
ft[time]:=v; 
end;

procedure DFS_Search_2(var G:TGraph;v:integer);
var
p:PNode;
begin
visited[v]:=true;
write(v,' '); {打印当前访问的节点}
p:=G.adjList[v];
while p<>nil do
 begin
  if (not visited[p^.vertex]) then DFS_Search_2(G,p^.vertex);
  p:=p^.next; 
 end;
end;


begin
for i:=1 to G1.size do visited[i]:=false;
time:=0;
for i:=1 to G1.size do
 if not visited[i] then
    DFS_Search_1(G1,i);   {深度优先遍历G1，并且记录每个节点的完成时刻}
    
transposition(G1,G2);  {求G1的转置图G2}

for i:=1 to G2.size do visited[i]:=false;  

writeln('The strongly connected componets of the graph are:');

for i:=G2.size downto 1 do      {按照深度优先遍历G1时每个节点的完成时刻递减顺序}
 if not visited[ ft[i] ] then
  begin
   DFS_Search_2(G2,ft[i]);
   writeln; 
  end;  
end;



begin
CreateGraph(G);
Strongly_Connect(G);
end.