当前位置: 首页 > 知识库问答 >
问题:

如何使用BFS计算到图中所有其他顶点的距离?

毛弘博
2023-03-14

如何使用BFS搜索计算从开始顶点到所有其他顶点的距离?如果没有到顶点的路径,那么距离应该报告为-1。我有一个类,它生成一个<代码>图形和一个方法<代码>距离(int start),我已经实现了BFS搜索,但是我不知道如何计算距离并以合适的数据结构返回它。

预期产出:

graph.distance(0);
>>> Distance from vertex 0 to 1 is 1
>>> Distance from vertex 0 to 2 is 1
>>> Distance from vertex 0 to 3 is 2
>>> Distance from vertex 0 to 4 is 2
>>> Distance from vertex 0 to 5 is 3
import java.util.*;
import static java.lang.System.out;
import java.util.concurrent.ThreadLocalRandom; 


public class Graph {
    int _vertices;
    ArrayList<ArrayList<Integer>> adj_list;

    private void addEdge(int u, int v) {
        adj_list.get(u).add(v);
        adj_list.get(v).add(u); 
        //out.println(adj_list);
    }

    /*
     * loop through all pairs of vertices u, v and decide, 
     * randomly with probability p, whether the edge (u, v) 
     * is in the graph.
     */

    Graph(int vertices, double prob){
        _vertices = vertices;
        adj_list = new ArrayList<ArrayList<Integer>>(vertices);
        for (int u = 0; u < vertices; u++) {
            //System.out.println(i);
            adj_list.add(new ArrayList<Integer>());
        }
        for (int v = 0; v < vertices; v++) {
            for(int u = 0; u < vertices; u++) {
                double random = ThreadLocalRandom.current().nextDouble(0, 1);
                if (random > prob) {
                    //System.out.println(checkElem(adj_list, v));
                    if (checkElem(adj_list, v, u) == false && u != v){
                        addEdge(v, u);
                    }
                }
            }
        }
    }

    public void printGraph() { 

        for (int i = 0; i < adj_list.size(); i++) { 
            System.out.println("\nAdjacency list of vertex " + i); 
            for (int j = 0; j < adj_list.get(i).size(); j++) { 
                System.out.print(" -> "+adj_list.get(i).get(j)); 
            } 
            System.out.println(); 
        } 
    }

    /*
     * @param vert: A vertex in the graph
     */
    public void printVertex(int vert) {
        System.out.print(" -> "+adj_list.get(vert)); 
    }

    /*
     * @param arr: list of list that represents graph
     * @param vertex: a vertex in the graph
     * @param node: node to be checked in vertex
     */
    private boolean checkElem(ArrayList<ArrayList<Integer>> arr, int vertex, int node) {
        ArrayList<Integer> temp = arr.get(vertex);
        if(temp.contains(node)){
            return true;
        } else {
            return false;
        }
    }

    /*
     * @param start: A vertex to start the search from in the graph
     */
    public void distance(int start) {
        boolean visited[] = new boolean[_vertices];
        ArrayList<Integer> queue = new ArrayList<Integer>();

        visited[start] = true; 
        queue.add(start); 


        while (queue.size() != 0) { 
            //out.println(queue);

            // Dequeue a vertex from queue and print it             
            start = queue.remove(0);

            // Get all adjacent vertices of the dequeued vertex s 
            // If a adjacent has not been visited, then mark it 
            // visited and enqueue it 
            ArrayList<Integer> temp = adj_list.get(start);
            Iterator<Integer> i = temp.listIterator();

            //out.println("Vertex: " + start +" Dist: " + edgeDist);
            while (i.hasNext()) { 
                out.println(start);
                int n = i.next(); 


                if (!visited[n]) {  
                    visited[n] = true; 
                    queue.add(n);                 
                } 
            }   
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5, 0.5);
        graph.distance(0);
    }   
}

共有1个答案

董哲
2023-03-14

计算从源到所有邻接的距离

更新您的代码以使用isEmpty(),因为它是固定时间,并且不使用size()==0,请使用Queue添加相邻顶点

 public int distance(int vertex) {
            boolean visited[] = new boolean[_vertices];
            Queue<Integer> queue = new ArrayDeque<>();

            visited[vertex] = true;
            queue.add(vertex);

            int distance = 0;

            while (!queue.isEmpty()) {
                int v = queue.poll();

                List<Integer> adj = adj_list.get(v);
                distance++;
                for (Integer w : adj) {
                    if (!visited[w]) {
                        System.out.println("Distance from vertex: " + vertex + " to: " + w +" is " + distance);
                        visited[w] = true;
                        queue.add(w);
                    }
                }
            }
            return distance == 0 ? -1 : distance;
        }
 类似资料:
  • 我正在寻找一个算法,找到顶点的最小子集,这样从图中移除这个子集(以及连接这些顶点的边),所有其他顶点都变得不连通(即,图将没有任何边)。 null 我有图论的基础知识,所以请原谅任何不正确的地方。

  • 因此,如果我在一个图中有两个顶点,它们通过一个以上的边连接,而它们之间有相同的最短路径(即,如果我有节点a和节点B,它们直接通过三条边连接(它们之间有三条最短路径,每个距离为1),所以计数应该返回3)我该如何修改BFS算法来实现这一点?这是我的代码,它只计算2个节点之间的最短路径,而不计算这些最短路径的个数。

  • 我试图弄清楚,如何计算具有加权顶点的图的最短路径。经典算法,如Dijkstra和Floyd-WarMarshall,通常使用加权边,我看不到如何将它们应用于我的情况(加权顶点): 我的一个想法是将图形转换为带有加权边的更经典的视图。这是我收到的: 这里我们有单向和双向加权边,但我仍然不确定哪种算法可以处理这一点,以找到最短路径。

  • 我有一个图数据结构,它是我从本文中复制的-http://www.dreamincode.net/forums/topic/377473-graph-data-structure-tutorial/ 我想在上面实现BFS算法。我不完全确定如何--我看到/读到的大多数关于该算法的文章都使用了更简单的数据结构。该数据结构存储顶点的散列映射,并将其字符串表示形式作为键,然后还存储边的散列映射,使用整数作为

  • 本文向大家介绍Python程序,用于在图形中使用BFS查找可从节点到达的所有节点,包括了Python程序,用于在图形中使用BFS查找可从节点到达的所有节点的使用技巧和注意事项,需要的朋友参考一下 当需要查找树的所有节点的总和时,将创建一个类,该类包含设置根节点,向树中添加元素,搜索特定元素以及将树中的元素添加至的方法。找到总和,依此类推。可以创建该类的实例来访问和使用这些方法。 以下是相同的演示-

  • 我试图使用Scala类计算两点之间的距离。但它给出了一个错误说 类型不匹配;发现:其他。需要类型(具有基础类型点):?{def x:?}请注意,隐式转换不适用,因为它们是不明确的:在[A](x:A)类型的对象Predef中确保[A]的方法any2Ensuring和在[A](x:A)“ArroAssoc[A]类型的对象Predef中的方法Ani2ArrowasSoc都是可能的其他转换函数。输入到?{