如何使用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);
}
}
计算从源到所有邻接的距离
更新您的代码以使用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都是可能的其他转换函数。输入到?{