Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- ?uses System.Collections.Generic;
- const
- MaxN = 1000;
- type
- Point = class
- private
- _index: integer;
- _previous: Point;
- public
- constructor(index: integer);
- begin
- _index := index;
- _previous := nil;
- end;
- procedure SetPrevious(previous: Point);
- property Index: integer read _index;
- property Previous: Point read _previous;
- end;
- procedure Point.SetPrevious(previous: Point);
- begin
- _previous := previous;
- end;
- function BFS(startPoint: integer;
- targetPoint: integer;
- params graph: Array[,] of integer): Point;
- begin
- var queue: Queue<Point>;
- queue := new Queue<Point>;
- var isFound: boolean;
- isFound := false;
- var visited: Array[0..MaxN] of boolean;
- queue.Enqueue(new Point(startPoint));
- while queue.Count <> 0 do
- begin
- var current: Point;
- current := queue.Dequeue();
- visited[current.Index] := true;
- if current.Index = targetPoint then
- begin
- isFound := true;
- result := current;
- break;
- end;
- for var i := 0 to Length(graph, 1) - 1 do
- begin
- if (graph[current.Index, i] = 1) and (not visited[i]) then
- begin
- var toAdd: Point;
- toAdd := new Point(i);
- toAdd.SetPrevious(current);
- queue.Enqueue(toAdd);
- end;
- end;
- end;
- if not isFound then
- result := nil;
- end;
- function DFS(startPoint: integer;
- targetPoint: integer;
- params graph: Array[,] of integer): Point;
- begin
- var stack: Stack<Point>;
- stack := new Stack<Point>;
- var isFound: boolean;
- isFound := false;
- var visited: Array[0..MaxN] of boolean;
- stack.Push(new Point(startPoint));
- while stack.Count <> 0 do
- begin
- var current: Point;
- current := stack.Pop();
- visited[current.Index] := true;
- if current.Index = targetPoint then
- begin
- isFound := true;
- result := current;
- break;
- end;
- for var i := 0 to Length(graph, 1) - 1 do
- begin
- if (graph[current.Index, i] = 1) and (not visited[i]) then
- begin
- var toAdd: Point;
- toAdd := new Point(i);
- toAdd.SetPrevious(current);
- stack.Push(toAdd);
- end;
- end;
- end;
- if not isFound then
- result := nil;
- 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(DFS(startPoint, targetPoint, graph));
- end.
Advertisement