标签: graph-algorithm

我在这里询问了一个最短路径算法: 2D航路点寻路:WP的组合从curLocation到targetLocation

(要了解我的情况,请阅读该问题以及此问题.)

似乎Dijkstra最短路径算法能够做到我需要的.但是,我的路线图中有大约500到1000个节点.

到目前为止,我所看到的实现将节点数限制在50以下.我的问题是:我是否应该使用Dijkstra最短路径算法,还是替代？Java中是否有任何实现？

我有一个无向的加权图,其中任意类型的对象作为节点.两个节点A和B之间的边缘的权重是这两个节点在区间(0,1)中的相似性.相似度0导致节点之间没有连接,因此可以对图形进行分区.

给定目标权重w和起始节点S,起始节点S是用于找到权重> w的所有节点的算法.子节点(从S看)应该具有路径上所有权重的乘积.即:

S --(0.9)-- N1 --(0.9)-- N2 --(0.6) -- N3

从S开始,节点将具有以下相似性值:

N1: 0.9 
N2: 0.9 * 0.9 = 0.81
N3: 0.9 * 0.9 * 0.6 = 0.486

因此,给定S和目标权重0.5,搜索应该返回N1和N3.从N2开始的搜索将返回S,N1和N3.

他们的算法是否符合我的需求？

我不知道这样的事情是否可行,或者在哪里寻找可以帮助解决这个问题的事情 - 因此寻求一些指针的问题.

这是我的情况:我有一个活动图表的矩阵表示.矩阵中的每个条目表示活动对另一个活动的相对影响,即('系统'中有'n'个活动.矩阵只是这些活动的'nxn'表示,条目意味着相对影响)

• 0(无影响)1,2,3(低,中,高)'正'影响,即它们积极(增加)有助于活动
• 负数:-1,-2,-3意味着"负面"影响,即它们负面(减去)贡献

(这些数字是信息性的,可以是任何数字,但只是简化为0-3).

现在给出这个矩阵,我将对图形进行描述.我想做的是随着时间的推移"模拟"图形,即,从时间开始,t=0我希望能够模拟"系统"随时间的变化.我肯定会在图表中有周期(非常可能),因此这里基于时间步的模拟很合适.

我不知道有任何可以帮助我理解循环图随时间变化的影响.我只知道一个这样的解决方案,即使用系统动力学并将此图转换为库存/流程图,然后模拟它以获得我想要的.实际上,图(上图)是因果循环图.

问题:我真的很想从矩阵表示转变为可模拟的系统而不强迫某人理解系统动力学(基本上在后台做一些事情).

问题是:系统动力学是实现我正在寻找的东西的唯一途径吗？我该如何系统地将图形的任意矩阵表示转换为系统动态模型？

如果不是系统动力学,那么我应该考虑哪些其他方法来解决这样的问题？具有相应指针的算法名称将被赞赏!

图表的示例表示:

假设我有3个活动的以下矩阵:行:'原因'的节点(外向箭头)列:节点"受影响"(传入箭头)

__| A | B | C |
A | - | 3 | 2 |
B | 1 | - |-2 |
C |-1 | 0 | - |

如果我'开始'有10个单位的图表(模拟)A我想看看系统如何随着时间的推移而给出矩阵表示中的相对影响.

更新: '模拟'将在一系列时间步骤中,即,在时间t = 0时,节点A的值为10,B将乘以3或加3,这取决于某人想要如何指定'影响".随着时间节点的累计值可以在图形绘制,显示的值是如何进展的趋势.

我有一个有向图,其顶点有成本.我想在两个顶点之间找到最大成本的路径,但我只找到算法以最低的成本解决路径.

另外,我正在使用Java.

所述布隆-Kerbosch算法是用于列出的图表的所有极大派系的方法。我最近只是为了好玩而成功地实现了该算法。缺点是该算法是递归的，因此只能在很小的图上运行，直到堆栈溢出为止。

应该有可能使算法纯粹是迭代的。考虑一下Wikipedia上的基本版本（无限制）。该算法的迭代版本在伪代码中的外观如何？某处有描述吗？

我在想象一个堆栈数据结构来模拟递归。我还应该有一个循环，在其中测试P和X的空度，但是我没有看到完整的答案。

我正在实现Kruskal算法,这是一种众所周知的方法来查找加权图的最小生成树.但是,我正在调整它以在图表中查找周期.这是Kruskal算法的伪代码:

KRUSKAL(G):
1 A = ?
2 foreach v ? G.V:
3    MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ? FIND-SET(v):
6       A = A ? {(u, v)}
7       UNION(u, v)
8 return A

我有一个很难把握FIND-SET()和MAKE-SET()功能,或者它们与并查集的实现.

我当前的代码如下所示:

class edge {
    public:      //for quick access (temp) 
      char leftV;
      char rightV;
      int weight;
};

std::vector<edge> kruskalMST(std::vector<edge> edgeList){
    std::vector<char> set;
    std::vector<edge> result;
    sortList(edgeList);    //sorts according to weight ( passed by reference)
    do{
        if(set.empty()){
            set.push_pack(edgeList[i].leftV); …

我今天在采访中问了这个问题.我告诉他们,它的遍历和DFS可用于查看图表是否已连接.他们说这太简单了.

DFS和BFS有哪些更重要的实际用途？

我目前正在尝试编写一个程序来检查有向图是否是循环的.我不确定我做错了什么(我很可能做错了所以所以请StackOverflow,告诉我我的愚蠢!).我会感谢任何帮助,因为我已经到了不知道可能出现什么问题的地步.

输入是一个邻接列表,例如:

0: 2 4
1: 2 4
2: 3 4
3: 4
4: 0 1 2 3

(0指向2和4; 1指向2和4,依此类推......)

我的想法是检查我正在检查的节点是否为"灰色"(部分探索).如果是,则它必须是后边缘,因此是循环图.始终探索黑色边缘或交叉边缘,因此不应触发循环消息.我的目标是深度搜索

如果A - > B和B - > A,则不应触发有关循环的消息(但A - > B,B - > C,C - > A应该).

hasCycle调用hasCycleInSubgraph,它通过图的Adjency List递归调用自身.

class qs {

    private ArrayList<Integer>[] adjList;

    private Stack<Integer> stack;

    private ArrayList<Integer> whiteHat;
    private ArrayList<Integer> greyHat;
    private ArrayList<Integer> blackHat;

    public qs(ArrayList<Integer>[] graph) {
        this.adjList = graph;

        this.stack = new Stack();

        this.whiteHat = new ArrayList<Integer>();
        this.greyHat = new ArrayList<Integer>(); …

我正在使用图表,最近知道neo4j.

neo4j能帮我找到通过图中给定节点的所有简单循环吗？

通过实施Johnson算法的修改,我已经可以在java/ pythoncode中执行此操作.

这只是我创建的图表的一个示例,是可以在neo4j数据库上执行的Cypher代码:

CREATE (John:Person { name : '@john',facebook: 'facebook.com/john'})
CREATE (Josh:Person { name : '@josh',facebook: 'facebook.com/josh'})
CREATE (Dan:Person { name : '@dan',facebook: 'facebook.com/dan'})
CREATE (Kenny:Person { name : '@kenny',facebook: 'facebook.com/kenny'})
CREATE (Bart:Person { name : '@bart',facebook: 'facebook.com/bart'})
CREATE (Mike:Person { name : '@mike',facebook: 'facebook.com/mike'})
CREATE (Jenny:Person { name : '@jenny',facebook: 'facebook.com/jenny'})
CREATE (Frank:Person { name : '@frank',facebook: 'facebook.com/frank'})
CREATE (Erick:Person { name : '@erick',facebook: 'facebook.com/erick'})
CREATE (Lynda:Person { name : …

假设您正在尝试将由N个组件组成的系统组合在一起.在放入其他组件之前不能放入某些组件(不能在第一层之前建造第二层),并且除非没有放入其他组件,否则无法放入某些组件(不能在关闭墙壁后将绝缘材料放在墙壁上).

在数学上我通过将每个组件表示为位域中的一位来对此进行建模.我从全零开始,我尝试一次翻转一位,并且我有一些评估器功能,它确定该翻转是否是允许的移动.换句话说,我从空集开始,尝试逐个添加N的元素,直到它们都在我的集合中.但是,并非所有此类添加都是允许的.

根据我的数学,对应于上述问题的图将具有2 ^ N个节点,每个步骤S沿着构建过程(因此0 <= S <= N)由N组成!/(S!*(NS)!)节点.所以有N种方法放置第一个组件,(N ^ 2 - N)/ 2种方式放置第二个组件,依此类推.每个节点将具有与其子集N中的元素一样多的父节点,并且节点具有的父节点和子节点的数量将等于N中的元素的数量.

O(2 ^ N)除了非常小的N之外不能解决任何问题,但是我想知道是否有这个问题的名称,以便我可以阅读更多关于它的信息.

(我为我对技术术语的不当使用提前道歉.)