1

以下に示すような双方向グラフがあるとします。

ここに画像の説明を入力

これで、ソース 8 からの DFS Traversal は 8 1 2 3 6 7 4 5 になります。再帰的な実装

vector <int>  v[10001];
bool visited[10001];
void DFS(int s)
{
 visited[s]=true;
 cout<<s<<" ";
 for(int i=0;i<v[s].size();i++)
 {

 if(!visited[v[s][i]])
 {
     DFS(v[s][i]);
 }
 }
}

したがって、最初は再帰的に 8->1->2->3 、 8->6 、 8->7->4->5 になります

さて、この機能を使用して、すべてのノードのソースからの距離も追跡したいと思います。これを dist[N] と呼びましょう。N はノード数です。このグラフでは、dist[8]=0、dist 1 =1、dist[2]=2 などです。どうすればこれを実装できますか?

最初に、変数 d を保持して、以下のコードに示すようにインクリメントしようとしました

int d=0;
void DFS(int s)
{
 visited[s]=true;
 cout<<s<<" ";
 dist[s]=d;
 d++;
 for(int i=0;i<v[s].size();i++)
 {
 if(!visited[v[s][i]])
 {
     DFS(v[s][i]);
 }
 }
}

しかし、明らかに、d の値は、再び 8 に達したときに 0 にリセットする必要があります。そうしないと、上記の関数に従って、dist[6] は 1+ dist[3] になります。これを克服する方法は？また、これを達成するためのより効率的な方法はありますか?

4

1 に答える 1

0

グローバル変数の追跡深度を持つ代わりに、次の反復へのパラメーターにすることができます。

void DFS(int s, int d)
{
 visited[s]=true;
 cout<<s<<" ";
 dist[s]=d;
 for(int i=0;i<v[s].size();i++)
 {
     if(!visited[v[s][i]])
    {
       DFS(v[s][i], d+1);
    }
 }
}
于 2014-12-20T13:40:06.457 に答える