-2

Java を使用して BFS を実装しようとしています。この質問からコードを取得し、次のように変更しました。

格納する文字列型をオブジェクト型に変更します。機能していません。文字列であれば動作します。理由を教えてもらえますか？

私のコードを以下に示します。

package bfs;

import java.util.*;

/**
 *
 * @author Harikrishnan
 */
public class BFS {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Search.execute();
    }

}

class Graph {
    private Map <Node, LinkedHashSet<Node>> map = new HashMap();

    public void addEdge(Node node1, Node node2) {
        LinkedHashSet<Node> adjacent = map.get(node1);
        if(adjacent==null) {
            adjacent = new LinkedHashSet();
            map.put(node1, adjacent);
        }
        adjacent.add(node2);
    }

    public void addTwoWayVertex(Node node1, Node node2) {
        addEdge(node1, node2);
        addEdge(node2, node1);
    }

    public boolean isConnected(Node node1, Node node2) {
        Set adjacent = map.get(node1);
        if(adjacent==null) {
            return false;
        }
        return adjacent.contains(node2);
    }

    public LinkedList<Node> adjacentNodes(Node last) {
        LinkedHashSet<Node> adjacent = map.get(last);
        if(adjacent==null) {
            return new LinkedList();
        }
        return new LinkedList<Node>(adjacent);
    }
}


class Search {

    private static final Node START = new Node("1");
    private static final Node END = new Node("4");

    public static void execute() {
        // this graph is directional
        Graph graph = new Graph();
        graph.addEdge(new Node("1"), new Node( "2"));
        graph.addEdge(new Node("2"), new Node( "1"));
        graph.addEdge(new Node("2"), new Node( "3"));
        graph.addEdge(new Node("2"), new Node( "4"));
        graph.addEdge(new Node("2"), new Node( "7"));
        graph.addEdge(new Node("3"), new Node("5"));
        graph.addEdge(new Node("3"), new Node( "6"));
        graph.addEdge(new Node("3"), new Node( "2"));
        graph.addEdge(new Node("4"), new Node( "2"));
        graph.addEdge(new Node("4"), new Node( "7"));
        graph.addEdge(new Node("4"), new Node( "8"));
        graph.addEdge(new Node("5"), new Node( "3"));
        graph.addEdge(new Node("5"), new Node( "6"));
        graph.addEdge(new Node("5"), new Node("9"));
        graph.addEdge(new Node("6"), new Node( "3"));
        graph.addEdge(new Node("6"), new Node("7"));
        graph.addEdge(new Node("6"), new Node("5"));
        graph.addEdge(new Node("6"), new Node("9"));
        graph.addEdge(new Node("7"), new Node("2"));
        graph.addEdge(new Node("7"), new Node("6"));
        graph.addEdge(new Node("7"), new Node("8"));
        graph.addEdge(new Node("7"), new Node("10"));
        graph.addEdge(new Node("8"), new Node("4"));
        graph.addEdge(new Node("8"), new Node("7"));
        graph.addEdge(new Node("8"), new Node("10"));
        graph.addEdge(new Node("9"), new Node("5"));
        graph.addEdge(new Node("9"), new Node("6"));
        graph.addEdge(new Node("9"), new Node("10"));
        graph.addEdge(new Node("10"), new Node( "9"));
        graph.addEdge(new Node("10"), new Node("7"));
        graph.addEdge(new Node("10"), new Node("8"));
        LinkedList<Node> visited = new LinkedList();
        visited.add(START);
        new Search().breadthFirst(graph, visited);
    }

    private void breadthFirst(Graph graph, LinkedList<Node> visited) {
        LinkedList<Node> nodes = graph.adjacentNodes(visited.getLast());
        // examine adjacent nodes
        for (Node node : nodes) {
            if (visited.contains(node)) {
                continue;
            }
            if (node.equals(END)) {
                visited.add(node);
                printPath(visited);
                visited.removeLast();
                break;
            }
        }
        // in breadth-first, recursion needs to come after visiting adjacent nodes
        for (Node node : nodes) {
            if (visited.contains(node) || node.equals(END)) {
                continue;
            }
            visited.addLast(node);
            breadthFirst(graph, visited);
            visited.removeLast();
        }
    }

    private void printPath(LinkedList<Node> visited) {
        for (Node node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println();
    }
}

class Node
{
    public String name;
    public int x;
    public int y;

    public Node(String name)
    {
        this.name = name;
    }

    @Override
    public String toString()
    {
        return name;
    }

    @Override
    public boolean equals(Object n)
    {
        return ((Node)n).name.equals(name);
    }
}
4

1 に答える 1

0

あなたのコードは私を少し混乱させるので、私がそれをどうするか見てみましょう...

まず、すでに完全に優れた検索インスタンスがあるのに、なぜ新しい検索インスタンスを作成するのですか? コンストラクタをexecute()作成します。に変更new Search().execute()しますexecute()。

第二に、同じ数の新しいノードを作成したり、同じノードを再利用したりするつもりですか?すべてをリンクして解析します。ルートノードをどこにも含めないでください。

これが意図したものである場合は、ご容赦ください。私が言ったように、あなたのコードは私を混乱させます。

于 2012-12-14T14:01:50.417 に答える