标签: graph-algorithm

给定有向图,我可以使用什么算法来找到其边缘的随机子集,以便每个节点只有一个传入边和正好一个传出边？

例如,这可能是我给出的图表:

这将是一个有效的输出图:

这是有效的,因为:

• 它包含输入图上的所有节点
• 它的所有边都在输入图上
• 每个节点只有一个边缘离开它,一个边缘到达它(并且不能是相同的边缘,不允许循环,每个节点必须连接到至少一个其他节点).

如果没有可能的解决方案应该被检测到.

有没有一种有效的算法来解决这个问题？

谢谢!

想知道我们是否可以证明以下内容,或者是否已经证明我可以在哪里获得证据.

令v1,v2,v3 ... vn和t为有向图中的n + 1个顶点.v1,v2,v3 ... vn形式有向无环图.t连接到v1,v2,v3 ... vn的每个人.现在由于v1,v2,v3 ... v4以非循环方式连接,如果有一个循环,那么它将涉及t.我们是否可以证明长度超过3的所有循环总是涉及长度为3的循环.记住t连接到每个v1,v2 ... vn并且没有成对循环.

进一步解释问题.

假设顶点v1,v2,v3..vn的非循环有向图是v1-> v2-> v3 - > ... vn.每个v都有一个t的边.假设有一个周期t-> v1-> v2-> v3-> t.这样的循环似乎肯定涉及长度为3的循环,其为t-> v1-> v2-> t或t-> v2-> v3-> t.但是无法证明这一点.

谢谢

所以,基本上我感觉非常愚蠢,因为这个练习,我花了4到5个小时试图编码,到目前为止我还没有成功.

我已经意识到使用最长路径方法使用树遍历可以更容易地解决这个问题,但是我不确定(你能不能向我证实这一点.),可能是过度杀死因为它应该是这是一个容易出问题的问题,那么请您帮我解决一下如何解决这个问题的一些指导或基本步骤或算法方法？各种帮助当然值得赞赏.

PS.我通常会发布一些关于我到目前为止所做的事情的代码,但我相信到目前为止,一切都是错误的,我宁愿从头开始,至少在想法方面.

谢谢.

根据请求,这里是根据解决练习的接受答案键入的代码:

def get_max_sum(matrix)
  (1...matrix.length).each do |index|  
    flag = 0  
    matrix[index].each_with_index do |e, i|    
      add = (matrix[index-1][flag] > matrix[index-1][flag+1]) ? matrix[index-1][flag] : matrix[index-1][flag+1]
      e += add
      matrix[index][i] = e
      flag = flag + 1
    end    
  end
  matrix[-1][0]
end

矩阵参数是一个数组数组,每个数组代表一个三角形的行.

在下面给出的图中,递归遍历子部分.每个孩子必须报告其直系亲属.问题是孩子[3]必须在同一行同时报告其直接父母(即孩子[2]和孩子[4]).

traverse(Node node)
{
    if(node == null)
        return;

    for(Node child : node.getChilds()) {
        traverse(child);
    }
}

Parent 
|---child[1]
|       child[2]
|           child[3]
|---child[4]
        child[3]

现在我一次遍历一个节点,产生的输出是 -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2]
child[3]  child[4]

预期产量是 -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2], child[4]

搜索节点并为图形生成预期输出的最佳方法是什么？任何帮助,将不胜感激.

(我在这里敲我的头.让X = {x1,x2,...,xn}是一个整数集.让A1,A2,... Am是X的m个子集.对于任何i和j, Ai和Aj不一定是不相交的.现在的目标是有效地找到每个Ai(i = 1,...,m)的最大值,操作次数越少越好.

例如,给定X = {2,4,6,3,1},其子集A1 = {2,3,1},A2 = {2,6,3,1},A3 = {4,2, 3,1}.我们需要分别找到Max {A1},Max {A2},Max {A3}.

查找Max {A1},Max {A2},Max {A3}的强力方法是扫描每个Ai中的所有元素,并且需要(m*d)个操作,m为X的子集数量,和d是X的子集{Ai}的平均长度.

现在,我有一些观察:

(1)对于任何集合Y⊆X,max {Y}≤max{X},

例如,由于Max {X} = 6且6在A2中,因此可以直接找到Max {A2} = 6.

(2)对于任何两个集A和B,如果A∩B非空,则可以如下识别Max {A}和Max {B}:

首先,我们找到A和B之间的公共部分,取而代之的是c = max {A∩B}.

然后,我们发现Max {A} = Max {Max {A-(A∩B)},c}和Max {B} = Max {Max {B-(A∩B)},c}.

我不确定是否还有一些其他有趣的obervations来找到这些最大值.热烈欢迎任何想法!

我的问题是,如果对于一般情况,当X = {x1,x2,...,xn}并且有m个子集X时,表示为A1,A2,... Am,是否有一些更有效的技术可供查找这样的最大值Max {Ai}(i = 1,...,m)？

我们将非常感谢您的帮助!

我有一个连接方块的区域(img在左边),并且想要找到可以装入该区域的最大数量的"双"方块(img在右边).

我的方法是将原始区域表示为图形,其中每个方块表示由边缘连接到下方,上方,左侧和/或右侧的正方形的顶点.

我认为可以通过使用BFS算法,检查每个顶点和应用颜色来完成.但我也觉得可以用动态编程完成......我需要一些帮助!

给出graph G(V,E),无方向图.

|E| = m, |V| = n 

图的数据结构是邻接列表

如何在复杂性中找到并打印简单循环(或打印没有这样的循环)O(n)？
(如果有循环,则输出应该是循环的顶点列表.)

我知道如何找到复杂性的循环O(n),互联网上也有gudies.
我的问题是如何打印它.

这就是我试图做的事情:

DFS-CheckCycle ( Graph G)
{
    p[] <- null //parent array
    foreach v in V
        Color[u] <- white

    foreach v in V
    {
        if (Color[u] = white) 
            Visit(u)
    }
}

Visit(Vertex u)
{
    bool Cycle <- false;
    Color[u] <- gray
    foreach v in Adj[u]
    {
        p[v] <- u
        if (Color[v] = white)
            Visit(v);
        else if (Color[v] = gray) 
        { …

假设您有一个长度为n的垂直游戏板(即空格数).而且你有一个三面骰子可以选择:前进一个,留下并返回一个.如果你低于或高于棋盘游戏空间的数量,这是一个无效的游戏.一旦你到达董事会的最后,唯一有效的举措是"留下来".鉴于精确的掷骰数量t,是否可以通过算法计算出能够赢得比赛的独特骰子数量？

到目前为止,我已经尝试为给定数量的掷骰子生成(-1,0,1)的每个可能组合的列表,并通过列表进行排序,以查看是否有任何累加到板的长度并且还满足所有成为有效游戏的要求.但这对20岁以上的骰子来说是不切实际的.

例如:t = 1,n = 2; 输出= 1 t = 3,n = 2; 输出= 3

求出笛卡尔平面上从(0,0)到(n,n)的路径数,它们永远不会超过y = x线.沿着路径可以进行三种类型的移动:

move up, i.e. from (i, j) to (i, j + 1);
move to the right, i.e. from (i, j) to (i + 1, j);
the right-up move, i.e. from (i, j) to (i + 1, j + 1)

我在它们之间有n顶点和m无向加权边(权重代表分钟).每个顶点包含在该顶点上喝咖啡所需的分钟数.

我想确定时间(分钟)neccessary的最短摆脱顶点v到顶点w但是我必须喝顶点恰好我的一个咖啡对我的方式从另外的约束v来w).

示例:

(顶点中的数字是喝咖啡所需的分钟数,边缘上的重量表示行进此边缘所需的分钟数)

从获取v到w和喝咖啡对你的方式,输出的最小留点时间(输出应为30).

我目前的方法是找到Dijkstra的最短路径(总结该路径上所有边的权重),然后将该路径上具有最低咖啡时间的顶点值添加到我的结果中,以获得总量时间neccessary从中获取v到w.

我的方法不起作用,这是我的方法失败的一个例子(我的方法的结果是12分钟,实际结果应该是6分钟):

如何确定从顶点v到w我需要在路径上喝咖啡的约束的最短时间？