小编Dom*_*tin的帖子

在图论中,最小距离(Dijkstra算法找到的)和最小路径(我不确定它是什么)之间的区别是什么？

我遇到了一个问题,我在图中给出了N个节点,这些节点相互连接,然后给出一个矩阵,列出一个连接到另一个节点的节点(如果是,则为1,否则为0).我想知道如何最好地解决这个问题.我认为这些是邻接矩阵？但是我该如何实现......

基本上我试图摆脱这些是找到一个特定节点是否连接到给定集合'S'中的所有其他节点.选择的项目是否是集团......

我会感激任何提示.

什么是Splay树,红黑树,AVL树,B树和T树？

我正在寻找好的实施方案.

给定n个节点在坐标平面上互连的图形,找到包含m个节点的最小距离子树的最佳方法是什么？

我发现这个问题的唯一解决方案是生成连接的所有节点组合,并尝试通过Kruskal或Prim的算法连接这些节点,而忽略其余的,然后比较所有创建的树并找到最小的树,但这当涉及到更大的树木时,效率并不高.

有更快,更有效的算法/方法吗？

我找到了一个前几次发布的解决方案，我试图将它应用到我的练习中，但它不起作用。我有一个包含节点和边的类图和一个提供节点的所有子节点的方法 childrenOf。所有这些工作正常。这是我的 DFS 搜索代码，我想找到所有路径：

def myDFS(graph,start,end,path=[]):
path=path+[start]
if start==end:
    return path
paths=[]
for node in graph.childrenOf(start):
    if node not in path:
        paths.extend(myDFS(graph,node,end,path))            
return paths

我只有空列表。我需要看哪里？当我在循环中执行 path=myDFS... 时，我至少有最后一条路径。我试过 path+=myDFS 没有成功。该图是成功创建的，因此它不是来自它。谢谢

问题是：一个人正在二维数组中寻找目标（标记为 9），其中 0 代表墙壁，1 代表道路。该方法应该确定该人是否可以找到目标。

我很容易想出了使用 DFS 的解决方案，但在尝试找出代码的时间和空间复杂度时遇到了困难。

public boolean find(int[][] grid) {
    if(grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == 0) return 0;
    return helper(grid,0,0);    
}

private boolean helper(int[][] grid,int x, int y) {
    if(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
        if(grid[x][y] == 0) return false;
        else if(grid[x][y] == 9) return true;
        else if(grid[x][y] == 1) {
            grid[x][y]=2;
            return helper(grid,x,y-1) || helper(grid,x+1,y) || helper(grid,x,y+1) …

所以我目前正在研究一个单词梯子问题的项目，我已经构建了用于存储所有字典单词的图表并在其中添加了边，我使用 boost 图库完成了此操作。

但令我困惑的是该breadth_first_search()函数，似乎参数只采用起始顶点，但没有结束顶点。

我检查了文档并注意到我可以为该搜索功能定义 BFS 访问者，但由于我是 boost 库的新手，我无法弄清楚它是如何工作的。

谁能解释如何实现寻找两个顶点之间的最短路径？我正在使用无向且未加权的图。

#include <iostream> // std::cout
#include <fstream>
#include <string>
#include <stdlib.h>
#include <utility> // std::pair
#include "headers.h"
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace std;

//Define a class that has the data you want to associate to every vertex and 
edge
//struct Vertex{ int foo;}
//  struct Edge{std::string blah;}

struct VertexProperties {
  string name;
  VertexProperties(string name) : name(name) {}
};

//typedef property<edge_weight_t, int> EdgeWeightProperty;
//typedef property<vertex_name_t, string> VertexNameProperty; …

我很难找到有关如何在scipy 中使用和获取各种搜索算法的路径的教程/示例。

google 中最常见的就是这个例子，在这个例子的末尾有一些错误，带括号。

from scipy.sparse.csgraph import dijkstra
distances, predecessors = dijkstra(graph, indices = i1, return_predecessors = True)
path = []
i = i2

while i != i1:
   path.append(word_list[i])
   i = predecessors[i]

path.append(word_list[i1])
print path[::-1]i2]

我没有输入，所以我无法复制它，但我认为只需删除 i2] 即可。

我的主要问题是如何搜索计算所有索引的图形，而不是给出它indices=i1，这是一个可选参数。同样，如何使用 Floyd-Warshall 方法并获取从任何i,j索引到任何其他i,j索引的路径。我的部分困惑是缺乏对前辈矩阵真正是什么以及如何解析它的描述。

有没有更详尽的教程，或者有人可以举一些简单的例子来梳理和理解吗？

假设图G是有向无环图,其中'n'没有顶点.如果我从图表中删除所有边缘并使其完全断开,这会是DAG吗？

我怎样才能找出导致equals()返回false的原因？

我不是在问一个确定的方法,总是正确的方法,而是一些有助于开发过程的东西.目前我必须进入equals()调用(通常是它们的树),直到其中一个为假,然后进入它,令人作呕.

我想过使用对象图,将其输出到xml并比较两个对象.但是,XMLEncoder需要默认构造函数,jibx需要预编译,x-stream和简单的api不在我的项目中使用.我不介意将一个类,甚至一个包复制到我的测试区域并在那里使用它,但导入整个jar只是不会发生.

我还想过自己构建一个对象图遍历器,我可能仍然会这样做,但我不想开始处理特殊情况(有序集合,非有序集合,映射......)

知道如何去做吗？

编辑:我知道添加罐子是正常的做事方式.我知道罐子是可重复使用的单位.然而,(在我的项目中)所需的官僚机构并不能证明结果是合理的 - 我会继续进行调试和踩踏.

我必须创建一个方法来创建一个包含图形中所有路径的列表.我的图形只有一个起始节点和一个结束节点.每个节点都有一个列表,其子列表和其父节点列表.我必须制作另一个包含所有路径的列表(每个路径都在另一个列表中)

有什么建议??

我正在尝试使用递归打印字符串的所有排列，如下所示。但是我想知道我们是否也可以使用bfs或dfs来执行此操作，我是否认为正确？

如果是，那么您能给我个主意吗？我的想法是：如果string =“ abcd”，则开始节点：'a'结束节点：'d'中间节点：'b'和'c'

然后我们可以将起始节点更改为“ b”，“ c”和“ d”。

我很难将其可视化以放入算法中。

#include <stdio.h>

void swap(char *s, int i, int j)
{
    char temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}

void foo(char *s, int j, int len)
{
    int i;
    if (j == len-1) {
        printf("%s\n", s);
        return;
    }
    for (i=j;i<len;i++) {
        swap(s, i, j);
        foo(s, j+1, len);
        swap(s, i, j);
    }
}

int main()
{
    char s[] = "abc";
    foo(s, 0, strlen(s));
}

根据Serge Rogatch给出的逻辑，可以解决以下问题：

def swap_two(s, i, j): …