0

私は友達を見つけるための最短経路を見つけようとしています。人 X が人 Y に接続したい場合、X が Y に到達するための友達の最短経路を出力したいと思います。コードを実行するたびに、結果として null が返されます。

public void shortest(String first, String target){

    HashMap<String, String> prev = new HashMap<String, String>();
    Queue<PersonNode> q = new LinkedList<PersonNode>();
    PersonNode firstPerson = hash.get(first);

    firstPerson.visited = true;
    prev.put(first, first + " ");
    q.add(firstPerson);

    while(!q.isEmpty()){    
        PersonNode curr = q.remove();

        if(!curr.visited){
            curr.visited = true;
            if(curr.equals(target)){
                break;
            }
            else{
                for(int i =0; i < curr.list.size(); i++){
                    if(curr.list.get(i).visited = false){
                        q.add(curr.list.get(i));
                        curr.list.get(i).visited = true;
                        prev.put(curr.list.get(i).name, prev.get(curr.list.get(i).name) + curr.list.get(i));

                    }
                }

            }
            if(!curr.equals(target)){
                System.out.println("They have no connections");
            }

        }
    }
    System.out.println(prev.get(target));
}
4

1 に答える 1

0

コードをデバッグしてみてください。ループの外側に設定されているようですfirstperson.visited。true次に、キューからポップして無視しますtrue。ループ内でも同じです。すべての訪問済み属性を true に設定すると、実行時にキューからポップされたときに無視されます

また、「接続がありません」という部分は while ループ内にあってはならないと考えています

于 2012-12-08T11:13:25.717 に答える