Как вычислить расстояние до всех остальных вершин в Graph с помощью BFS? - PullRequest
Новая
       66

Как вычислить расстояние до всех остальных вершин в Graph с помощью BFS?

0 голосов
/ 07 мая 2020

Как мне вычислить расстояние от начальной вершины до всех остальных вершин с помощью поиска BFS? Если пути к вершине нет, то расстояние должно быть указано как -1. У меня есть класс, который генерирует Graph и метод distance(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 Ответ

1 голос
/ 07 мая 2020

Расчет расстояния от источника до всех смежностей

Обновите свой код, чтобы использовать 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;
        }
...