标签: graph-algorithm

我的问题与将任何正整数转换为RGB值的算法有关但实际上它不是同一个问题 - 那个人主要是数据规范化问题,实际上我有更多的审美颜色选择问题.

我有一堆介于-1.0和+1.0之间的数字.我需要创建一个叠加文本的热图.

使用PHP的最简单方法是将每个数字转换为HTML颜色(#rrggbb),这样生成的颜色不仅直观地与温度相关(即最冷的最热,最热的最红,最流畅的一些)两者之间的过渡)但它也适合作为黑色文本的背景颜色？

确定无向图是否为树的最佳算法的时间复杂度是多少？

我们可以说Big-oh(n),有n个顶点吗？

我必须进行一个不知情的搜索(广度优先搜索)程序,它接受两个节点并返回它们之间的所有路径.

public void BFS(Nod start, Nod end) {
            Queue<Nod> queue = new Queue<Nod>();
            queue.Enqueue(start);
            while (queue.Count != 0)
            {
                Nod u = queue.Dequeue();
                if (u == end)  break;
                else
                {
                    u.data = "Visited";
                    foreach (Edge edge in u.getChildren())
                    {
                        if (edge.getEnd().data == "")
                        {
                            edge.getEnd().data = "Visited";
                            if (edge.getEnd() != end)
                            {
                                edge.getEnd().setParent(u);
                            }
                            else
                            {
                                edge.getEnd().setParent(u);
                                cost = 0; 
                                PrintPath(edge.getEnd(), true);
                                edge.getEnd().data = "";
                                //return;
                            }
                        }
                        queue.Enqueue(edge.getEnd());
                    }
                }
            }
        }

我的问题是,我只获得两条路径,而不是所有路径,我不知道在我的代码中编辑什么来获取它们.我的问题输入基于这张地图:

对于大学项目,我正在尝试实施Bron-Kerbosch算法,即列出给定图形中的所有最大派系.

我正在尝试实现第一个算法(没有透视),但我的代码在维基百科的例子上测试后没有产生所有答案,到目前为止,我的代码是:

# dealing with a graph as list of lists 
graph = [[0,1,0,0,1,0],[1,0,1,0,1,0],[0,1,0,1,0,0],[0,0,1,0,1,1],[1,1,0,1,0,0],[0,0,0,1,0,0]]


#function determines the neighbors of a given vertex
def N(vertex):
    c = 0
    l = []
    for i in graph[vertex]:
        if i is 1 :
         l.append(c)
        c+=1   
    return l 

#the Bron-Kerbosch recursive algorithm
def bronk(r,p,x):
    if len(p) == 0 and len(x) == 0:
        print r
        return
    for vertex in p:
        r_new = r[::]
        r_new.append(vertex)
        p_new = [val for val in p if …

我知道Prim和Dijkstra算法之间的区别.前者产生MST,而后者产生从源到所有节点的最短路径.在数学上,这些不一样,所以我们不会总是期望这两种算法产生相同的结果.

然而,在尝试不同的例子时,我得到了相同的结果.Prim算法和Dijkstra算法的伪代码看起来非常相似.有人可以给我一个例子,其中Prim产生的MST在用Dijkstra解决时不会获得,反之亦然.

另外,据我所知.这两种算法都使用以下方法.如果我错了,请纠正我:

找到最短的ij,其中i来自已经被包含的集合,j来自尚未包含的集合,然后将j添加到集合中.

我在比赛的某个地方发现了这个问题,但还没有找到解决方案.我正在考虑应用Dijkstra的东西,但不是很清楚:

''您将获得一个城市的加权连通图,其中所有边都具有正权重.一些城市(节点)有汽油泵,而有些城市没有.你有一辆坦克容量为C的自行车.也就是说,有了满箱,汽车可以行驶C单位的距离.在任何有汽油泵的城市,汽车都可以将其油箱装满.找出给定源和给定目标之间的最短路径.假设你从一个满罐开始.''

我有一种感觉O(mn logn)将被它接受.

我试图在考虑其成本的情况下在多边形内找到路径.

在我的具体情况下,我有一个角色应该只是相对直的,也就是说它不应该相差几度,不能移动到北,东,南或西.

理想情况下,我会指定一个随偏差而增加的成本.我假设这是一个图论相关的问题,但我不知道如何在多边形中做到这一点......

插图中的红色虚线路径是常规算法产生的; 绿色是我想要的.编辑:我把图片弄乱了一点; 澄清:红色路径是多边形内部最短的路径,我希望绿色路径是角度约束下可能的最短路径.

(为了澄清,如果我的多边形看起来像 (1),我希望路径是这样的 (2),而不仅仅是点之间的直线)

(1)   ,-------------------+      (2)   ,-------------------+
     /               (B)  |           /               (B)  |
    /                     |          /                /    |
+--+                      |  ->  +--+                /     |
|                       +-+      |                  /    +-+
| (A)                   |        | (A)-------------+     |
+-----------------------+        +-----------------------+

我有一群人,他们每个人都有朋友名单和敌人名单.我想把它们排成一行(桌子上没有圆圈),所以没有敌人,只有朋友彼此相邻.

输入示例:https://gist.github.com/solars/53a132e34688cc5f396c

我想我需要使用图形着色来解决这个问题,但我不确定如何 - 我想我必须省略朋友(或敌人)列表以使其更容易并映射到图表.

有谁知道如何解决这些问题,并告诉我,如果我走在正确的道路上？

代码示例或在线示例也不错,我不介意编程语言,我通常使用Ruby,Java,Python,Javascript

非常感谢你的帮助!

在一本书中指出"Dijkstra算法仅适用于有向无环图".

只要没有负循环,该算法似乎适用于具有周期的图形.那是对的吗？

编辑1:书"Grokking Algorithms"-Aditya Bhargava.第7章.第122页.

在阵列A中有N个城市.还有一辆自行车可以在城市之间的最多K个单位旅行.

我们需要回答Q问题.每个查询都具有LR X形式.它询问可从城市X到达的城市数量,这些城市在A中的L和R之间(1 - 索引).每个城市都有一个汽油泵,因此您可以假设燃料在到达时会得到补充.

例:

A = [4,3,1,9,6],K = 2

Q1 = 1 3 6 =>(3)

Q2 = 1 5 3 =>(4)

在Q1,从6号城市出发,您可以前往4号城市,然后前往3号城市,然后前往1号城市.

在第二季度,从3号城市出发,您可以前往9号城市以外的所有城市.

约束:

N <= 10 ^ 5且Q <= 10 ^ 5且K <= 10 ^ 8

我该如何解决这个问题？显然,不可能从每个X执行DFS/BFS,因为它非常昂贵并且会超时.我试着想到Disjoint集合加入彼此距离K的城市,但我对它没有一个非常明确的想法.

任何帮助表示赞赏.谢谢!