实现广度优先搜索算法时出现内存不足错误

Question

我收到以下错误：

[error][1] (E/DartVM  (14988): Exhausted heap space, trying to allocate 536870928 bytes.
E/flutter (14988): [ERROR:flutter/lib/ui/ui_dart_state.cc(148)] Unhandled Exception: Out of Memory)

尝试实现breadth_first搜索算法以查找图形中的最短路径时。我找到了用 C# 编写的算法，我正在尝试用 dart/flutter 重写它。

可以在此处找到 C# 中的原始代码。

我的飞镖代码：

import 'dart:collection';
import 'package:stack/stack.dart';
class Node<T>{
int id;
Node(this.id);
String toString() => '$id';
}
class Graph<T>{
final Map<Node, List<Node>> adj;
Graph(this.adj);
void AddEdge(Node node1,Node node2){
if(!adj.containsKey(node1))
adj[node1]=List<Node>();
if(!adj.containsKey(node2))
adj[node2]=List<Node>();
adj[node1].add(node2);
adj[node2].add(node1);
}
Stack<Node> ShortestPath(Node source, Node dest){
var path=Map<Node<T>,Node<T>>();
var distance=Map<Node<T>,int>();
//adj.keys.forEach(( node) => distance[node]=-1);
for(var node in adj.keys){
distance[node]=-1;
}
distance[source]=0;
var q=Queue<Node<T>>();
q.add(source);
while(q.isNotEmpty){
var node=q.removeFirst();
for(var adjs in adj[node].where((n) => distance[n]==-1)){
distance[adjs]=distance[node]+1;
path[adjs]=node;
q.add(adjs);
}
}
var res=Stack<Node>();
var cur=dest;
while(cur != res){
res.push(cur);
cur=path[cur];
}
res.push(source);
return res;
}
}
void main() {
var g = new Graph({});
var n1 = new Node<int>(1);
var n2 = new Node<int>(2);
var n3 = new Node<int>(3);
var n4 = new Node<int>(4);
var n5 = new Node<int>(5);
var n6 = new Node<int>(6);
var n7 = new Node<int>(7);
g.AddEdge(n1, n2);
g.AddEdge(n1, n3);
g.AddEdge(n1, n4);
g.AddEdge(n4, n5);
g.AddEdge(n2, n6);
g.AddEdge(n4, n7);
g.AddEdge(n5, n6);
g.AddEdge(n6, n7);
var answ=g.ShortestPath(n1, n7);
print(answ);
}

那么我的程序有什么问题，如果有人知道更好的方法来找到图中的最短路径以在 dart 中使用它，那就太好了。

提前致谢

Answer 1

首先，您的主要问题是根据 C# 实现，您的 while 循环不正确：

var res=Stack<Node>();
var cur=dest;
while(cur != res){
res.push(cur);
cur=path[cur];
}
res.push(source);
return res;

这个循环永远不会完成 res 和 cur 是完全不同的类型，其中cur是Node，res是Stack。如果检查 C# 实现，可以看到这是不正确的：

var res = new Stack<Node<T>>();
var cur = dest;
while(cur != source) {
res.Push(cur);
cur = path[cur];
}
res.Push(source);
return res;

所以我认为通过与source进行比较，它将正确解决问题。但是在你的代码中有很多小问题，其中类型不是很好，你可以通过在更多的地方使用泛型来使其更加类型安全。

因此，我为您的代码添加了更多键入信息(我需要这样做才能捕获类型错误(。我也放弃了Stack类的使用，因为我认为它没有多大意义。此外，您获得的Stack类没有toString实现，因此我只是认为仅使用List并返回结果更容易：

import 'dart:collection';
class Node<T> {
int id;
Node(this.id);
@override
String toString() => '$id';
}
class Graph<T> {
final Map<Node<T>, List<Node<T>>> adj;
Graph(this.adj);
void AddEdge(Node<T> node1, Node<T> node2) {
if (!adj.containsKey(node1)) adj[node1] = <Node<T>>[];
if (!adj.containsKey(node2)) adj[node2] = <Node<T>>[];
adj[node1].add(node2);
adj[node2].add(node1);
}
List<Node<T>> ShortestPath(Node<T> source, Node<T> dest) {
final path = <Node<T>, Node<T>>{};
final distance = <Node<T>, int>{};
//adj.keys.forEach(( node) => distance[node]=-1);
for (final node in adj.keys) {
distance[node] = -1;
}
distance[source] = 0;
final q = Queue<Node<T>>();
q.add(source);
while (q.isNotEmpty) {
final node = q.removeFirst();
for (final adjs in adj[node].where((n) => distance[n] == -1)) {
distance[adjs] = distance[node] + 1;
path[adjs] = node;
q.add(adjs);
}
}
final res = <Node<T>>[];
var cur = dest;
while (cur != source) {
res.add(cur);
cur = path[cur];
}
res.add(source);
return res;
}
}
void main() {
final g = Graph<int>({});
final n1 = Node<int>(1);
final n2 = Node<int>(2);
final n3 = Node<int>(3);
final n4 = Node<int>(4);
final n5 = Node<int>(5);
final n6 = Node<int>(6);
final n7 = Node<int>(7);
g.AddEdge(n1, n2);
g.AddEdge(n1, n3);
g.AddEdge(n1, n4);
g.AddEdge(n4, n5);
g.AddEdge(n2, n6);
g.AddEdge(n4, n7);
g.AddEdge(n5, n6);
g.AddEdge(n6, n7);
final answ = g.ShortestPath(n1, n7);
print(answ); // [7, 4, 1]
}