rybufc

BFW and DFW

Feb 4th, 2018
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 1.95 KB | None | 0 0
  1. ?uses System.Collections.Generic;
  2.  
  3. const
  4.   MaxN = 1000;
  5.  
  6. function BFS(startPoint: integer;
  7.               targetPoint: integer;
  8.               params graph: Array[,] of integer): boolean;
  9. begin
  10.   var queue: Queue<integer>;
  11.   queue := new Queue<integer>;
  12.  
  13.   var isFound: boolean;
  14.   isFound := false;
  15.  
  16.   var visited: Array[0..MaxN] of boolean;  
  17.   queue.Enqueue(startPoint);
  18.  
  19.   while queue.Count <> 0 do
  20.   begin
  21.     var current: integer;
  22.     current := queue.Dequeue();
  23.     visited[current] := true;
  24.    
  25.     if current = targetPoint then
  26.     begin
  27.       isFound := true;
  28.       break;
  29.     end;
  30.    
  31.     for var i := 0 to Length(graph, 1) - 1 do
  32.     begin
  33.       if (graph[current, i] = 1) and (not visited[i]) then
  34.         queue.Enqueue(i);
  35.     end;
  36.   end;
  37.   Result := isFound;
  38. end;
  39.  
  40. function DFS(startPoint: integer;
  41.               targetPoint: integer;
  42.               params graph: Array[,] of integer): boolean;
  43. begin
  44.   var stack: Stack<integer>;
  45.   stack := new Stack<integer>;
  46.  
  47.   var isFound: boolean;
  48.   isFound := false;
  49.  
  50.   var visited: Array[0..MaxN] of boolean;  
  51.   stack.Push(startPoint);
  52.  
  53.   while stack.Count <> 0 do
  54.   begin
  55.     var current: integer;
  56.     current := stack.Pop();
  57.     visited[current] := true;
  58.    
  59.     if current = targetPoint then
  60.     begin
  61.       isFound := true;
  62.       break;
  63.     end;
  64.    
  65.     for var i := 0 to Length(graph, 1) - 1 do
  66.     begin
  67.       if (graph[current, i] = 1) and (not visited[i]) then
  68.         stack.Push(i);
  69.     end;
  70.   end;
  71.   Result := isFound;
  72. end;
  73.  
  74. begin
  75.   var graph: array[,] of integer;
  76.   graph := new integer[10, 10];
  77.   for var i := 0 to Length(graph, 0) - 1 do
  78.     for var j := 0 to Length(graph, 1) - 1 do
  79.       graph[i,j] := 0;
  80.   var startPoint, targetPoint: integer;
  81.  
  82.   startPoint := 0;
  83.   targetPoint := 5;
  84.   Writeln(BFS(startPoint,targetPoint,graph));
  85.  
  86.   graph[0,3] := 1;
  87.   graph[3,5] := 1;
  88.   Writeln(BFS(startPoint,targetPoint,graph));
  89. end.
Advertisement