2

インターネットを調べましたが、オブジェクトパスカルにDFS（深さ優先探索）またはBFS（幅優先探索）のコード例が見つからなかったため、Delphiで実装できます。

グラフ理論を知らない方はこちら

グラフオブジェクトのあり方が原因で、自分で開発するのは難しいです。とは関連していて、配列を使用するverticesかどうか、またそれらのデータをどのように構造化するかはわかりません。プレビューの例がいくつかあれば、最初から始めるのではなく、最善のアプローチを選択できます（このサイトはそのためにここにあると思います）。edgesrecordsobjects

どこから始めればいいのか誰か知っていますか？

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

（DFS）と（BFS）DelphiForFun Graph Searchingの両方を実装する例とチュートリアルを見つけることができるを参照することをお勧めします。depth first searchbreadth first search

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 に答える