标签: graph-algorithm

给定有向图G,边缘颜色为绿色或紫色,G中有顶点S,我必须找到一个算法,找到从G到G中每个顶点的最短路径,这样路径最多包含两个紫色边缘(和绿色)尽可能多的).

在删除所有紫色边缘之后我想到了G上的BFS,并且对于最短路径仍然无穷大的每个顶点,做一些尝试找到它的东西,但是我有点卡住,并且它需要很多运行时间...

还有其他建议吗？

提前致谢

我试图找出4向梯度填充的最佳模型.我的最新型号是这个小提琴:

<svg height="360" width="400" xmlns="http://www.w3.org/2000/svg" version="1.1">
  <defs>
    <clipPath id="C">
      <path d="M 100 200 L 300 58 L 400 250 L 300 341 Z" />
    </clipPath>
    <radialGradient id="G1" cx="50%" cy="50%" r="50%" fx="50%" fy="50%">
      <stop offset="0%"   style="stop-color:rgb(255,0,0);    stop-opacity:1" />
      <stop offset="100%" style="stop-color:rgb(128,128,64); stop-opacity:0" />
    </radialGradient>
    <radialGradient id="G2" cx="50%" cy="50%" r="50%" fx="50%" fy="50%">
      <stop offset="0%"   style="stop-color:rgb(0,255,0);    stop-opacity:1" />
      <stop offset="100%" style="stop-color:rgb(128,128,64); stop-opacity:0" />
    </radialGradient>
    <radialGradient id="G3" cx="50%" cy="50%" r="50%" fx="50%" fy="50%">
      <stop offset="0%"   style="stop-color:rgb(0,0,255);    stop-opacity:1" />
      <stop offset="100%" style="stop-color:rgb(128,128,64); stop-opacity:0" /> …

从这个网站阅读PageRank算法理论后,我想玩它.我试图用Java实现它.我的意思是我想详细使用PageRank(比如赋予不同的权重等).为此,我需要构建超链接矩阵.如果我有100万个节点,那么我的超链接矩阵将是100万x 100万大小,这会导致此异常:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
    at WebGraph.main(WebGraph.java:6)

如何在Java中实现PageRank,有没有办法存储超链接矩阵？

是否有一个实用的算法(非NP-hard)可以将图形切割成两个近似相等的子图形(例如,一个子图形具有40%-50%的顶点),同时证明切割是最小的在两个子图具有近似相同数量的顶点的情况下,可能的切割？

我最近遇到了这个问题，并认为我可以在这里分享，因为我无法得到它。

我们得到一个编号为 1-25 的 5*5 网格，以及一组 5 对点，它们是网格上路径的起点和终点。

现在我们需要为 5 对点找到 5 条对应的路径，这样两条路径不应该重叠。另请注意，仅允许垂直和水平移动。此外，组合的 5 条路径应覆盖整个网格。

例如，我们给出了一对点：

P={1,22},{4,17},{5,18},{9,13},{20,23}

那么对应的路径将是

1. 1-6-11-16-21-22
2. 4-3-2-7-12-17
3. 5-10-15-14-19-18
4. 9-8-13
5. 20-25-24-23

到目前为止我想到的是：也许我可以计算所有点对从源到目标的所有路径，然后检查路径中是否没有公共点。然而，这似乎具有更高的时间复杂度。

谁能提出更好的算法？如果有人可以通过伪代码解释，我会很高兴。谢谢

在实现DFS和BFS时,CLRS作者为每个顶点区分3种颜色 - 灰色,黑色和白色.我知道黑色和白色表示节点是否被访问过.为什么我们需要灰色？

我的猜测是检测周期,但是我们还能检测出只有黑白的周期(即没有灰色)吗？

考虑该图对于应用Dijkstra算法是有效的,即没有负边权重.我很难说服自己Dijkstra的算法只有在每轮选择最小距离节点被提取时才有效.什么构成提取除最小距离节点以外的任何东西的证据都会导致Dijkstra算法的失败？我正在寻找一个好的论点,但欢迎支持的例子.

在无向图 G=(V,E) 中，顶点被着色为红色、黄色或绿色。此外，存在一种将图划分为两个子集的方法，使得 |V1|=|V2| 或 |V1|=|V2|+1 其中以下条件适用：V1 的每个顶点都连接到 V2 的每个顶点，或者 V1 的顶点没有连接到 V2 的顶点。这递归地适用于 V1 和 V2 的所有诱导子图

我可以通过将邻接矩阵与其自身相乘三倍并逐步增加与主对角线的非零条目相对应的节点来找到图中的所有三角形。然后我可以查看三角形的节点是否以正确的方式着色。O(n^~2,8)！但是考虑到图形的独特属性，我想使用分治法找到一个解决方案来找到彩色三角形。这是具有给定属性的示例图。我需要找到粗体三角形： 蓝色框表示分区完全连接，紫色框表示分区之间没有连接

我最近做了一个项目，使用不同的寻路算法解决给定的迷宫。我通过导入黑白迷宫图像，并使每个结点成为节点来做到这一点。我尝试使用 DFS、BFS、Dijkstra 和 A* 解决这个问题，但注意到令人惊讶的是 DFS 给了我最短的运行时间。我的问题是，在完美的迷宫（只有一个解决方案）上使用更高级的算法（例如 Dijkstra 或 A*）是否有意义？还是这些算法只在有多种解决方案的迷宫中才有意义？

我在网上研究了这个，发现很多人喜欢用 A* 来解决这类问题，但我不明白这有什么好处，至少对于一个完美的迷宫。

我一直在研究寄存器分配，并想知道为什么当有更好的方法可以做到时，他们都从实时寄存器列表中构建图表。我认为他们可以做到的方式是当活动寄存器超过可用寄存器的数量时，寄存器可能会溢出。这是一个示例（伪组装）：

## ldi: load immediate
## addr: add registers and store in arg 2
## store: store memory at offset from stack pointer
.text
    main:
        # live registers: {}
        ldi    %t0, 12             # t0 = 12
        # live registers: {t0}
        ldi    %t1, 8              # t1 = 8
        # live registers: {t0, t1}
        addr   %t0, %t1            # t1 = t0 + t1
        # live registers: {t1}
        store  -4(%sp), %t1        # -4(%sp) = t1
        # live registers: {}
        exit

我已经在汇编代码中列出了实时寄存器。现在，所有的教程和文本都从这里构建了干扰图，等等。但不是这样（正如我上面提到的），他们可以查看活动寄存器。例如，如果这是一台单1寄存器机器，那么当活动寄存器是 …