1

我目前正在编写一个程序，该程序获取节点图并返回特征路径长度（从一个节点到每个其他节点的路径长度平均然后为每个节点重复并再次平均）。我已经完成了所有其他工作，但我不确定如何实现节点的深度优先搜索以找到从一个节点到另一个节点的最短路径。这就是我到目前为止所拥有的。

        int dist = 0;
        List<Node> path = new ArrayList<Node>();
        List<Node> shrtPath = new ArrayList<Node>();
        Node curNode = rtNode;
        if (rtNode == goalNode) {
            return dist;
        }
        path.add(curNode);
        for (int l = 0; l < rtNode.connections.size(); l++) {
            Node tempNode = new Node();
            curNode = rtNode.connections.get(l);
            for (int i = 0; i < curNode.connections.size(); i++) {
                tempNode = curNode.connections.get(i);
                path.add(tempNode);
                if (curNode.connections.get(i) == goalNode) {
                    if (path.size() < shrtPath.size()) {
                        shrtPath.clear();
                        shrtPath = path;
                    }
                }
            }
        }
        dist = shrtPath.size();
        return dist;

我知道这是不完整的，但我不确定从这里去哪里，或者我是否朝着正确的方向前进。我知道我需要能够搜索根节点及其连接，但我不确定如何遍历连接的连接等等。我也意识到我必须标记访问的节点，因为我的 Node 类中有一个布尔值，因为我还没有实现它。这也是我的 Node 类。

import java.util.ArrayList;
import java.util.List;



public class Node {

    List <Node> connections = new ArrayList<Node>();
    int cons = 0;
    boolean hub;
    boolean visited = false;

    public Node() {
        hub = false;

    }

    public void setNbs(Node nb1, Node nb2) {
        connections.add(nb1);
        connections.add(nb2);
    }

    public boolean addExtraCon(Node con) {
        for (int i = 0; i < connections.size(); i++) {
            if(connections.get(i) == con) {
                return false;
            }
        }
        connections.add(con);
        return true;
    }

    public boolean makeHub() {
        hub = true;
        return hub;
    }

    public int numberOfConnections() {
        cons = connections.size();
        return cons;
    }

    public boolean isHub() {
        if (hub == true) {
            return true;
        }
        return false;
    }

}

我希望这有助于任何和所有的帮助，非常感谢。提前致谢。

4

0 回答 0