rybufc icon

BFW and DFW

rybufc | PRO | 02/04/18 12:01:38 PM UTC | 0 ⭐ | 7259 👁️ | Never ⏰ | []
Pascal |

1.95 KB

|

None

|

0 👍

/

0 👎

?uses System.Collections.Generic;
 
const
  MaxN = 1000;
 
function BFS(startPoint: integer;
              targetPoint: integer; 
              params graph: Array[,] of integer): boolean;
begin
  var queue: Queue<integer>;
  queue := new Queue<integer>;
  
  var isFound: boolean;
  isFound := false;
  
  var visited: Array[0..MaxN] of boolean;  
  queue.Enqueue(startPoint);
  
  while queue.Count <> 0 do
  begin
    var current: integer;
    current := queue.Dequeue();
    visited[current] := true;
    
    if current = targetPoint then
    begin
      isFound := true;
      break;
    end;
    
    for var i := 0 to Length(graph, 1) - 1 do
    begin
      if (graph[current, i] = 1) and (not visited[i]) then
        queue.Enqueue(i);
    end;
  end;
  Result := isFound;
end;
 
function DFS(startPoint: integer;
              targetPoint: integer; 
              params graph: Array[,] of integer): boolean;
begin
  var stack: Stack<integer>;
  stack := new Stack<integer>;
  
  var isFound: boolean;
  isFound := false;
  
  var visited: Array[0..MaxN] of boolean;  
  stack.Push(startPoint);
  
  while stack.Count <> 0 do
  begin
    var current: integer;
    current := stack.Pop();
    visited[current] := true;
    
    if current = targetPoint then
    begin
      isFound := true;
      break;
    end;
    
    for var i := 0 to Length(graph, 1) - 1 do
    begin
      if (graph[current, i] = 1) and (not visited[i]) then
        stack.Push(i);
    end;
  end;
  Result := isFound;
end;
 
begin
  var graph: array[,] of integer;
  graph := new integer[10, 10];
  for var i := 0 to Length(graph, 0) - 1 do
    for var j := 0 to Length(graph, 1) - 1 do
      graph[i,j] := 0;
  var startPoint, targetPoint: integer;
  
  startPoint := 0;
  targetPoint := 5;
  Writeln(BFS(startPoint,targetPoint,graph));
  
  graph[0,3] := 1;
  graph[3,5] := 1;
  Writeln(BFS(startPoint,targetPoint,graph));
end.

Comments

  •  icon
    01/01/70 12:00:00 AM UTC
    Plain Text |

    0 B

    |

    👍

    /

    👎

    
        
  •  icon
    01/01/70 12:00:00 AM UTC
    Plain Text |

    0 B

    |

    👍

    /

    👎