计算广度优先搜索中遍历的边数？ [英] Counting the number of edges traversed in a Breadth First Search?

问题描述

这是我的bfs算法。我想存储遍历在字段边缘的边数，但我无法确定将变量放在哪里为每个边添加一个。我总是得到太长的答案，所以我认为这比简单地增加边缘更难。

This is my bfs algorithim. I want to store the number of edges i traversed in the field edges, but I can't figure out where to place the variable to add one for each edge. I keep getting answers that are too long, so i think this is harder than simply incrementing edge.

应该注意的是，这应该计算沿着真实的边缘只有路径，而不是额外的边缘。

It should be noted that this is supposed to calculate the edges along the true path only, not the extra edges.

public int distance(Vertex x, Vertex y){
        Queue<Vertex> search = new LinkedList<Vertex>();
        search.add(x);
        x.visited = true;
        while(!search.isEmpty()){
            Vertex t = search.poll();
            if(t == y){
                return edges;
            }
            for(Vertex n: t.neighbours){
                if(!n.visited){
                    n.visited = true;
                    search.add(n);
                }

            }
            System.out.println(search + " " + t);
        }
        return edges;   
    }

欢迎任何和所有帮助。如果您需要更多课程/方法请告诉我

Any and all help is appreciated. if you require more classes/methods let me know

编辑

import java.util.ArrayList;

public class Vertex {

    public static char currentID = 'a';
    protected ArrayList<Vertex> neighbours;
    protected char id;
    protected boolean visited = false;
    protected Vertex cameFrom = null;
    public Vertex(){
        neighbours = new ArrayList<Vertex>();
        id = currentID;
        currentID++;
        Graph.all.add(this);
    }
    public void addNeighbour(Vertex x){
        int a;
        while(x == this){
             a = (int) (Math.random()*(Graph.all.size()));
             x = Graph.all.get(a);
        }           
            if(!(neighbours.contains(x))){
                neighbours.add(x);
                x.addNeighbour(this);
                //System.out.println(this + " Linking to " + x);
            }
    }
    public void printNeighbours(){
        System.out.println("The neighbours of: " + id + " are: " + neighbours);
    }
    public String toString(){
        return id + "";
    }

}

推荐答案

在 Vertex 类中，创建一个 Vertex cameFrom 字段，您设置该字段指向 Vertex 您来自访问该节点的时间。您甚至可以用此替换布尔访问字段（如果它是 null Vertex 尚未访问过。）

In your Vertex class, create a Vertex cameFrom field which you set to point to the Vertex you came from when that node was visited. You could even replace your boolean visited field with this (if it is null the Vertex hasn't been visited yet).

然后，当你找到 Vertex y 只需按照指针返回 Vertex x 计算你走的步数。

Then, when you find the Vertex y just follow the pointers back to Vertex x counting how many steps it takes as you go.

如果你不喜欢我想更改您的 Vertex 类，然后在搜索过程中保留一个 Map< Vertex，Vertex> 从您访问的顶点到您来自的顶点的映射。当你到达终点时，你可以按照相同的方式跟随开头的路径。

If you don't want to change your Vertex class, then just keep a Map<Vertex,Vertex> during your search which stores the mappings from the vertex you're visiting to the vertex you came from. When you get to the end you can follow the path to the beginning in the same way.

沿着这些方向的某些东西也许：

Something along these lines perhaps:

    public int distance(Vertex x, Vertex y){
        Queue<Vertex> search = new LinkedList<Vertex>();
        search.add(x);
        while(!search.isEmpty()){
            Vertex t = search.poll();
            if(t == y){
                return pathLength( t );
            }
            for(Vertex n: t.neighbours){
                if(n.cameFrom == null || n != x){
                    n.cameFrom = t;
                    search.add(n);
                }

            }
            System.out.println(search + " " + t);
        }
        return -1;  
    }

    public int pathLength( Vertex v )
    {
       int path = 0;

       while ( v.cameFrom != null )
       {
         v = v.cameFrom;
         path++;
       }

       return path;
    }

这篇关于计算广度优先搜索中遍历的边数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！