2

我查看了 Internet，并没有在 object pascal 中找到任何 DFS（深度优先搜索）或 BFS（广度优先搜索）的代码示例，因此我可以在 Delphi 中实现它们。

不懂图论的可以点这里

由于图形对象的方式，我很难自己开发它。我们有vertices和edges之间相关的，我不知道我是否使用records,objects或数组，也不知道如何构造这些数据。如果我有一些预览示例，我可以选择一个最佳方法，而不是从头开始（我相信这个网站就是为了它）。

有谁知道从哪里开始？

具有 6 个边和 7 个顶点的图

在我的项目中，我必须在其中插入一个新图，然后进行 DFS 搜索以捕获所有边缘并发现到高速公路的最近路径。

4

2 回答 2

3

简短的回答是，您可以通过保持关联数组将访问节点映射到先前节点和访问的邻居的联合来实现 DFS。

用法

这是解决方案表面上的样子。假设您定义了一个节点...

type
INode = interface
  ['{8D3C78A3-3561-4945-898D-19C5AD4EC35B}']
    {$REGION 'property accessors'}
      function GetNeighbour( idx: Integer): INode;
      function GetNeighbourCount: integer;
    {$ENDREGION}
    function  DisplayName: string;
    function  Link( const Neighbours: INode): boolean; // True iff succesful.
    procedure ShutDown; // Dereference all nodes recursively.
    property  Neighbours[ idx: Integer]: INode  read GetNeighbour;
    property  NeighbourCount: integer           read GetNeighbourCount;
  end;

我将 INode 的实现留给 OP，因为 (A) 它是微不足道的；(B) 因为它是高度应用特定的。

您将能够遍历节点网络深度优先，原文如此......

procedure DFSTraversal( const Start: INode);
var
  X: INode;
begin
for X in TGraph.DepthFirstSearch( Start) do
  DoSomething( X);
end;

...在一些声明的帮助下...

INodeEnumerator = interface
  ['{1A8725EB-AE4B-474C-8052-E35852DCD5FC}']
    function  GetCurrent: INode;
    function  MoveNext: Boolean;
    procedure Reset;
    property  Current: INode read GetCurrent;
  end;

IEnumerableNode = interface
  ['{DA11A890-01C4-4FD0-85BB-AE9D65185364}']
    function GetEnumerator: INodeEnumerator;
  end;

TGraph = class
  public
    class function DepthFirstSearch( const StartingPoint: INode): IEnumerableNode;
  end;

解决方案

深度优先搜索可以很容易地实现，如前所述，使用关联数组将访问过的节点映射到之前的节点和访问过的邻居。这个关联数组被封装到类型 TDictionary 中。以下是它的实现方式......

type
TBaseEnumerableNode = class abstract( TInterfacedObject, IEnumerableNode)
  protected
    function GetEnumerator: INodeEnumerator; virtual; abstract;
  end;

TDepthFirstSearchEnumerable = class( TBaseEnumerableNode)
  private
    FRoot: INode;
  protected
    function GetEnumerator: INodeEnumerator; override;
  public
    constructor Create( const Root: INode);
  end;

TBaseNodeEnumerator = class abstract( TInterfacedObject, INodeEnumerator)
  private
    function  GetCurrent: INode;
    procedure Reset;
  protected
    FCurrent: INode;
    function  MoveNext: Boolean;  virtual; abstract;
  end;

RTraversalInfo = record
    FCurrIndex: integer;
    FPredecessor: INode;
  end;

TDepthFirstSearchEnumerator = class ( TBaseNodeEnumerator)
  private
    FVisitedNodes: TDictionary<INode,RTraversalInfo>;
  protected
    function  MoveNext: Boolean;  override;
  public
    constructor Create( const Root: INode);
    destructor Destroy; override;
  end;


class function TGraph.DepthFirstSearch(
  const StartingPoint: INode): IEnumerableNode;
begin
result := TDepthFirstSearchEnumerable.Create( StartingPoint)
end;


constructor TDepthFirstSearchEnumerable.Create( const Root: INode);
begin
FRoot := Root
end;

function TDepthFirstSearchEnumerable.GetEnumerator: INodeEnumerator;
begin
result := TDepthFirstSearchEnumerator.Create( FRoot)
end;


function TBaseNodeEnumerator.GetCurrent: INode;
begin
result := FCurrent
end;

procedure TBaseNodeEnumerator.Reset;
begin  // Not used.
end;

constructor TDepthFirstSearchEnumerator.Create( const Root: INode);
var
  TravInfo: RTraversalInfo;
begin
FCurrent := Root;
FVisitedNodes := TDictionary<INode,integer>.Create;
TravInfo.FCurrIndex   := -1;
TravInfo.FPredecessor := nil;
FVisitedNodes.Add( FCurrent, TravInfo)
end;

destructor TDepthFirstSearchEnumerator.Destroy;
begin
FVisitedNodes.Free;
inherited
end;

function TDepthFirstSearchEnumerator.MoveNext: boolean;
var
  ChildIdx: integer;
  LastIdx : integer;
  TravInfo: RTraversalInfo;
  Next    : INode;
  Child   : INode;
  GoDown  : boolean;
begin
result := assigned( FCurrent);
if not result then exit;
result := False;
Next := FCurrent;
FCurrent := nil;
repeat
  TravInfo := FVisitedNodes[ Next];
  ChildIdx := TravInfo.FCurrIndex;
  LastIdx  := Next.NeighbourCount - 1;
  GoDown := ChildIdx <= LastIdx;
  if GoDown then
    begin
    Inc( ChildIdx);
    TravInfo.FCurrIndex := ChildIdx;
    FVisitedNodes[ Next] := TravInfo;
    GoDown := ChildIdx <= LastIdx
    end;
  if GoDown then
      begin
      Child := FCurrent.Neighbours[ ChildIdx];
      result := not FVisitedNodes.ContainsKey( Child);
      if result then
          begin
          FCurrent := Child;
          TravInfo.FPredecessor := Next;
          TravInfo.FCurrIndex   := -1;
          FVisitedNodes.Add( FCurrent, TravInfo)
          end
        else
          Next := Child
      end
    else
      Next := TravInfo.FPredecessor
until result or (not assigned( Next))
end;
于 2013-03-20T00:11:53.783 回答
1

我建议查看DelphiForFun Graph Searching，您可以在其中找到实现depth first search(DFS) 和breadth first search(BFS) 的示例和教程。

DFS 的数据包含在TStringList后代中，其中节点用文本字符串标识，该字符串也用作排序的键。排序是使用二分搜索算法完成的。

包含指向相邻节点 ( adjecency list) 的指针列表的节点数据作为每个项目字符串的对象存储在字符串列表中。

引用关于 DFS 算法的教程：

Here is the pseudocode for depth first search: 

SearchGoalDF(nodenbr, goalkey, maxdepth) - search depth first for all solutions from nodenbr node to goalkey node with depth of maxdepth or less.
    Set visited array to false, visited has an boolean entry for each node.
    clear stack
    push nodenbr node onto stack
    call dfs
    end.
dfs

pop (retrieve and delete)  most current stack entry, temp.
    mark temp as visited.  {to avoid looping back here as we search on down}
    if  temp.key=goalkey then notify caller of solution found
    else if stack.count<maxdepth then for each  node in temp's adjacency list, 
    push adjacent[i] onto stack
    call dfs
     mark temp as unvisited {there might be another path through this node to a solution}
    end.

希望这能让您开始并了解如何处理节点数据。

请注意，寻找最短路径，BFS 算法似乎做得更好：

见Shortest path: DFS, BFS or both?和Why can't DFS be used to find shortest paths in unweighted graphs?。

于 2013-03-19T23:52:49.620 回答