home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 13 / CDA13.ISO / cdactual / demobin / share / program / Pascal / BFTGPH.ZIP / BFT.PAS < prev    next >
Encoding:
Pascal/Delphi Source File  |  1991-09-09  |  8.6 KB  |  220 lines
  1. Program BFT;
  2.  
  3. (*****************************************************************************)
  4. (*   Name:  BFT                                                              *)
  5. (*   Written by: William Hobday                                              *)
  6. (*   Last modified: March 5, 1989                                            *)
  7. (*                                                                           *)
  8. (*   Purpose: Implements the Bredth First traversal algorithm using the      *)
  9. (*            Graph, Tree, and Q units.  The following program produces BFT  *)
  10. (*            traversals of the following graphs starting from node C:       *)
  11. (*                                                                           *)
  12. (*                    Graph 1                   Graph 2                      *)
  13. (*                                                                           *)
  14. (*                  A - B - C - D              A - B   C                     *)
  15. (*                   \ / \ / \ /                                             *)
  16. (*                    E - F - G                                              *)
  17. (*                     \ / \ /                                               *)
  18. (*                      H - I                                                *)
  19. (*                       \ /                                                 *)
  20. (*                        J                                                  *)
  21. (*                                                                           *)
  22. (*            In case the adjacency graph as well as the corresponding       *)
  23. (*            spanning tree is printed.                                      *)
  24. (*                                                                           *)
  25. (*****************************************************************************)
  26.  
  27. uses graph,Q,tree,crt;
  28.  
  29. var A,B,C,D,E,F,G,H,I,J,K,L,M : Vertex;
  30.     Grph1,Grph2: Vertex;
  31.  
  32.  
  33.  
  34. (*****************************************************************************)
  35. (*   Name: Visit                                                             *)
  36. (*                                                                           *)
  37. (*   Purpose: Visits node by adding vertex to tree and placing it in the Q   *)
  38. (*            then marking the node as visited.                              *)
  39. (*   Input: Grph - The graph                                                 *)
  40. (*          VertexQ - the queue                                              *)
  41. (*          Father - the tree node to be added to                            *)
  42. (*          Name - name of the vertex to visit                               *)
  43. (*   Output: the modifed graph and queue                                     *)
  44. (*****************************************************************************)
  45.  
  46. Procedure Visit( Grph : Vertex; var VertexQ : Queue; Father : TreeNode; Name: char );
  47.  
  48. begin
  49.    AddTreeNode( Father,Name );
  50.    GetVertex( Grph,Name )^.visited := true;
  51.    EnQueue( VertexQ,Name );
  52. end;
  53.  
  54.  
  55.  
  56. (*****************************************************************************)
  57. (*   Name: SelectFatherNode                                                  *)
  58. (*                                                                           *)
  59. (*   Purpose:  Given a father node it test to see if it the valid one for    *)
  60. (*             when inserting into the tree.                                 *)
  61. (*   Input: Father - node to check                                           *)
  62. (*   Output: pointer to selected node                                        *)
  63. (*****************************************************************************)
  64.  
  65. Function SelectFatherNode( Father : TreeNode ) : TreeNode;
  66.  
  67. begin
  68.    if Father^.Son = nil
  69.       then begin
  70.               Father := Father^.Parent;
  71.               if Father^.brother = nil
  72.                  then SelectFatherNode := Firstchild( father )
  73.                  else SelectFatherNode := NextSibling( father )
  74.            end
  75.       else SelectFatherNode := FirstChild( father )
  76. end;
  77.  
  78.  
  79.  
  80. (*****************************************************************************)
  81. (*   Name: SelectGraphNode                                                   *)
  82. (*                                                                           *)
  83. (*   Purpose: Given the graph it selects the next Node that has not been     *)
  84. (*            visited.                                                       *)
  85. (*   Input: Grph - pointer to start of graph                                 *)
  86. (*   Output: pointer to selected node                                        *)
  87. (*****************************************************************************)
  88.  
  89. Function SelectGraphNode( Grph : Vertex ) : Vertex;
  90.  
  91. begin
  92.    While (Grph^.visited = True) and (Grph <> nil) do
  93.       Grph := Grph^.Next;
  94.    SelectGraphNode := Grph
  95. end;
  96.  
  97.  
  98.  
  99. (*****************************************************************************)
  100. (*   Name: BFTraverse                                                        *)
  101. (*                                                                           *)
  102. (*   Purpose:  Given a graph and starting vertex this procedure produces a   *)
  103. (*             spanning tree of the Breadth First Traversal of the graph.    *)
  104. (*   Input: Grph - the start of the graph                                    *)
  105. (*          V - the vertex to start traversal at                             *)
  106. (*   Output: The spanning tree produce by the BFT                            *)
  107. (*****************************************************************************)
  108.  
  109. Procedure BFTraverse( Grph : Vertex; V : Vertex);
  110.  
  111. var Name,Name2 : char;
  112.     VertexQ: Queue;
  113.     BFTree,Father : TreeNode;
  114.  
  115. begin
  116.    NewQueue( VertexQ );
  117.    while V <> nil do
  118.          begin
  119.             BFTree := NewTree( V^.Name );
  120.             Father := BFTree;
  121.             V^.Visited := true;
  122.             EnQueue( VertexQ,V^.Name );
  123.             while not empty( VertexQ ) do
  124.                begin
  125.                   Name := DeQueue( vertexQ );
  126.                   Name2 := FirstSuccessor( Grph,Name );
  127.                   while Name2 <> #0 do
  128.                      begin
  129.                         if not GetVertex( Grph,Name2 )^.visited
  130.                            then Visit( Grph,VertexQ,Father,Name2 );
  131.                         Name2 := NextSuccessor( Grph,Name,Name2 );
  132.                      end;
  133.                   Father := SelectFatherNode( Father )
  134.                end;
  135.             writeln('BFT Spanning Tree');
  136.             writeln('─────────────────');
  137.             PrintTree( BFTree );
  138.             writeln('─────────────────');
  139.             writeln;
  140.             V := SelectGraphNode( Grph )
  141.       end
  142. end;
  143.  
  144.  
  145.  
  146.  
  147. begin
  148.    Grph1 := NewGraph;                                (* Initialize graphs *)
  149.    Grph2 := NewGraph;
  150.    A := NewVrtx(Grph1,'A');                          (* Add Vertices *)
  151.    B := NewVrtx(Grph1,'B');
  152.    C := NewVrtx(Grph1,'C');
  153.    D := NewVrtx(Grph1,'D');
  154.    E := NewVrtx(Grph1,'E');
  155.    F := NewVrtx(Grph1,'F');
  156.    G := NewVrtx(Grph1,'G');
  157.    H := NewVrtx(Grph1,'H');
  158.    I := NewVrtx(Grph1,'I');
  159.    J := NewVrtx(Grph1,'J');
  160.    K := NewVrtx(Grph2,'A');
  161.    L := NewVrtx(Grph2,'B');
  162.    M := NewVrtx(Grph2,'C');
  163.    WtdJoin(A,B,1);                                   (* Join vertices *)
  164.    WtdJoin(A,E,4);
  165.    WtdJoin(B,A,1);
  166.    WtdJoin(B,C,2);
  167.    WtdJoin(B,F,4);
  168.    WtdJoin(B,E,7);
  169.    WtdJoin(C,B,2);
  170.    WtdJoin(C,D,3);
  171.    WtdJoin(C,G,5);
  172.    WtdJoin(C,F,1);
  173.    WtdJoin(D,C,3);
  174.    WtdJoin(D,G,4);
  175.    WtdJoin(E,F,2);
  176.    WtdJoin(E,A,4);
  177.    WtdJoin(E,H,3);
  178.    WtdJoin(E,B,7);
  179.    WtdJoin(F,E,2);
  180.    WtdJoin(F,G,3);
  181.    WtdJoin(F,B,4);
  182.    WtdJoin(F,I,1);
  183.    WtdJoin(F,C,1);
  184.    WtdJoin(F,H,3);
  185.    WtdJoin(G,F,3);
  186.    WtdJoin(G,C,5);
  187.    WtdJoin(G,D,4);
  188.    WtdJoin(G,I,5);
  189.    WtdJoin(H,I,5);
  190.    WtdJoin(H,E,3);
  191.    WtdJoin(H,J,2);
  192.    WtdJoin(H,F,3);
  193.    WtdJoin(I,H,5);
  194.    WtdJoin(I,F,1);
  195.    WtdJoin(I,G,5);
  196.    WtdJoin(I,J,6);
  197.    WtdJoin(J,H,2);
  198.    WtdJoin(J,I,6);
  199.    WtdJoin(K,L,1);
  200.    WtdJoin(L,K,1);
  201.    ClrScr;                                           (* display graph 1 *)
  202.    writeln('                         Graph 1');
  203.    BFTraverse( Grph1,c );
  204.    Window(40,2,80,25);
  205.    writeln('Adjacency Matrix');
  206.    writeln('────────────────');
  207.    writeln;
  208.    PrintGraph( Grph1 );
  209.    delay(5000);
  210.    Window(1,1,80,25);                                (* display graph 2 *)
  211.    ClrScr;
  212.    writeln('                         Graph 2');
  213.    BFTraverse( Grph2,k );
  214.    Window(40,2,80,25);
  215.    writeln('Adjacency Matrix');
  216.    writeln('────────────────');
  217.    writeln;
  218.    PrintGraph( Grph2 )
  219. end.
  220.