标签: graph-algorithm

什么是枚举父图的所有子图的有效算法.在我的特定情况下,父图是一个分子图,因此它将被连接,通常包含少于100个顶点.

编辑:我只对连接的子图感兴趣.

我很想知道D3使用什么算法来实现库中的力导向图功能.阅读了Kobourov关于力导向图的历史的总结让我有点困惑的是,库中使用的确切算法或方法(算法/启发式的组合)是什么.

D3 API参考说Barnes-Hut算法用于计算作用于物体的电荷,O(N*log(N))操作.Kobourov的文章提到Quigley-Eades算法和Hu的算法是利用Barnes-Hut的多级算法.其中一个是在D3中以某种方式使用的吗？

API wiki进一步说,Verlet集成用于粒子定位.在源代码中提到高斯-赛德尔算法,该消息又在提到这两个胡锦涛的算法和德威尔的图形布局文件.我想我正在寻找答案的问题是D3使用的"综合"算法; Kobourov的文章列出了几个和D3强制导向的功能似乎并不适合任何一个.

给定n个节点,如果每个节点连接到每个其他节点(除了它自己),则连接数将为n*(n-1)/ 2

如何证明这一点？

这不是一个家庭作业问题.我已经远离CS教科书,并且忘记了如何证明这一点的理论.

我知道Bellman-Ford算法适用于有向图.它是否适用于无向图？似乎使用无向图,它将无法检测周期,因为并行边将被视为周期.这是真的吗？算法可以应用吗？

这个陈述有效吗？

"对于有向图和无向图,邻接列表表示具有所需的特性,即它所需的存储量是O(V + E)."

来源:算法介绍,cormen.

我正在尝试以编程方式计算非常大的电路上的电压变化.

*这个问题似乎可能面向电子产品,但更多的是将算法应用于一组数据.

为了简单起见,
这是一个完整的电路,电压已经计算过:

我原本只给出了电池电压和电阻:

我的问题是并联和串联电路之间的电压计算方式不同.
在SO上提出了一个类似的问题.

一些公式:

When resistors are in parallel:
Rtotal = 1/(1/R1 + 1/R2 + 1/R3 ... + 1/Rn)

When resistors are in series:
Rtotal = R1 + R2 + R3 ... + Rn

欧姆定律:

V = IR
I = V/R
R = V/I

V is voltage (volts)
I is current (amps)
R is resistance(ohms)

我在互联网上找到的每个教程都包括人们在概念上将并联电路分组以获得总电阻,然后使用该电阻来计算串联电阻.

这对于小例子来说很好,但是对于大规模电路来说很难从中推导出算法.

我的问题:
给定一个包含所有完整路径的矩阵,
我有办法计算所有电压降吗？

我目前将系统作为图形数据结构.
所有节点都表示(并且可以通过查找)id号.

所以对于上面的例子,如果我运行遍历,我会得到一个像这样的路径列表:

[[0,1,2,4,0]
,[0,1,3,4,0]]

每个数字都可用于导出实际节点及其相应的数据.我需要对这组数据执行什么样的转换/算法？

电路的某些部分很可能是复合的,而这些复合部分可能会发现它们与其他复合部分并联或串联.

我认为我的问题类似于:http:
//en.wikipedia.org/wiki/Series-parallel_partial_order

我有一个无向的、正加权的、连接的图，带有 verticesV和边E。我也有一个S顶点子集。现在V包含大约 22000 个顶点和E大约 23000 个边，但是对于更大的输入，这些预计会增加到大约 100 万个。S另一方面，通常包含少于 1000 个顶点，并且它们在图中相对靠近。

我想找到 的“中心” S，意思是一个顶点c，V从它到最远顶点的距离S尽可能小。它就像图中心，但仅适用于顶点的子集。[编辑：] 这也是图形上的1 中心问题；更一般的k 中心问题是 NP-hard 问题，但这个问题可能更容易。

有没有一种算法可以有效地找到这个中心？理想情况下，性能仅取决于S及其周围环境，而不取决于整个图。

我想过开始从所有顶点的广度优先搜索s_i的S同时，当一个顶点停止v_i已经被所有遇到的s_i，但是这是不是太有效。在这种情况下它可能是可行的，但感觉可能有更好的方法。

假设我们有一个DIRECTED,WEIGHTED和CYCLIC图表.

假设我们只对总重量小于MAX_WEIGHT的路径感兴趣

找到总重量小于MAX_WEIGHT的两个节点A和B之间的不同路径数量的最合适(或任何)算法是什么？

PS:这不是我的功课.只是个人的非商业项目.

我正在使用Python的瑞士锦标赛系统,我正试图找出一个最佳的配对算法.
我最大的问题是我所带来的每个算法都会在几个序列中产生错误,其中最后一对被拾取的对象已经相互发挥作用,判断配对无效.

我正在研究的瑞士系统很简单:即使是玩家,每个人都会在每一轮比赛中进行比赛,并且基于胜利的接近度来完成配对(因此强大的球员与强大的球员对抗,弱对弱者).
没有再见,只有输赢(没有平局),对手不能互相打两次.

我目前的算法如下工作:

1. 按排名顺序制作球员名单(大多数胜利至最少胜利)
2. 选择球员,从拥有最多胜利的球员开始
3. 将他与排名最靠近的球员相匹配.如果他们已经玩过,请将他与下一个匹配,直到找到匹配为止
4. 将该对弹出列表并返回1

例如:
2轮后的排名:

1. P1: [P2 win, P3 win] 2 wins
2. P5: [P6 win, P2 win] 2 wins
3. P3: [P4 win, P1 lost] 1 win, 1 loss
4. P4: [P6 win, P3 lost] 1 win, 1 loss
5. P2: [P1 lost, P5 lost] 2 losses
6. P6: [P5 lost, P4 lost] 2 losses

第一个选择是P1,第一个匹配是P5.将(P1,P5)从列表中取出.

1. P3: [P4 win, P1 lost] 1 win, 1 loss
2. P4: [P6 win, P3 lost] …

我需要一些有关 BFS 字链的作业的帮助。词链基于五个字母的词，当词 x 的最后四个字母在词 y 中时，两个词相连。例如，climb 和 blimp 是相连的，因为climb 中的 l、i、m 和 b 在单词 blimp 中。

建议使用来自 Sedgewick 算法第 4 版的定向 BFS 或对其进行修改。代码可以在这里找到：https : //algs4.cs.princeton.edu/40graphs/并使用以下代码读取数据文件以列出单词：

BufferedReader r =
    new BufferedReader(new InputStreamReader(new FileInputStream(fnam)));
ArrayList<String> words = new ArrayList<String>();
while (true) {
    String word = r.readLine();
    if (word == null) { break; }
    assert word.length() == 5;  // inputcheck, if you run with assertions
    words.add(word);
}

以及从文件中读取测试用例的以下代码：

BufferedReader r = 
    new BufferedReader(new InputStreamReader(new FileInputStream(fnam)));
while (true) {
    String line …