2

だから私はコンマで区切られた一度に1行で読むこの割り当てを持っています。

Atlanta, Philadelphia   
New York, Philadelphia   
Philadelphia, Chicago   
Washington, Florida
.....
up to a vast amount.. (I don't know the amount)

各線は 2 つの場所の間の接続を表します (たとえば、アトランタはフィラデルフィアに接続します)。接続されたノードと接続されていないノードを作成します。たとえば、ワシントンとフロリダは互いに接続されていますが、他には接続されていません。

プログラムが行うことになっているのは、ファイルを読み取り、2 つの都市の引数を指定すると、接続されている場合は [はい]、接続されていない場合は [いいえ] を吐き出すことです。

プログラムを終了し、動作しますが、効率的ではありません。私は何ができるのか途方に暮れています。これは、コードを非効率にするプログラムの一部です。

この最初の入力でファイルが読み取られるため、さまざまな都市のリストのサイズを判断できます。また、重複する都市はすべて削除されます。

private static void createCityList() throws IOException{

        try {
            FileReader a = new FileReader(file);
            BufferedReader br = new BufferedReader(a);
            String line;
            line = br.readLine();

            while(line != null){
                StringTokenizer st = new StringTokenizer(line, ",");
                while(st.hasMoreTokens()){ 
                    String currentToken = st.nextToken();
                    if(!cityList.contains(currentToken.trim())){ 
                        cityList.add(currentToken.trim());
                    }//if
                }//while hasMoreTokens
                line = br.readLine();//read the next line
            }//while line != null
            br.close();
        }//try

        catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        length = cityList.size(); // set length to amount of unique cities

    }//createCityList

別のファイル読み取りを行う2番目の方法...隣接行列を作成できます

private static void graph() throws IOException{ 
    cityGraph = new int[cityList.size()][cityList.size()]; 

        try {
            FileReader a = new FileReader(file);
            BufferedReader br = new BufferedReader(a);
            String line;
            line = br.readLine();


            while(line != null){
                StringTokenizer st = new StringTokenizer(line, ",");
                while(st.hasMoreTokens()){ 
                    String firstToken = st.nextToken().trim();
                    String secondToken = st.nextToken().trim();
                    cityGraph[cityList.indexOf(firstToken)][cityList.indexOf(secondToken)] = 1; 
                    cityGraph[cityList.indexOf(secondToken)][cityList.indexOf(firstToken)] = 1; 
                }//while hasMoreTokens

                line = br.readLine();//read the next line

            }//while line != null

            br.close();

        }//try

        catch (FileNotFoundException e) {
            e.printStackTrace();
        }//catch
    }//graph

最後に、2 つの都市で DFS を実行して、接続されているかどうかを判断します。

private static void isConnected(String s1, String s2){

        city1 = cityList.indexOf(s1); //set city to the index of s1 or s2 in the cityList LinkedList.
        city2 = cityList.indexOf(s2); 


        int startNode = city1;
        q.add(startNode); // start node

        while(!q.isEmpty()){
        //visit vertex
            for(int i = 0; i < length; i++){
                if(cityGraph[startNode][i] == 1){
                    if( i == city2 ){ 
                        System.out.println("yes");
                        return;
                    }//if city2 found
                    q.add(i);
                    cityGraph[startNode][i] = 0; //Set to visited
                }//if vertex exist
            }//for
            q.remove();//remove the top element and start with new node
            if(!q.isEmpty()){
                startNode = (Integer) q.element();
            }//if

        }//while q is not empty     
        System.out.println("no");
    }//isConnected

私は 1 つのファイルのみを読み取ろうとしていますが、ファイルを読み取ってサイズがわかった後でのみ、未知のサイズからマトリックスを作成する際に問題が発生しています。どんな助けや提案も大歓迎です!

4

3 に答える 3

2

コードについていくつかコメントがあります。

1）最初のコードスニペットでこれらの行を取得します。

while(st.hasMoreTokens()){ 
    String currentToken = st.nextToken();
    if(!cityList.contains(currentToken.trim())){ 
        cityList.add(currentToken.trim());
    }//if
}//while hasMoreTokens

このcityList.contains()方法では、都市の数に線形の時間がかかり、密なグラフを作成できるため、Vが頂点の数であるwhile(st.hasMoreTokens())実行時間が発生する可能性があります。O(V^2)したがって、この1つのループだけで、O（V ^ 3）時間を消費しています。O(V + E)これは、DFS（O(V^2)密グラフにある）よりもすでに最悪です。すべてのエッジを読み取る必要があるため、O（V ^ 2）ループを高速化することはできませんが、より効率的なデータ構造を使用して、その都市リスト、つまりハッシュ（O(1)ルックアップ、O(1)挿入）を保持できます。

2）2番目のコードスニペット：

while(st.hasMoreTokens()){ 
    String firstToken = st.nextToken().trim();
    String secondToken = st.nextToken().trim();
    cityGraph[cityList.indexOf(firstToken)][cityList.indexOf(secondToken)] = 1; 
    cityGraph[cityList.indexOf(secondToken)][cityList.indexOf(firstToken)] = 1; 
}//while hasMoreTokens

まったく同じこと。リストの代わりにハッシュを使用します。

3）DFSの内部ループ

if(cityGraph[startNode][i] == 1){
    if( i == city2 ){ 
        System.out.println("yes");
        return;
    }//if city2 found
    q.add(i);
    cityGraph[startNode][i] = 0; //Set to visited
}//if vertex exist

2つの問題があります。1つは、DFSを実行するたびにグラフ表現を上書きしていることです。設定cityGraph[startNode][i] = 0;することにより、実際にグラフの端を削除します。すべてのDFSのグラフを再構築する場合、それは大きな問題です。

2番目の問題は、訪問したノードを間違った方法でマークしているように見えることです。ノードではなく、訪問したEDGESをマークしているだけです。パス1->2とパス1->4->2がある場合は、ノード2に2回アクセス（およびキューに追加）します。

両方の問題を解決するには、boolean visited[#cities]配列を使用します。DFSを開始するたびに、すべてのノードを非アクセスに設定します。エッジをチェックするたびに、そのノードに既にアクセスしたかどうかをチェックします。そうでない場合は、キューに追加します。

最後に、

q.remove();//remove the top element and start with new node
if(!q.isEmpty()){
    startNode = (Integer) q.element();
}//if

whileループでキューが空かどうかをすでに確認しているため、これは醜いです。代わりに、このコードをwhileループの最初に移動して、if条件を削除することができます（キューが空ではないことがわかっているため）。

while(!q.isEmpty()){
    startNode = (Integer) q.element();
    q.remove();

お役に立てば幸いです。

于 2011-02-17T05:22:02.113 に答える
1

これは双方向グラフですか、それとも単方向グラフですか？

いずれにせよ、ある都市から別の都市へのエッジを表すためにマップを使用するとよいでしょう。それを考えると、あなたはメソッドを書くことができます

getReachableNodes（String startNode、Map到達可能性）;を設定します。

目的のターゲットが結果のセットに含まれているかどうかを確認します。

于 2011-02-17T04:54:50.120 に答える
1

優れたソフトウェアの鍵は、最適なデータ構造を選択することだと思います。それは手順よりも重要だと思います（もちろん重要ですが）。巨大なグラフの 2 次元配列と膨大な数の都市のリストが最適なデータ構造であるとは思いません。どちらのタイプのデータ構造でも、線形検索を行う必要があります。これらのデータ構造のサイズが大きくなるにつれて、速度が低下することを意味します。

そこで、 と に依存する部分の再設計を提案しHashMap<String>ますHashSet<String>。HashMap の主な価値は一定のルックアップ時間です。つまり、パフォーマンスが低下することはありません (仕組みに興味がある場合は、ウィキペディアを参照してください)。

したがって、上記のいくつかの回答が示唆したように、擬似コードの概要は次のようになります。

HashMap<String, HashSet<String>> m = new ...
For each pair c1 c2 {
     if c1 is not a key in m {
          HashSet<String> set = new HashSet<String>
          set.add(c2)
          m.put(c1, set);

     }
     else //c is a key
          m.get(c1).add(c2)
 }

ここで、c1 と c2 が接続されているかどうかを調べます。

boolean isDirectlyConnected(c1, c2) { 
  return m.get(c1).contains(c2) || m.get(c2).contains(c1) 
}         

boolean isConnected (c1, c2) {    //checking the transitive closure of directly connected
   HashSet<String> citiesAlreadyChecked = new ...   //cities whose edges have already been checked
   Queue<String>  citiesToCheck = new ...
   citiesToCheck.push(c1)
   while (citiesToCheck is not empty) {
         String cityBeingCurrentlyChecked = citiesToCheck.pull
         if (isDirectlyConnected(cityBeingCurrentlyChecked,c2)) {
               return true;
         } 
         else {
               citiesAlreadyChecked.add(cityBeingCurrentlyChecked)
               for (String adjacentCity: m.get(cityBeingCurrentlyChecked)) {
                    if (adjacentCity is not in citiesAlreadyChecked) {
                           citiesToCheck.push(adjacentCity)
                    }
               }
          }
    }
    return false  
   //transitive colsure of cities connected to c1 have been checked, and c2 was not found there.

}

グラフを二重にリンクして、|| を取り除くこともできます。で isDirectlyConnected。二重リンクの作成は、呼び出しによる構築中に行われます

m.put(c1、c2 を追加したセット) AND m.put(c2、c1 を追加したセット)

于 2011-02-17T12:13:25.047 に答える