[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]
Program BFT;
(*****************************************************************************)
(* Name: BFT *)
(* Written by: William Hobday *)
(* Last modified: March 5, 1989 *)
(* *)
(* Purpose: Implements the Bredth First traversal algorithm using the *)
(* Graph, Tree, and Q units. The following program produces BFT *)
(* traversals of the following graphs starting from node C: *)
(* *)
(* Graph 1 Graph 2 *)
(* *)
(* A - B - C - D A - B C *)
(* \ / \ / \ / *)
(* E - F - G *)
(* \ / \ / *)
(* H - I *)
(* \ / *)
(* J *)
(* *)
(* In case the adjacency graph as well as the corresponding *)
(* spanning tree is printed. *)
(* *)
(*****************************************************************************)
uses graph,Q,tree,crt; { graph is in math.swg
q is in pointers.swg !! }
var A,B,C,D,E,F,G,H,I,J,K,L,M : Vertex;
Grph1,Grph2: Vertex;
(*****************************************************************************)
(* Name: Visit *)
(* *)
(* Purpose: Visits node by adding vertex to tree and placing it in the Q *)
(* then marking the node as visited. *)
(* Input: Grph - The graph *)
(* VertexQ - the queue *)
(* Father - the tree node to be added to *)
(* Name - name of the vertex to visit *)
(* Output: the modifed graph and queue *)
(*****************************************************************************)
Procedure Visit( Grph : Vertex; var VertexQ : Queue; Father : TreeNode; Name: char );
begin
AddTreeNode( Father,Name );
GetVertex( Grph,Name )^.visited := true;
EnQueue( VertexQ,Name );
end;
(*****************************************************************************)
(* Name: SelectFatherNode *)
(* *)
(* Purpose: Given a father node it test to see if it the valid one for *)
(* when inserting into the tree. *)
(* Input: Father - node to check *)
(* Output: pointer to selected node *)
(*****************************************************************************)
Function SelectFatherNode( Father : TreeNode ) : TreeNode;
begin
if Father^.Son = nil
then begin
Father := Father^.Parent;
if Father^.brother = nil
then SelectFatherNode := Firstchild( father )
else SelectFatherNode := NextSibling( father )
end
else SelectFatherNode := FirstChild( father )
end;
(*****************************************************************************)
(* Name: SelectGraphNode *)
(* *)
(* Purpose: Given the graph it selects the next Node that has not been *)
(* visited. *)
(* Input: Grph - pointer to start of graph *)
(* Output: pointer to selected node *)
(*****************************************************************************)
Function SelectGraphNode( Grph : Vertex ) : Vertex;
begin
While (Grph^.visited = True) and (Grph <> nil) do
Grph := Grph^.Next;
SelectGraphNode := Grph
end;
(*****************************************************************************)
(* Name: BFTraverse *)
(* *)
(* Purpose: Given a graph and starting vertex this procedure produces a *)
(* spanning tree of the Breadth First Traversal of the graph. *)
(* Input: Grph - the start of the graph *)
(* V - the vertex to start traversal at *)
(* Output: The spanning tree produce by the BFT *)
(*****************************************************************************)
Procedure BFTraverse( Grph : Vertex; V : Vertex);
var Name,Name2 : char;
VertexQ: Queue;
BFTree,Father : TreeNode;
begin
NewQueue( VertexQ );
while V <> nil do
begin
BFTree := NewTree( V^.Name );
Father := BFTree;
V^.Visited := true;
EnQueue( VertexQ,V^.Name );
while not empty( VertexQ ) do
begin
Name := DeQueue( vertexQ );
Name2 := FirstSuccessor( Grph,Name );
while Name2 <> #0 do
begin
if not GetVertex( Grph,Name2 )^.visited
then Visit( Grph,VertexQ,Father,Name2 );
Name2 := NextSuccessor( Grph,Name,Name2 );
end;
Father := SelectFatherNode( Father )
end;
writeln('BFT Spanning Tree');
writeln('ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ');
PrintTree( BFTree );
writeln('ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ');
writeln;
V := SelectGraphNode( Grph )
end
end;
begin
Grph1 := NewGraph; (* Initialize graphs *)
Grph2 := NewGraph;
A := NewVrtx(Grph1,'A'); (* Add Vertices *)
B := NewVrtx(Grph1,'B');
C := NewVrtx(Grph1,'C');
D := NewVrtx(Grph1,'D');
E := NewVrtx(Grph1,'E');
F := NewVrtx(Grph1,'F');
G := NewVrtx(Grph1,'G');
H := NewVrtx(Grph1,'H');
I := NewVrtx(Grph1,'I');
J := NewVrtx(Grph1,'J');
K := NewVrtx(Grph2,'A');
L := NewVrtx(Grph2,'B');
M := NewVrtx(Grph2,'C');
WtdJoin(A,B,1); (* Join vertices *)
WtdJoin(A,E,4);
WtdJoin(B,A,1);
WtdJoin(B,C,2);
WtdJoin(B,F,4);
WtdJoin(B,E,7);
WtdJoin(C,B,2);
WtdJoin(C,D,3);
WtdJoin(C,G,5);
WtdJoin(C,F,1);
WtdJoin(D,C,3);
WtdJoin(D,G,4);
WtdJoin(E,F,2);
WtdJoin(E,A,4);
WtdJoin(E,H,3);
WtdJoin(E,B,7);
WtdJoin(F,E,2);
WtdJoin(F,G,3);
WtdJoin(F,B,4);
WtdJoin(F,I,1);
WtdJoin(F,C,1);
WtdJoin(F,H,3);
WtdJoin(G,F,3);
WtdJoin(G,C,5);
WtdJoin(G,D,4);
WtdJoin(G,I,5);
WtdJoin(H,I,5);
WtdJoin(H,E,3);
WtdJoin(H,J,2);
WtdJoin(H,F,3);
WtdJoin(I,H,5);
WtdJoin(I,F,1);
WtdJoin(I,G,5);
WtdJoin(I,J,6);
WtdJoin(J,H,2);
WtdJoin(J,I,6);
WtdJoin(K,L,1);
WtdJoin(L,K,1);
ClrScr; (* display graph 1 *)
writeln(' Graph 1');
BFTraverse( Grph1,c );
Window(40,2,80,25);
writeln('Adjacency Matrix');
writeln('ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ');
writeln;
PrintGraph( Grph1 );
delay(5000);
Window(1,1,80,25); (* display graph 2 *)
ClrScr;
writeln(' Graph 2');
BFTraverse( Grph2,k );
Window(40,2,80,25);
writeln('Adjacency Matrix');
writeln('ÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ');
writeln;
PrintGraph( Grph2 )
end.
[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]