标签: prims-algorithm

我直观地认为,如果使用Prim的算法来查找图的最小生成树,那么选择哪个根节点无​​关紧要 - 结果MST将具有相同的权重.它是否正确？

我正在使用Prim的算法来创建一个迷宫.我已经成功地完成了这项任务,但我现在正试图通过改变选择潜在细胞添加到迷宫中的方式来"变得更难".在我看来,"艰难"介于两个极端之间:

极端#1是潜在通道列表中完全随机选择的细胞,其中每个分支以大致相等的速度发展.这有很多不同的分支,但是一旦你到达原点,你几乎可以沿着一条直线前往所需的位置.这是一张显示这种方法的图片:

极端#2是选择添加到列表中的最后一个东西,创建一个漫长,乏味,简单的迷宫.当您仅选择放入潜在通道列表中的最后一个项目时,就会形成它.这是一张显示这种方法的图片:

我试图通过优先放置最近放置的细胞来平衡这一点,但是很难创建分支,如第一个所示,但仍然有一条引导整个迷宫的路径.

尝试这样做的最有趣的方式是当我试图将最后一个块添加的概率提高50%,然后如果那个失败则有50%的几率,等等.但是,我把它搞砸了,并试图先做[-0]的索引,使第一个块的概率增加50%,然后是最后一个,然后是最后一个,依此类推.这创造了一个有趣的迷宫,但当我"固定"它时,迷宫看起来很像第二个极端.

我尝试的另一种方法是我的代码中使用的方法:

for i in range(1, len(potential_passage_list) + 1):
        if randint(0, int(len(passage_list) / 50)) == 0:
            maze_passage(potential_passage_list[-i][0], potential_passage_list[-i][1])

这是尝试并且有可能在之前添加到potential_passage_list中的块被放置.

所以,我的问题是,你怎么能创造一个'硬'迷宫,包含许多分支,但是不可预测的模式？可以用什么算法来做到这一点？

我正在使用python 3和pygame库来显示所有内容.

这是我的代码,如果你能理解它:

import pygame
from random import shuffle, randint

# variables
######
# changeable variables
cell_size = 7  # cannot be less than 3
maze_length = 160 * cell_size + 1
maze_height = 100 * cell_size + 1
######

# colours
black = (0, 0, 0)
white = (245, 245, 245)
red = (255, 0, …

我使用的是邻接矩阵,优先级队列是数据结构.

根据我的计算,复杂性是V^3 log V:

• 循环: V
• 检查相邻的顶点: V
• 如果条目已存在则检查队列,并更新相同的队列: V log v

但是,我到处都读到复杂性 V^2

请解释.

"因此,Prim算法的总时间为O(V lg V + E lg V)= O(E lg V),这与我们实施Kruskal算法的渐近相同."

来自http://serverbob.3x.ro/IA/DDU0137.html

但为什么O(V lg V + E lg V)= O(E lg V)？

是因为E至少是V-1？

对于我过去一直努力完成的编程课,我有这个问题......而且我不知道该怎么做.

我理解Prim算法的基本概念:

1. Start at an arbitrary node (the first node will do) and 
add all of its links onto a list.  

2. Add the smallest link (which doesn't duplicate an existing path) 
in the MST, to the    Minimum Spanning Tree.  
Remove this link from the list.  

3. Add all of the links from the newly linked node onto the list

4. repeat steps 2 & 3 until MST is achieved 
(there are no nodes left unconnected).  

我已经获得了一个Graph(使用邻接列表)的实现来实现Prim的算法.问题是我真的不了解实施.到目前为止,我对实施的理解如下:

作为邻接列表,我们拥有数组形式的所有节点:链接到此是一个链接列表,包含权重,目标和指向特定节点其余链接的指针的详细信息:

看起来有点像这样的东西: …

我想知道dijkstra和prim的算法,当他们在多个顶点之间进行选择时会发生什么,并且有多个顶点具有相同的权重.

例如

示例图像http://img688.imageshack.us/img688/7613/exampleu.jpg

时间的复杂性普里姆的MST算法是O(|V|^2),如果你使用邻接矩阵表示.

我试图使用邻接矩阵实现Prim的算法.我用它 作为参考.

V = {1,2...,n}
U = {1}
T = NULL
while V != U:

     /* 
         Now this implementation means that 
         I find lowest cost edge in O(n).
         How do I do that using adjacency list? 
     */

     let (u, v) be the lowest cost edge 
                such that u is in U and v is in V - U;

     T = T + {(u,v)}
     U = U + {v}

编辑:

1. 我非常了解Prim的算法.
2. 我知道如何使用堆和优先级队列有效地实现它.
3. 我也知道更好的算法.
4. 我想使用图的邻接矩阵表示并得到O(| V …

我可以编写Prim和Kruskal的算法来找到C++或Java中的最小生成树,但我想知道如何在Haskell中使用O(mlogm)或O(mlogn)实现它们(纯函数式程序更好).非常感谢.

所以我需要一些帮助来找到最小生成树的方法.假设我有一个邻接列表形式的图表:

A 2 B 12 I 25
B 3 C 10 H 40 I 8
C 2 D 18 G 55
D 1 E 44
E 2 F 60 G 38
F 0
G 1 H 35
H 1 I 35

第一个字母告诉您正在查看哪个节点,该数字表示与其他任何节点的连接数.例如,A有两个连接 - 一个连接到B和I.之后,字母后面的数字只表示边的权重.B的重量为12,我的重量为25.所以我原计划将这整个事物表示为一个名为String的数组Graph[8].每一行都是数组中的不同插槽.我无法通过Prims或Kruskalls算法找出如何实现这一目标.

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

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

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

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