Java 网络/树模拟在一定数量的节点后进入无限循环

Question

我希望有人可以帮助解决我遇到的问题。首先，我尝试删除尽可能多的不会导致问题的代码。

我的问题是这样的:当我运行程序时，一切都运行得很好，直到我创建了一个包含大约 130 个节点的图。一旦达到 130 多个节点，程序就会无限循环地运行。

我尝试在 15 处运行 135 个节点的程序，以获得所需的图形密度。

为了提供一些背景信息，我正在研究模拟，为此我正在创建随机图并使用 BFS 构建生成树。

我的问题出现在创建生成树的过程中。

复制并粘贴代码，并使用 javac MMB.java 进行编译，全部放在一个文件中。

import java.util.*;

/**
 *  Custom type Set used to differentiate nodes in the FAST and SLOW sets
*/
enum Set {
    FAST, SLOW;
}

/**
 *  Custom node class used to store our spanning tree
*/
class Node<T> {

    private T data;
    private Node<T> parent;
    private List<Node<T>> children;
    private int level;
    private int rank;
    private Set set;

    // constructor for root Nodes and stand alone nodes
    public Node(T data){
        this.data = data;
        this.parent = null;
        this.level = 0;
        this.rank = Integer.MIN_VALUE;
        this.children = new ArrayList<Node<T>>();
    }

    // constructor for all non root nodes
    public Node(T data, Node<T> parent){
        this.data = data;
        this.setParent(parent);
        this.level = (parent.getLevel()) + 1;
        this.rank = Integer.MIN_VALUE;
        this.children = new ArrayList<Node<T>>();
    }

    // get data
    public T getData(){
        return this.data;
    }

    // set data
    public void setData(T data){
        this.data = data;
    }

    // add child node
    public void addChild(Node<T> child){
        children.add(child);
    }

    // remove child node
    public void removeChild(Node<T> child){
        children.remove(child);
    }

    // get rank
    public int getRank(){
        return this.rank;
    }

    // set rank
    public void setRank(int rank){
        this.rank = rank;
    }

    // get parent
    public Node<T> getParent(){
        return this.parent;
    }

    // set parent - updates parent node to have child
    public void setParent(Node<T> parent){
        this.parent = parent;
        parent.addChild(this);
    }

    // returns level of a Node
    public int getLevel(){
        return this.level;
    }

    // returns a list of children of a given node
    public List<Node<T>> getChildren(){
        return this.children;
    }

    // set the Set a node is in
    public void setSet(Set set){
        this.set = set;
    }

    // get the Set a node is in
    public Set getSet(){
        return this.set;
    }

    // returns the tree as a list of nodes using DFS traversal
    public List<Node<T>> treeToList(){
        List<Node<T>> list = new LinkedList<Node<T>>();
        List<Node<T>> visitedNodes = new LinkedList<Node<T>>();

        list.add(this);
        while(list.size() > 0){
            Node<T> currentNode = list.get(list.size() - 1);
            List<Node<T>> currentNodesChildren = currentNode.getChildren();
            if(!visitedNodes.contains(currentNode)){
                for(Node<T> n : currentNodesChildren){
                    list.add(n);
                }
                visitedNodes.add(currentNode);
            }
            else {
                list.remove(currentNode);
            }
        }
        return visitedNodes;
    }

    // returns the number of levels in the tree
    // Note: levels start at 0
    public int numberOfLevels(){
        List<Node<T>> list = this.treeToList();
        int maxLevel = 0;
        for(Node<T> n : list)
            if(n.getLevel() > maxLevel)
                maxLevel = n.getLevel();
        return maxLevel + 1;
    }

    // returns the max rank in the tree
    public int maxRank(){
        List<Node<T>> list = this.treeToList();
        int maxRank = 0;
        for(Node<T> n : list)
            if(n.getRank() > maxRank)
                maxRank = n.getRank();
        return maxRank;
    }

    // returns a list of nodes with a given rank and level in the FAST set
    public List<Node<T>> nodeRankLevelSubset(int rank, int level){
        List<Node<T>> list = this.treeToList();
        List<Node<T>> subset = new LinkedList<Node<T>>();
        for(Node<T> n : list)
            if(n.getRank() == rank && n.getLevel() == level && n.getSet() == Set.FAST)
                subset.add(n);
        return subset;
    }

    // Print All
    public void printAll(){
        List<Node<T>> list = this.treeToList();
        for(Node<T> n : list){
            System.out.println("{");
            System.out.println(" \"data\": " + n.getData() + ",");
            System.out.println(" \"level\": " + n.getLevel() + ",");
            System.out.println(" \"rank\": " + n.getRank() + ",");
            switch(n.getSet()){
                case FAST:
                    System.out.println(" \"set\": \"FAST\"");
                    break;
                case SLOW:
                    System.out.println(" \"set\": \"SLOW\"");
                    break;
            }
            System.out.print(" \"parent\": ");
            if(n.getParent() != null)
                System.out.println(n.getParent().getData() + ",");
            else
                System.out.println(" ,");
            System.out.print(" \"children\": [");
            for(Node<T> cn : n.getChildren()){
                System.out.print(cn.getData() + ",");
            }
            System.out.println("]\n}");
        }
    }
    // BFS to print
    public void printTree(){
        List<Node<T>> discoveredNodes = new LinkedList<Node<T>>();
        List<Node<T>> queue = new LinkedList<Node<T>>();
        List<Node<T>> children;
        Node<T> currentNode;
        queue.add(this);
        discoveredNodes.add(this);
        while(queue.size() > 0){
            currentNode = queue.remove(0);
            children = currentNode.getChildren();
            System.out.print("\n" + currentNode.getData() + ": ");
            for(Node<T> n : children){
                queue.add(n);
                discoveredNodes.add(n);
                System.out.print(n.getData() + " " + " Rank: " + n.getRank() + " ");
            }
        }
        System.out.print("\n");
    }
}

public class MMB {
    // boolean 2D array used to make the edges in a random graph
    public static boolean[][] randomGraph;
    // custom Node class used to store our BFS spanning tree
    public static Node<Integer> spanningTree;

    public static void main(String[] args){
        int numberOfNodes, graphDensity;

        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the desired number of Nodes: ");
        numberOfNodes = scanner.nextInt();
        System.out.print("Enter the desired graph density: ");
        graphDensity = scanner.nextInt();

        randomGraph = randomGraph(numberOfNodes, graphDensity);

        /* Print Out Graph */
        for(int i = 0; i < randomGraph.length; i++){
            System.out.print(i + " ");
            for(int j = 0; j < randomGraph.length; j++){
                System.out.printf(" " + randomGraph[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("");
        System.out.println("HERE - CREATED GRAPH");
        spanningTree = spanningTree(0);
        System.out.println("HERE - CREATED SPAnnING TREE");
        // rankNodes(spanningTree, spanningTree.numberOfLevels());
        // System.out.println("HERE - FIRST RANK");
        // determineSet(spanningTree);
        // System.out.println("HERE - DETERMINE SET");
        // //spanningTree.printTree();
        // reRankNodes(spanningTree);
        // System.out.println("HERE - RERANK NODES");
        // //spanningTree.printTree();
        // spanningTree.printAll();
    }


    /**
     *  Create an undirected graph at random
     *  A 2D boolean array will represent the edges between nodes
     *  @param  numberOfNodes   number of nodes in the graph
     *  @param  graphDensity    integer percentage of graph density
    */
    public static boolean[][] randomGraph(int numberOfNodes, int graphDensity){
        boolean[][] graph = new boolean[numberOfNodes][numberOfNodes];
        Random randomNumber = new Random();

        boolean hasEdge;
        for(int i = 0; i < numberOfNodes; i++){
            hasEdge = false;
            for(int j = 0; j < numberOfNodes; j++){
                // i != j ensures no loops
                if(i != j && (randomNumber.nextInt(100) + 1) < graphDensity){
                    graph[i][j] = true;
                    graph[j][i] = true;
                    hasEdge = true;
                }
            }
            // to ensure no disconnected nodes, keep track with hasEdge
            // if no edge exists create a random one
            int randomNum;
            while(!hasEdge){
                if((randomNum = randomNumber.nextInt(numberOfNodes)) != i){
                    graph[i][randomNum] = true;
                    graph[randomNum][i] = true;
                    hasEdge = true;
                }
            }
        }
        return graph;
    }


    /**
     *  Create a Spanning Tree from an undirected graph using BFS
     *  A custom Node structure will represent our spanning tree
     *  @param  root    root of undirected graph from 0 to numberOfNodes-1
    */
    public static Node<Integer> spanningTree(int root){
        Node<Integer> tree = new Node<Integer>(root);
        Node<Integer> currentNode;
        Integer currentNodeData;

        LinkedList<Node<Integer>> discoveredNodes = new LinkedList<Node<Integer>>();
        LinkedList<Node<Integer>> queue = new LinkedList<Node<Integer>>();

        queue.add(tree);
        discoveredNodes.add(tree);
        while(queue.size() > 0){
            currentNode = queue.removeFirst();
            currentNodeData = currentNode.getData();
            for(int i = 0; i < randomGraph.length; i++){
                if(randomGraph[currentNodeData][i] && !listContainsNode(discoveredNodes, i)){
                    Node<Integer> newNode = new Node<Integer>(i, currentNode);
                    queue.add(newNode);
                    discoveredNodes.add(newNode);
                }
            }
        }
        return tree;
    }

    /* Helper Methods */
    // search a list of Nodes for a value
    public static boolean listContainsNode(List<Node<Integer>> list, Integer data){
        for(Node<Integer> n : list)
            if(n.getData() == data)
                return true;
        return false;
    }
}

Answer 1

在尾部

/* Helper Methods */
// search a list of Nodes for a value
public static boolean listContainsNode(List<Node<Integer>> list, Integer data){
    for(Node<Integer> n : list)
        if(n.getData() == data)  // <-- Can you spot the bug?
            return true;
    return false;
}

问题在于您将Integer 与== 进行比较。对于低于 128 的数字，它可以工作，因为整数被保留，但对象上的比较不再工作。

只需使用:

if (n.getData().equals(data))

比较节点内容(并继续编写出色的代码；) - 在 StackOverflow 的问题中看到这样的质量并不容易)