假设我们正在遍历图表并希望快速确定之前是否已经看过某个节点.我们有一些先决条件.

1. 节点已标记为整数值1..N
2. 使用具有邻接列表的节点来实现图
3. 1..N中的每个整数值都出现在图中,其大小为N.

以纯函数方式执行此操作的任何想法？(不允许使用哈希表或数组).

我想要一个包含两个函数的数据结构; 添加(添加遇到的整数)和查找(检查是否添加了整数).两者都应该优选地将O(n)时间摊销以进行N次重复.

这可能吗？

我的算法类中的一个任务是设计一个穷举搜索算法来解决集团问题.也就是说,给定大小为n的图,该算法应该确定是否存在大小为k的完整子图.我想我已经得到了答案,但我不禁想到它可以改进.这就是我所拥有的:

版本1

输入:由数组A [0,... n -1] 表示的图形,要查找的子图形的大小k.

output:如果子图存在则为True,否则为False

算法(类似python的伪代码):

def clique(A, k):
    P = A x A x A //Cartesian product
    for tuple in P:
        if connected(tuple):
            return true
    return false

def connected(tuple):
    unconnected = tuple
    for vertex in tuple:
        for test_vertex in unconnected:
            if vertex is linked to test_vertex:
                remove test_vertex from unconnected
    if unconnected is empty:
        return true
    else:
        return false

版本2

input:大小为n乘n的邻接矩阵,k是要查找的子图的大小

输出:A中大小为k的所有完整子图.

算法(这次是在函数/ …

通过迭代修剪顶点来计算图的k核是很容易的.但是,对于我的应用程序,我希望能够将顶点添加到起始图并获得更新的核心,而无需从头开始重新计算整个k-core.是否有可靠的算法可以利用先前迭代所做的工作？

对于好奇的人来说,k-core被用作集团发现算法中的预处理阶段.任何大小为5的小团体都保证是图形的4核心的一部分.在我的数据集中,4核比整个图要小得多,所以从那里强制它可能是易处理的.增量添加顶点使算法可以使用尽可能小的数据集.我的顶点集是无限的和有序的(素数),但我只关心编号最小的集团.

编辑:

基于akappa的答案更多地考虑它,检测循环的创建确实很关键.在下图中,在添加F之前,2核是空的.添加F不会改变A的程度,但它仍然将A添加到2核.扩展它很容易看到关闭任何大小的循环会导致所有顶点同时加入2核.

添加顶点会对任意距离之外的顶点的核心性产生影响,但这可能会过多地关注最坏情况的行为.

我有一个带有Vertex V和Edge 的无向图E.我正在寻找一种算法来识别该图中的所有循环基础.

我认为Tarjans算法是一个好的开始.但我的参考是关于找到所有周期,而不是周期基(根据定义,它是不能通过其他周期的并集构建的周期).

例如,看看下面的图表:

因此,算法会有所帮助.如果有一个现有的实现(最好是在C#中),那就更好了!

想象一下Git背后的数据结构.它就像一个有条理的持久性数据结构,除了使用散列引用而不是传统的指针.

我需要Git的数据结构,除了没有任何工作树和索引的东西.并且将有数百万个分支机构,每个分支机构跟踪少数其他本地分支机构.提交和合并将在不同的线程上每分钟发生几千次.拉动会每秒发生一次.

在libgit2和jgit之间我可以使用Git的数据存储子系统.

但我使用合适的工具吗？是否有一个具有git功能的数据库,但更快/更多并发/可扩展/更少阻抗不匹配？内存缓存写入非常有用.

任务:

一个协作编辑的游戏.每个玩家都有自己的分支,他们对游戏世界所做的每一项改变都只适用于他们的版本.可信用户将更改合并回"主"分支.数据和源代码通常捆绑在一起,需要相同的分支和合并功能.

我正在根据这张图片进行练习.我发现最大团体大小为4.我对图论的概念有几个问题.

根据定义,clique是一个完整的子图,其中每对顶点都是连接的.这是否意味着,如果我计算3个派系,(3,4,5),(3,4,6),(3,5,6)和(4,5,6)将被视为3个派系？或者我应该省略那些子图,因为它们是4-clique的一部分.

每个图表只有一个最大集团吗？在我的脑海中想象它,我觉得有可能有​​一个以上的最大团.

练习中的一个问题是询问每个具有一个或多个节点的图形是否必须至少有一个集团.是否存在2-clique(只是一个边缘)或者每个集团是否应该形成一个封闭的形状？

我似乎无法画出一个没有3-clique的4-clique的例子,所以可以安全地假设每个4-clique至少有一个3-clique？我将如何更大规模地检查这样的东西？

甲超图是在其中边缘可以连接许多顶点的图的概括.最近我看到很多关于超图(分段,聚类等)的出版物.所以我的问题是:

• 是否存在超图(以及可能的实现)的实际应用,或者这只是工程师无意使用的学术研究？
• 是否存在可用于超图的常用图算法的类似物,如max-flow或Dijkstra？

我对普通图有直觉.例如,图可用于表示贝叶斯网络的传输网络或繁忙规则.但我对超图没有这样的直觉,它们对我来说绝对违反直觉.

给定一般的无向图,我们如何在O(N + M)时间内打印图的所有双连通分量？我知道Tarjan的算法用于输出无向图的所有关节点,但我发现很难扩展算法来打印双连通组件.我尝试搜索谷歌,但我得到的所有结果都不适用于我的测试用例,因为他们错过了算法的边缘情况.

有人可以提供这个问题的工作代码.

Def:双连通组件是一个连接子图,不包含顶点,删除会断开子图.

编辑:我已成功实施了Niklas提供的此链接中所述的算法.现在我有一个不同的问题,我怎样才能找到一个无向图的子图,其中没有边删除会断开子图.请帮我解决这个替代问题.

我正在进行医学图像分割,我想将模糊连通性算法与图形切割相结合,其思路是将图像与模糊连通性分割为背景,前景将用作图形切割算法的接收器和源,是我的代码获取图形切割分割的种子坐标

FC=afc(S,K); %// Absolute FC
u=FC>thresh;
v=FC<thresh;

s=regionprops(u, 'PixelIdxList'); %// listes de pixels de l´objet
t=regionprops(v, 'PixelIdxList'); %// listes de pixels de l´arrière plan
[a,b]=size(s);
[w,c,z]= size(t)

for i=1:a
    for j=1:b
        [y,x] = ind2sub(size(u), s(i,j).PixelIdxList);
    end
end
for k=1:w
    for d=1:c
        [y1,x1] = ind2sub(size(v), t(k,d).PixelIdxList);
    end
end

对于图形切割,我使用了文件交换中的算法

例如,我可以定义

Cs=-log([y x])
Ct=-log([y1 x1])

但问题是如何组合成本函数的信息,如代码源的这一部分

u = double((Cs-Ct) >= 0);
ps = min(Cs, Ct);
pt = ps

它将超过矩阵大小

有一些算法,如Edmond算法或Boruvka算法,它要求程序员创建一个图形,该图形是通过将一些节点收缩到一个节点中,然后再将其扩展回来获得的.

收缩的正式描述如下:

让我们G与顶点的图V和边E.让我们C成为一个连接组件G.G相对于的收缩C被定义为图形V - nodes(C) + C*,其中C*是表示收缩组分的"超级节点".不涉及顶点的边缘C是原样的.C现在连接有端点的边C*.

我不清楚如何使用邻接列表等表示来实现这样的算法原语.

什么是一种优雅而有效的方式来表示图形,以便它们可以签约,同时记住用于扩展它们的相关数据？