graph-theory

1热度

1回答

我正在研究基于任务的并行计算，并对旧项目管理问题的变化感兴趣 - 顶点活动（AOV）的关键路径项目网络，如果没有死锁周期，可以使用拓扑排序算法计算。这些活动在关键路径上的总时间是项目的最短完成时间。但是，这是假设我们总是有足够的工人同时完成没有依赖彼此的活动。如果可用的工人（处理器/核心）数量有限，某些活动可能会等待，而不是因为他们所依赖的某些活动尚未完成，而仅仅是因为所有工作人员现在都在忙于其

0热度

1回答

DFS计算关节点的隔离节点

我有一个图形和一个起始节点。当我使用DFS删除图中的所有节点的每个节点时，我想查找有多少节点变得孤立。例如，如果我从固定节点1开始，并删除节点2，我将拥有多少个隔离节点？如果我删除节点3？我知道我可以为所有节点做DFS（每次移除一个不同的节点），但是这样做，我将不得不为每个节点导航一次图形，我想用一次运行来解决它。我已经被告知它有O（| V | * || A |），其中| V | =边的数量，

0热度

1回答

在递归函数中迭代的问题

下面的代码用于根据给定的约束（maxTotalDist和maxDistOutdoors）来查找最短路径。我得到它主要是工作，但我遇到的问题是，即使我能够找到一个路径（在一些给定的问题）。我无法确认，我发现它。例如，如果找到路径，代码中的“visited”列表应该是我获得的完整路径（然后测试路径是否足以成为“最短路径”路径”）。但是，我试图实现的任何打印语句以查看我正在打印的节点是不是正在打印。

1热度

1回答

过滤图中的节点

我想filter的列表，以便我得到的只是有一个连接的节点，无论是直接或间接与候选人 var candidate = 1; var data = [ { source: 1, target: 2 }, // is connected with 1 { source: 2, target: 3 }, // is connected with 1 { source

2热度

2回答

可以多次访问顶点的TSP

我正在寻找解决一个问题，其中我有一个加权有向图，我必须从原点开始，至少访问一次所有顶点并以最短路径返回原点。本质上这将是TSP的一个典型例子，除了我不要有限制，每个顶点只能访问一次。在我的情况下，除了原点以外的任何顶点都可以沿路径访问任意次数，如果这样可以缩短路径的话。因此，例如在包含顶点V1, V2, V3这样的路径将是有效的，因为它是最短的路径图： ORIGIN -> V1 -> V2 ->

-2热度

1回答

在图中计算三角形

我的教授说我应该找到一种方法来查找图中三角形的数量。我有一个问题，我应该使用什么图表，但我的教授建议我必须先找到一种方法来计算图表中的三角形。我已经通过Google进行了搜索，发现有一种计算图中三角形的算法，但我不太了解它，因为我不是ComSci（计算机科学）的学生。而且我还发现我可以通过矩阵来计算三角形的数量。（1/6）（A）^ 3。这是A的痕迹。所以...我现在要问的是在图表中找到三角形数量

0热度

1回答

序言图未找到路径

我有一个通过Prolog程序链接小镇新西兰的问题。我得到了一组数据，这些数据是道路，它们的来往和距离以及距离。我认为第一个问题会很直接，但是我一直把我的头发拉上几个小时，没有运气，我只需要打印出一条可行的路线。为什么下面的解决方案找不到正确的路径？ road('Wellington', 'Palmerston North', '143'). road('Palmerston North', 'W

0热度

1回答

边缘存在（发现如果边缘存在与否）

问题是：您已被给定组成的Ñ节点和中号边缘的无向图。这个图可以由自循环和多个边组成。另外，您还被给予Q查询。对于每个查询，您将获得2个整数A和B。您只需要找到节点A和节点B之间是否存在边缘。如果是，则打印“是”（不含引号），否则打印“否”（不含引号）。我的代码： #include<bits/stdc++.h> #include <iostream> using namespace std;

0热度

1回答

Union-Find如何与图形相关或不同？

我明白，前者是一个data structure而后者则是一个mathematical structure。但是实施时，他们似乎有着许多相同的特征和行为。在不相交集合的每个元素可以被认为是在一个图形的顶点。图中的边代表Union-Find中的一组。审查http://algs4.cs.princeton.edu/15uf/和http://algs4.cs.princeton.edu/42digr

3热度

1回答

先切技术的含义是什么？

M H Alsuwaiyel写的“算法设计技术与分析”第3部分被命名为“First-Cut Techniques”，其中包括贪心法和图遍历。我想知道“先切技术”的含义。我无法通过Google搜索找到它，所以我在此寻求帮助。