0

次のように視覚的に表された、6つの頂点を持つ無向グラフを作成しました：http：//i.imgur.com/EtQyspG.png

同じノードに再度アクセスすることなく、開始点からすべてのパスを見つけることができ、終了点が指定されていないスクリプトを作成したいと思います。

私が見たBFS、DFS、A *アルゴリズムのすべての例には、最終宛先ノードが必要です。ただし、より大きなグラフでは、ポイントAからポイントZまでのすべての可能な経路を見つけるのはNP困難かもしれません。このため、設定された移動回数内で達成可能なすべての目的地へのすべての経路を見つけたいと思います（このグラフ上）たとえば、-3つの移動==パス内の最大4つの頂点）

PHP配列を使用してグラフをコーディングしました。各キーは頂点であり、その配列には隣接するポイントが含まれています。

<?php

$graph[1] = array(2,6);
$graph[2] = array(1,4);
$graph[3] = array(4,5);
$graph[4] = array(2,3,6);
$graph[5] = array(6,3);
$graph[6] = array(1,5,4);

ただし、この方法でパス検索を実行するアルゴリズムはわかりません。私の希望する出力は次のようになります。

Path 1: 1,2
Path 2: 1,2,4
Path 3: 1,2,4,3
Path 4: 1,6
Path 5: 1,6,4,3
Path 6: 1,6,5
Path 7: 1,6,5,3

必要なコードを書くのに問題はありませんが、アルゴリズム/関数に必要な手順（ツリートラバーサル再帰を想定していますか？）を理解するのは困難です。

質問：これを行うにはどのようなアプローチ/アルゴリズムを使用する必要がありますか？グラフ入力配列が与えられた場合にどのように機能するかを示す例（または少なくとも擬似コード）はありますか？

4

2 に答える 2

0

単一の開始点と分岐により、ツリーを構築するように指示されます。これは、限られた深さのツリー検索です。各レベルで、すでにアクセスしたノードを整理する必要があります。擬似コードはwikiの記事にあります

于 2013-02-24T22:01:00.443 に答える
0

密グラフ（| E | 〜O（| V | ^ 2））では、出力のサイズは最大移動量の指数関数であり、プログラムはデータのサイズに少なくとも線形で時間がかかります。出力する必要があります。

要求したことを実行する最も簡単な方法は、バニラ再帰DFSアルゴリズムを使用して、次のように変更することです。

1）頂点のスタックは、実際のスタックで維持されます（つまり、配列/ベクトル/ Pythonリストなど、PHPに相当するものは何でも）。呼び出す前にターゲット頂点を挿入し、呼び出しが戻った後にポップします。

2）深さkに達すると、関数はスタックを出力に出力し、

3）再帰関数は、戻る直前に現在の頂点の「マークを外す」

ただし、PHPについては特にお手伝いできません。

于 2013-02-24T22:07:27.983 に答える