再帰関数によって使用されるグローバル変数

Question

Graphクラスを実装する必要があり、いくつかのアルゴリズムが含まれていて、dfs（深さ優先探索）を使用しているとします。例えば、それは接続性チェックであるかもしれないとGraphクラスは、次のようになります。

class Graph { 
    void dfsConnected(int v) { 
     visited[v] = true; 
     //indexing over v's adjacencies and calling dfsConnected recursively 
    } 
    bool isConnected { 
     //indexing over vertice list and calling dfsConnected 
    } 
} 

は、（それらのすべてのは、特定のDFSを使用しています）このクラスでは、DFSを使用して、我々はアルゴリズムの束を持っていると仮定します。などvisitedConnectivity、visitedTopSorting、visitedBridges、のようなすべてのDFSは、だから我々はGraphのすべてのインスタンスにプライベート変数の多くを持つことになりますため、我々はプライベートフィールドとして、それを定義することができ

• ： 問題がvisited配列です。そして、すべてのdfsに対してこのような「グローバル」変数が3-4ある場合はどうなりますか？
• をdfsの引数として渡すことができます。この場合、すべてのdfs呼び出しにオーバーヘッドが発生します。

この問題の最も簡単で現実的な解決策は何ですか？もちろん、それはグラフアルゴリズムだけでなく、dfsという言葉で簡単に説明することができます。

Answer 1

よりOOPの方法は、私の意見では、各DFSクラスのフィールドvisitedをdelcaring、そしてそれは、独自のDFSを実行しますされて....

それは私が割り当てられなかった何を追跡することを防止することができます？それはどこに接続されていますか？等...」

は

あなたのDFSは、はるかにカプセル化され、その後、あなたが個別に維持する必要があります各DFSのための追加のパラメータを追加し、少ないデータが必要になります。

ここでのパフォーマンス上の問題がありますほとんどの場合、読みやすさに無視され、maintainabilityはできるだけ多くのデータをクラスそのものにカプセル化して実現します

Answer 2

visitedを引数として渡します。オーバーヘッドはありません！

更新OK私は訂正しました。 ）オーバーヘッドが無視できると言いましょう;）でも、関数の外側では意味のないフィールド/グローバル変数を持ち、毎日やり遂げられた後にメモリを食べるということで、スタック内にポインタを置くことを選択します。

本当に気にしている場合は、DFSを独自のvisitedフィールドを持つオブジェクトにカプセル化し、そのグラフを引数として取ります。しかしそれでもおそらくスタック上のオブジェクトポインタを持つ関数呼び出しに変換されます。

Answer 3

静的変数を使用できます。