java - 计算 AdjacencyMatrix 中节点之间的距离

Question

我已经在java中实现了AdjacencyMatrix，但是我很难实现distance()方法来找到两个节点之间的距离。知道我该怎么做吗？我尝试了很多方法，但似乎无法得到正确的答案。

这是我的实现

public class AdjacencyMatrix implements Representation {
private Node[] nodes;
private int[][] adjacencyMatrix;
private int numberOfNodes =0;


public AdjacencyMatrix(File file) {

    Scanner inFile;
    int numNodes;
    try {
        inFile = new Scanner(file);
        numNodes = Integer.parseInt(inFile.nextLine());

        adjacencyMatrix = new int[20][20];

        nodes = new Node[20];
        String[] line;

        while (inFile.hasNextLine()) {
            line = inFile.nextLine().split(":");
            Node from = new Node(Integer.parseInt(line[0]));
            Node to = new Node(Integer.parseInt(line[1]));
            int value = Integer.parseInt(line[2]);

            if(!Arrays.asList(nodes).contains(from))
                addNode(from);
            if(!Arrays.asList(nodes).contains(to))
                addNode(to);


            addEdge(new Edge(from, to, value));

        }


    } catch (FileNotFoundException e) {
        System.out.print(e.getCause());
    }
}
public AdjacencyMatrix() {

}

@Override
public boolean adjacent(Node x, Node y) {
    int fromIndex = findIndex(x);
    int toIndex = findIndex(y);

    if(adjacencyMatrix[fromIndex][toIndex] == 1 || adjacencyMatrix[toIndex][fromIndex] ==1){
        return true;
    }
    return false;
}

@Override
public List<Node> neighbors(Node x) {
    ArrayList<Node> neighbors = new ArrayList<>();
    int fromIndex = findIndex(x);
    if(x.getData().toString().equals("4")) {
        System.out.println("FromIndex is: " + fromIndex);
    }

    if(x.getData().toString().equals("4")){
        for(int i =0; i < nodes.length; ++i){

            System.out.println(nodes[i] + " ");
        }
    }

     for (int i = 0; i <= numberOfNodes; i++){
        if(adjacencyMatrix[fromIndex][i] == 1){

                neighbors.add(nodes[i]);
                if(x.getData().toString().equals("4")) {
                System.out.println("Match!: " + i);
                System.out.println("Adding NODE: " + nodes[i]);
            }
        }

    }

    int [] nums = new int[neighbors.size()];
    for(int i =0; i < nums.length; ++i){
        nums[i] = Integer.parseInt(neighbors.get(i).getData().toString());
    }
    Arrays.sort(nums);
    ArrayList<Node> newNeighbors = new ArrayList<>();
    for(int i =0; i < nums.length; ++i){
        newNeighbors.add(new Node(nums[i]));
    }
    return newNeighbors;
}

@Override
public boolean addNode(Node x) {
    if(Arrays.asList(nodes).contains(x)){
        return false;
    }


    nodes[numberOfNodes] = x;

    for (int i = 0; i <= numberOfNodes; i++){

        adjacencyMatrix[numberOfNodes][i] = 0;
        adjacencyMatrix[i][numberOfNodes] = 0;
    }
    numberOfNodes++;
    return true;
}

@Override
public boolean removeNode(Node x) {

    if (!Arrays.asList(nodes).contains(x)) {
        return false;
    }
    for (int k = 0; k < numberOfNodes; k++) {
        if (x.equals(nodes[k])) {

            //decrement the number of nodes
            numberOfNodes--;

            for (int i = k; i < numberOfNodes; i++) {
                nodes[i] = nodes[i + 1];
            }

            for (int i = k; i < numberOfNodes; i++) {
                for (int j = 0; j <= numberOfNodes; j++) {
                    adjacencyMatrix[i][j] = adjacencyMatrix[i + 1][j];
                }
            }

            for (int i = k; i < numberOfNodes; i++) {
                for (int j = 0; j < numberOfNodes; j++) {
                    adjacencyMatrix[j][i] = adjacencyMatrix[j][i + 1];
                }
            }
        }

        //

    }
    return true;
}


@Override
public boolean addEdge(Edge x){

    int from = Integer.parseInt(x.getFrom().getData().toString());
    int to = Integer.parseInt(x.getTo().getData().toString());
    int fromIndex = findIndex(x.getFrom());
    int toIndex = findIndex(x.getTo());

    if(from == 4){
        System.out.println("Adding adjecent to 4 -> " + to);

    }
    if(adjacencyMatrix[fromIndex][toIndex] == 1 ){
        return false;
    }

    adjacencyMatrix[fromIndex][toIndex] = 1;
    return true;
}

@Override
public boolean removeEdge(Edge x) {
    int from = Integer.parseInt(x.getFrom().getData().toString());
    int to = Integer.parseInt(x.getTo().getData().toString());
    int fromIndex = findIndex(x.getFrom());
    int toIndex = findIndex(x.getTo());

    if(adjacencyMatrix[fromIndex][toIndex] == 0 && adjacencyMatrix[toIndex][fromIndex] ==0){
        return false;
    }

    adjacencyMatrix[fromIndex][toIndex] = 0;
    return true;
}

@Override
public int distance(Node from, Node to) {
    return 0;
}


@Override
public Optional<Node> getNode(int index) {
    return null;
}

@Override
public Collection<Node> getNodes() {

    return Arrays.asList(nodes);
}

public int findIndex(Node node)
{
    for (int i = 0; i < numberOfNodes; ++i)
        if (nodes[i].equals(node))
            return i;
    return -1;
}}

除了 distance() 之外，我的所有方法都有效。我在 distance() 方法中返回 0，因为我不知道如何正确实现它。任何帮助将不胜感激。

Answer 1

我明白了。基本上我做了一个数组来跟踪我的边缘:

private Edge [] edges;

然后我用图形边缘填充数组。现在，在我的距离方法中，我只需找到给定“To”和“From”节点的边缘，并提取它的值，这就是我正在寻找的距离:)

public int distance(Node from, Node to) {

    for(Edge edge: edges){
        if(edge.getFrom().equals(from) && edge.getTo().equals(to)){
            return edge.getValue();
        }
    }
    return 1;
}

我一定早就想到了这个简单的解决方案!