统计
  • 文章总数:662 篇
  • 评论总数:0 条
  • 分类总数:13 个
  • 最后更新:2月17日

arcpy项目-利用krusal最小树方法生成最小树

本文阅读 2 分钟
首页 ArcGIS 正文

arcpy888.png


【需求】将两两生成的最短路径生成最小树

【分析】根据最小树的原理编写程序,利用图来生成最小树

#! /usr/bin/env python

#coding:utf-8


#以全局变量X定义节点集合,即类似{'A':'A','B':'B','C':'C','D':'D'},如果A、B两点联通,则会更改为{'A':'B','B':'B",...},即任何两点联通之后,两点的值value将相同。


X = dict()


#各点的初始等级均为0,如果被做为连接的的末端,则增加1


R = dict()


#设置X R的初始值


def make_set(point):

X[point] = point

R[point] = 0


#节点的联通分量


def find(point):

if X[point] != point:

X[point] = find(X[point])

return X[point]


#连接两个分量(节点)


def merge(point1,point2):

r1 = find(point1)

r2 = find(point2)

if r1 != r2:

if R[r1] > R[r2]:

X[r2] = r1

else:

X[r1] = r2

if R[r1] == R[r2]: R[r2] += 1


#KRUSKAL算法实现


def kruskal(graph):

for vertice in graph['vertices']:

make_set(vertice)


minu_tree = set()


edges = list(graph['edges'])

edges.sort() #按照边长从小到达排序

for edge in edges:

weight, vertice1, vertice2 = edge

if find(vertice1) != find(vertice2):

merge(vertice1, vertice2)

minu_tree.add(edge)

return minu_tree



if __name__=="__main__":


graph = {

'vertices': ['A', 'B', 'C', 'D', 'E', 'F'],

'edges': set([

(1, 'A', 'B'),

(5, 'A', 'C'),

(3, 'A', 'D'),

(4, 'B', 'C'),

(2, 'B', 'D'),

(1, 'C', 'D'),

])

}


result = kruskal(graph)

print result

网上已经有许多关于最小树算法,大多都是通过类来定义,通过图这一数据结构来解决,因为之前对图的数据结构不太了解,所以现在还在苦啃数据结构一书,希望能有所突破

本文来自投稿,不代表本站立场,如若转载,请注明出处:
CAD快捷键命令大汇总
« 上一篇 04-07
利用arcpy将文件夹中所有栅格文件转化为矢量文件
下一篇 » 04-10

作者信息

作者有点忙,还没写简介
TA的最新作品
    请设置要调用的作者ID

动态快讯

    请配置好页面缩略名选项

热门文章

标签TAG

没有任何标签