1

グラフが接続されているかどうかを判断するアルゴリズムを作成しようとしています。StackOverFlowErrorが発生し続けますが、コードはほぼ正しいと思います。個人的には、アルゴリズムをテストしているグラフにサイクルがあるため、コードはそれを理解せず、ループに陥っていると思います。しかし、私は配列を使用して、ノードがすでにアクセスされているかどうかを確認しています！だからそれは起こらないはずです！とにかくこれは私のコードです：

public int isConnected(String s) 
    {

        int in = nodes.indexOf(s);


        visited[in] = true;
        counter++;
        for(int i = 0; i < listOfChildren(s).size(); i++)
        {
            int ind = nodes.indexOf(listOfChildren(s).get(i));
            if(visited[ind] == false)
            {
                isConnected(listOfChildren(s).get(i));
            }

        }
        System.out.println(counter);
        if(counter == nodes.size())
            return 1;
        return 0;

    }

sは私が始めたノードであり、ノードはノードのArrayListであり、アクセスした配列と同じサイズ（この場合は5）です。最初に訪問したのは次のようになります：[false false false false false]、したがって、どのノードも訪問されませんでした。listOfChildren（）は、特定のノードの子（すべてではなく、ノードに隣接する子のみ）のArrayListを返します。私は43545454回テストしたので、listOfChildren（）が機能すると確信しています。

どんな助けでもありがたいです（可能であれば、コードの最小限の変更で）。ありがとう。

アップデート：

私のグラフは指示されています。

私はこのように訪問を定義します：

private boolean[] visited;

このコードでは、コンストラクターでその中のすべてをfalseに設定します。

public void setUnvisited()
    {
        visited =  new boolean[nodes.size()];

        for(int i = 0; i < nodes.size(); i++)
        {
            visited[i] = false;
        }
    }

ノードは文字列です！訪問済みノードとノードの長さは同じです。そのため、アクセスした配列にnodes.indexOf（blabla）を使用できます。

UPDATE2：

グラフは次のようになります。 ここに画像の説明を入力してください

問題はN3の後であると確信しています。アルゴリズムは、N1がすでにアクセスされていることを理解していないため、N3の後でループします。なぜこれが起こるのか本当にわかりません！

UPDATE3

文字列の名前は異なり、重複はありません。たとえば、indexOf（nodes.get（2））は0などではなく2を返します。

問題は、N3にアクセスした後、アルゴリズムが停止して0または1を返す必要があることですが、その方法がわかりません:)

4

3 に答える 3

2

これを追跡するのが非常に難しいと思った理由は、グラフクラスのすべての可変状態です。特に、とがcountありvisited、後者はメソッドisConnectedとの両方によって変更されますsetUnvisited。

再帰を停止するタイミングを配列に依存していますvisitedが、への呼び出しを介した再帰呼び出しごとに誤って配列をリセットしますlistOfChildren。

これを回避してvisited、クラスメンバーにならないようにする1つの方法。コードをほとんど変更しないソリューションは次のとおりです。

public boolean isConnected(String s) {
    int nVisited = isConnected(s, new boolean[nodes.size()], 0);
    return nVisited == nodes.size();
}

private int isConnected(String s, boolean[] visited, int counter) 
{

    int in = nodes.indexOf(s);


    visited[in] = true;
    counter++;
    for(int i = 0; i < listOfChildren(s).size(); i++)
    {
        int ind = nodes.indexOf(listOfChildren(s).get(i));
        if(visited[ind] == false)
        {
            counter = isConnected(listOfChildren(s).get(i), visited, counter);
        }

    }
    System.out.println(counter);
    return counter;
}

visitedとcounterは共有されなくなったため、発生していたバグはなくなりました。isConnected()これにより、最初の呼び出しのみが機能する（ただし、まだ気づいていない）別のバグも解決されます。この場合、リセットまたは適切にリセットされていなかったためです。visitedcounter

上記と同じアイデアのよりクリーンな実装：

public boolean isConnected(String s) {
    Set<String> visited = new HashSet<String>();
    isConnected(s, visited);
    return visited.size() == nodes.size();
}

private void isConnected(String s, Set<String> visited) 
{
    visited.add(s);
    for (String child : listOfChildren(s)) {
        if (!visited.contains(s)) {
            isConnected(child, visited);
        }
    }
}

私は実際にそれをコンパイルしたり実行したりしていないので、バグがあるかもしれませんが、あなたはその考えを理解していると思います。

于 2011-02-20T12:18:23.120 に答える
1

私はあなたの更新に基づいて小さなテストプログラムを作成しました、そしてそれは魅力のように機能するようです：

public class NodeTest
{
    static ArrayList<String> nodes = new ArrayList<String>();
    boolean visited[] = {false, false, false, false, false};

    int counter = 0;

    static HashMap<String, ArrayList<String>> childMap = new HashMap<String, ArrayList<String>>();

    static
    {
        nodes.add("N0");
        nodes.add("N1");
        nodes.add("N2");
        nodes.add("N3");
        nodes.add("N4");

        //N4 --> N2 --> N3 --> N1 <-- N0
        //       ^-------------+
        ArrayList<String> list = new ArrayList<String>();
        list.add("N2");
        childMap.put("N4", list); //N4 to N2

        list = new ArrayList<String>();
        list.add("N3"); 
        childMap.put("N2", list); //N2 to N3

        list = new ArrayList<String>();
        list.add("N1");
        childMap.put("N3", list); //N3 to N1

        list = new ArrayList<String>();
        list.add("N2");
        childMap.put("N1", list); //N1 to N2

        list = new ArrayList<String>();
        list.add("N1");
        childMap.put("N0", list); //N0 to N1
    }

    @Test
    public void test()
    {
        System.out.println("Is connected = " + isConnected("N0"));
    }

    public int isConnected(String s) 
    {
        System.out.println("Handling node " + s);

        int in = nodes.indexOf(s);


        visited[in] = true;
        counter++;
        for(int i = 0; i < listOfChildren(s).size(); i++)
        {
            int ind = nodes.indexOf(listOfChildren(s).get(i));
            if(visited[ind] == false)
            {
                System.out.println("Recursing into child " + listOfChildren(s).get(i));
                isConnected(listOfChildren(s).get(i));
            }
            else
            {
                System.out.println("Node " + listOfChildren(s).get(i) + " has already been visited");
            }

        }
        //System.out.println(counter);
        if(counter == nodes.size())
            return 1;
        return 0;

    }

    public ArrayList<String> listOfChildren(String s)
    {
        return childMap.get(s);
    }

}

isConnected-methodはあなたのものと同じです、私はロギングのためにいくつかのメッセージを追加しました。出力：

Handling node N0
Recursing into child N1
Handling node N1
Recursing into child N2
Handling node N2
Recursing into child N3
Handling node N3
Node N1 has already been visited
Is connected = 0

予想どおり、グラフは接続されていません（質問で描いたのと同じグラフです）。開始ノードをN4に変更し、N1の唯一の子をN0に変更すると、アルゴリズムはグラフを接続済みとして正しく認識します。これに基づいて、問題は、listOfChildrenが奇妙なものを返すか、 visitedで使用されるインデックス（ある時点で、visited [in] = trueは、 if（visited [ind] == false）以外のインデックスをvisitedとしてマークすることです。 ）それらがいつ同じである必要があるかをチェックしていますか？）

于 2011-02-20T12:11:57.133 に答える
0

本当の問題は、ノードを文字列で表現しようとしていることです。そうすることで、ノードの子を別の場所に保存する必要がありますlistOfChildren。また、訪問した人を追跡する必要がありますboolean[] visited。

ノードは2つの方法で識別されるようになりました

  1. listOfChildrenは文字列表現を使用します"node1","node2",...
  2. visited []は、のインデックスであるインデックスを使用しますnodes。

おほ。ここで、すべての文字列表現がノード配列に1つのインデックスを持っていることを確認する必要があります。（2つのIDの1対1のマッピングが必要です。）

nodes.add("node");
nodes.add("node");
nodes.add("node");

return nodes.indexOf( nodes.get(2) );//what does this return? 0!

問題がわかりますか？'node'インデックスが3つあるノード、または同じ名前のノードが3つあります。

しかし、私は配列を使用して、ノードがすでにアクセスされているかどうかを確認しています！

たぶんそれは同じ'ノード'ではありません、あなたは文字列'ノード'、またはインデックス'ノード'を意味しますか？

これを修正するには、ノードに対して1つの識別、1つの表現を作成します。

public class Node
{
  List<Node> children;
}

文字列やインデックスは必要ありません！ノードをノードとします。

于 2011-02-20T11:44:19.683 に答える