标签: graph-algorithm

我一直在搜索贝尔曼-福特算法的空间复杂度，但在维基百科贝尔曼-福特算法上，它说空间复杂度是 O(V)。在这个链接上它说 O(V^2) 。我的问题是；什么是真正的空间复杂度，为什么？

我正在构建一种算法来计算作为邻接表形式的有向图的 G^2，其中 G^2 = (V,E')，其中 E' 定义为 (u,v)?E ? 如果 G 中的 u 和 v 之间有一条长度为 2 的路径。我很好地理解了这个问题，并找到了一个我认为是正确的算法，但是我的算法的运行时间是 O(VE^2)，其中 V 是数字顶点数，E 是图的边数。我想知道如何在 O(VE) 时间内做到这一点，以使其更有效率？

这是我想出的算法：

在顶点的顶点
的邻居在邻居
的邻居对于n
如果（！N =邻居）
则─>如果（n.value ==邻居）
它添加到一个新的邻接表
中断; // 这意味着我们在顶点和邻居之间找到了一条大小为 2 的路径，
否则继续

我有以下 Tarjan 算法的（递归）实现来查找图中的强连通分量，并且它工作正常：

public class StronglyConnectedComponents
{
    public static List<List<int>> Search(Graph graph)
    {
        StronglyConnectedComponents scc = new StronglyConnectedComponents();
        return scc.Tarjan(graph);
    }

    private int preCount;
    private int[] low;
    private bool[] visited;
    private Graph graph;
    private List<List<int>> stronglyConnectedComponents = new List<List<int>>();
    private Stack<int> stack = new Stack<int>();

    public List<List<int>> Tarjan(Graph graph)
    {
        this.graph = graph;
        low = new int[graph.VertexCount];
        visited = new bool[graph.VertexCount];

        for (int v = 0; v < graph.VertexCount; v++) if (!visited[v]) DFS(v);

        return stronglyConnectedComponents;
    }

    public void DFS(int v) …

从杰夫·埃里克森的讲义上的图形算法，有一个锻炼，以检查是否给定顶点之间的步行路程s，并t可以通过3有向图整除。

我的想法是在图上使用广度优先搜索来获取从s到 的所有路径t。如果简单路径的长度不能被 3 整除，则再次运行该算法以检查循环长度不能被 3 整除的位置s和t位置之间是否存在循环。但是，我觉得该方法非常低效。

如果您对这个问题有任何好的建议，那就太好了。

我想用 Julia 语言编写解决一些图/树问题。这是一些很好的例子。在C中是这样完成的：
Recursive C program for level order traversal of Binary Tree

#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node *left, *right;
};

/* Function prototypes */
void printGivenLevel(struct node* root, int level);
int height(struct node* node);
struct node* newNode(int data);

/* Function to print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
    int h = …

问题陈述：编写一个算法来找到填充完整图片/桶所需的最大笔画数。约束：

1. 一笔可以填充相邻的单元格（左、右、上、下），但不能填充对角线。
2. 给定的是字符串列表，函数应返回填充完整图片/存储桶的最大笔画数的 int 值。

static int fillBucket(List<String> picture){}

 Sample Input: 
    1. picture = ["aaaba", "ababa",a"aaaca"],  Output: 5
    2. picture = ["bbba", "abba", "acaa", "aaac"], Output: 4

存储桶应如何填充的示例：

我有一个无向且连通（不完整）的顶点图，其中u和v可以是任意 2 个不同的顶点。我想构建从顶点u开始，经过v，然后返回到u 的最小权重电路，而不重复任何边。可以通过执行以下操作来完成吗？

1. 找到从u到v 的最短路径- 称之为p1

2. 从图中删除p1的所有组成边

3. 寻找从v到u 的新最短路径- 称之为p2

4. 将所有删除的边返回到图中，并将p1和p2连接在一起 - 称之为c1

考虑到同时通过u和v的约束，c1是可以构造的最小权重电路吗？如果是的话，我该如何证明，如果不是，为什么不呢？