我知道这通常是广度优先的,但我们被要求两者都做,我已经做到了广度优先……
我觉得这是一个使用深度优先搜索的典型例子,所以我希望我能在这里得到一些帮助……我试图通过深度优先搜索找到迷宫中的最短路径,但到目前为止,我还不能确切地知道如何做到这一点。这是我到目前为止的代码:
void maze::findPathRecursive(graph &g, int position, int goal) {
if (position == goal) {
isPath = true; //returns true if there is a path to the goal
我已经设法找到了使用递归dfs的未加权图的最短路径。这就是这样一种尝试。
void dfsHelper(graph*& g, int start,int end, bool*& visited, int& min, int i) {
visited[start] = true;
i = i + 1;
if (start == end) {
if (i<=min) { min = i; }
}
node* current = g->adj[start];
while (current != NUL
我正在尝试用C++编写Dijkstra算法,在互联网上有无数的例子,但我似乎就是不能掌握这些例子是如何工作的。我更愿意以一种对我有意义的方式来做,这样我就可以更好地理解算法。我知道算法本身应该如何工作,并且我已经写了一些代码。我想知道是否有人能指出我思维过程中的缺陷。我选择将我的图表示为边列表。我将用伪代码编写,因为我的实际代码是一个巨大的混乱:
class Node{
vector<node> linkVector; //links to other nodes, generated at random
int cost;
我使用BFS来查看给定路径是否存在于图中:
static class Node{
int data;
Node next;
public Node(int data){
this.data = data;
}
}
//Adjency List to store the reference to head of each Node/Vertice
static class AdjList implements Iterable<Integer>{
Node head;
public void add(int to){
我的算法
假设我有一个二维的实数数组。我从这个数组中的一个特定的单元格开始,其中包含一个特别大的数字。我想标记其他单元格中的哪个应该属于上述开始单元格。规则是这样的:如果我找到了从开始单元格到另一个单元格的步行方式,则另一个单元格属于开始单元格。我只能在牢房里上下走动。我只能从一个数字较高的牢房走到一个号码较低的牢房。下面是我从中心9开始的一个例子
我的伪算法是
function Step(cellNr):
foreach neighborNr in neighbors_of(cellNr):
if array_value(neighborNr) < a
我已经使用一组LatLon点的scipy.spatial Python库制作了一个Voronoi图,以查找每个点的邻居。然后,我发现Delaunay三角剖分会更有用,现在我可以使用这个算法很容易地找到每个点的“第一层”和“第二层”邻居:
def findNeighbors(delaunay):
"Returns a adjacency list of the graph"
neighbors = defaultdict(set)
for simplex in delaunay.simplices:
for vertice in simp
我在寻找一种算法,它告诉我在点A和点B之间是否存在一条路径。我不需要知道路径到底是什么,我只需要知道它是否存在,执行时间是关键。基本网格要么有空的字段,要么有墙壁,只有这两个。你们能提点建议吗?
编辑:我想我应该澄清一下。我所拥有的是这样的基本网格:
O O O X O
O O O X X
O O O X O
O O X X O
O O O X O
其中O-空空间,X-墙,起点A(0,0)和结束B(4,4).我要做的是检查有多少次我可以拆除一堵墙的路径存在,终点是可达的。
适用于下列模式:
class Entity(models.Model):
name = models.CharField(max_length=256)
class Entry(models.Model):
""" A <subj> has a <connection> to an <obj>
"""
subj = models.ForeignKey(Entity, related_name='subject')
connection = models.