rybufc

BFS and DFS

Feb 4th, 2018
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Pascal 2.76 KB | None | 0 0
  1. ?uses System.Collections.Generic;
  2.  
  3. const
  4.   MaxN = 1000;
  5.  
  6. type
  7.   Point = class
  8.  
  9.   private
  10.     _index: integer;
  11.     _previous: Point;
  12.  
  13.   public
  14.     constructor(index: integer);
  15.     begin
  16.       _index := index;
  17.       _previous := nil;
  18.     end;
  19.    
  20.     procedure SetPrevious(previous: Point);
  21.     property Index: integer read _index;
  22.     property Previous: Point read _previous;
  23.   end;
  24.  
  25. procedure Point.SetPrevious(previous: Point);
  26. begin
  27.   _previous := previous;
  28. end;
  29.  
  30. function BFS(startPoint: integer;
  31.               targetPoint: integer;
  32.               params graph: Array[,] of integer): Point;
  33. begin
  34.   var queue: Queue<Point>;
  35.   queue := new Queue<Point>;
  36.  
  37.   var isFound: boolean;
  38.   isFound := false;
  39.  
  40.   var visited: Array[0..MaxN] of boolean;  
  41.   queue.Enqueue(new Point(startPoint));
  42.  
  43.   while queue.Count <> 0 do
  44.   begin
  45.     var current: Point;
  46.     current := queue.Dequeue();
  47.     visited[current.Index] := true;
  48.    
  49.     if current.Index = targetPoint then
  50.     begin
  51.       isFound := true;
  52.       result := current;
  53.       break;
  54.     end;
  55.    
  56.     for var i := 0 to Length(graph, 1) - 1 do
  57.     begin
  58.       if (graph[current.Index, i] = 1) and (not visited[i]) then
  59.       begin
  60.         var toAdd: Point;
  61.         toAdd := new Point(i);
  62.         toAdd.SetPrevious(current);
  63.         queue.Enqueue(toAdd);
  64.       end;
  65.     end;
  66.   end;
  67.   if not isFound then
  68.     result := nil;
  69. end;
  70.  
  71. function DFS(startPoint: integer;
  72.               targetPoint: integer;
  73.               params graph: Array[,] of integer): Point;
  74. begin
  75.   var stack: Stack<Point>;
  76.   stack := new Stack<Point>;
  77.  
  78.   var isFound: boolean;
  79.   isFound := false;
  80.  
  81.   var visited: Array[0..MaxN] of boolean;  
  82.   stack.Push(new Point(startPoint));
  83.  
  84.   while stack.Count <> 0 do
  85.   begin
  86.     var current: Point;
  87.     current := stack.Pop();
  88.     visited[current.Index] := true;
  89.    
  90.     if current.Index = targetPoint then
  91.     begin
  92.       isFound := true;
  93.       result := current;
  94.       break;
  95.     end;
  96.    
  97.     for var i := 0 to Length(graph, 1) - 1 do
  98.     begin
  99.       if (graph[current.Index, i] = 1) and (not visited[i]) then
  100.       begin
  101.         var toAdd: Point;
  102.         toAdd := new Point(i);
  103.         toAdd.SetPrevious(current);
  104.         stack.Push(toAdd);
  105.       end;
  106.     end;
  107.   end;
  108.   if not isFound then
  109.     result := nil;
  110. end;
  111.  
  112. begin
  113.   var graph: array[,] of integer;
  114.   graph := new integer[10, 10];
  115.   for var i := 0 to Length(graph, 0) - 1 do
  116.     for var j := 0 to Length(graph, 1) - 1 do
  117.       graph[i, j] := 0;
  118.   var startPoint, targetPoint: integer;
  119.  
  120.   startPoint := 0;
  121.   targetPoint := 5;
  122.   Writeln(BFS(startPoint, targetPoint, graph));
  123.  
  124.   graph[0, 3] := 1;
  125.   graph[3, 5] := 1;
  126.   Writeln(DFS(startPoint, targetPoint, graph));
  127. end.
Advertisement