1

スタックを使用して可能なDFS実装はありますか?これは、グラフ(循環/非循環)の場合に、グラフ内のある頂点から別の頂点へのすべての可能なパスを提供します。

私の現在のDFSコードは次のとおりです:-

void Graph::DFS(int x, int required){
stack s;
bool *visited = new bool[n+1];
int i;
for(i = 0; i <= n; i++)
    visited[i] = false;
s.push(x);
visited[x] = true;
if(x == required) return;
cout << "Depth first Search starting from vertex ";
cout << x << " : " << endl;
while(!s.isEmpty())
{
    int k = s.pop();
    if(k == required)
    {
      cout<<k<<" ";
      break;
    }
    cout<<k<<" ";
    for (i = n; i >= 0 ; --i)
        if (isConnected(k, i) && !visited[i]) 
        {
            s.push(i);
            visited[i] = true;
        }
}
  cout<<endl;
  delete [] visited;
 }

これにより、存在する場合に可能なパスの1つが得られますが、必要なのはall possible paths1つだけではありません。

4

1 に答える 1

2

いいえ-無向グラフの場合、パスの数は無限です（任意のエッジを行き来するか、サイクルを回るだけです）。そのため、すべてを返すコードを記述できません。

他の制約（「各ノードに一度だけアクセスするパス」など）を適用する場合は、はい。

「各ノードに1回だけアクセスするパス」の制約については、基本的に検索を変更して、visited[i]が「このノードにアクセスしたことがあるか」ではなく「このパスで[i]これにアクセスしたことがあるか」になります。（現在のコードにあるように）そして、ターゲットに到達するたびに、現在のパスを見つかったパスのリストに追加し、見つからなかったかのように続行する必要があります。

于 2012-08-19T07:26:14.963 に答える