0

整数キーを持つ HashMap と値の ArrayList を使用して、グラフ アルゴリズムを実装しようとしています。

キーは頂点であり、ArrayList はキー頂点に接続されているすべての頂点です。

ブラックリストを使用して、どこに行ったかを追跡しています。アイテムがブラックリストにある場合、私はまだその頂点を訪れていません。このコードの問題は、プログラムの実行中に検索を複数回呼び出すことができる必要があることです。私がやっていることは、ブラックリストを頂点のあるグラフに向けることです。次に、頂点にアクセスすると、blackList の値を削除します。問題は、blackList が元のグラフの値を指していることです。そのため、検索を再度実行すると、元のグラフには、以前の検索で訪れたすべての頂点がありません。

TL:DR の質問は次のとおりです。ポイントを指定せずに新しい同一の HashMap を作成するにはどうすればよいですか。

HashMap をループして各エントリをコピーできることは理解していますが、多くの検索 (大規模な検索です!) を行うと遅くなります。それがそれを行う唯一の方法である場合、私はそのようにすることを超えていません。

 //The class variables used for this search
 HashMap<Integer, ArrayList<Integer>> mapBlacklist;
 Queue<Integer> line = new PriorityQueue<Integer>();
 int searchFor;
 boolean areTheyConnected;

 //The constructor I'm using
 GraphSearch(HashMap<Integer, ArrayList<Integer>> graph, int match){
    mapBlacklist = new HashMap<Integer, ArrayList<Integer>>(graph);
    searchFor = match;
 }
 //The search method.
 void numberOne(int start, HashMap<Integer, ArrayList<Integer>> graph){
    if(graph.get(start).contains(this.searchFor)){
        this.areTheyConnected = true;
    }
    else{
        while(!this.mapBlacklist.get(start).isEmpty()){
            this.line.add(this.mapBlacklist.get(start).get(0) ;
            this.mapBlacklist.get(start).remove(0);
        }
    }

    if(!this.line.isEmpty() && !this.areTheyConnected){
            numberOne(this.line.remove(), graph);
    }
}

メインメソッドでは：

/* What it looks like in the command line to see if vertices 2 5 are connected:
       1 2 5

   To close the program:
       0
*/
boolean keepGoing = true;
    while(keepGoing){
        Scanner sc = new Scanner(System.in);
        int number0 = Integer.parseInt(sc.next());
        if(number0 == 0){
            keepGoing = false;
            sc.close();
        }
        else if(number0 == 1){
            int number1 = Integer.parseInt(sc.next());
            int number2 = Integer.parseInt(sc.next());
           // GraphSearch gsearch = new GraphSearch(graph, number2);
            GraphSearch gsearch = new GraphSearch(mapGraph, number2);
            gsearch.numberOne(number1, mapGraph);
            System.out.println(gsearch.areTheyConnected);
        }
4

2 に答える 2

0

そもそもなぜこのマップブラックリストが必要なのですか?

アルゴリズムから、キューを使用して、アクセスしていないすべてのアイテムを (再帰的に) 反復処理できることがわかります。

ループの中：

while(!this.mapBlacklist.get(start).isEmpty()){
        this.line.add(this.mapBlacklist.get(start).get(0) ;
        this.mapBlacklist.get(start).remove(0);
    }

ブラックリストを使用せず、グラフから何も削除しないでください。現在の頂点のリストを反復処理し、その中のすべてのアイテムをキューに追加することしかできません。

それは理にかなっていますか？

于 2013-04-30T18:48:15.693 に答える