兄赵的无向图连结算法

李瑾 21:17:34
  给一组点和点之间的连结规则
  然后要输出无向图
李瑾 21:20:48
  点是有xy坐标的一组点
  每两点间满足(|x1-x2| <= A && |y1-y2| <= B) 就可以连结
  要连成无向图存储下来
兄赵 21:24:52
  有一个问题,如果有三个点ABC,水平排列
兄赵 21:25:15
  且 AB< AC < 给定的可连接距离
兄赵 21:25:42
  那么是不是A和B、C都应该分别相连
李瑾 21:26:41
  可以先不考虑会出这种情况
兄赵 21:27:07
  要考虑,这个决定我要给出什么样的算法
兄赵 21:27:26
  在图很大的时候,效率完全不一样了
李瑾 21:27:40
  应该说,出这种情况也不认为有什么问题
兄赵 21:27:51
  不是有没有问题
兄赵 21:28:13
  是你的需求里面,是不是需要A既可以直接通B也可以直接通C
兄赵 21:28:15
  如果需要
兄赵 21:28:18
  那是一种算法
兄赵 21:28:20
  如果不需要
兄赵 21:28:26
  那是另外一种算法
李瑾 21:29:26
  说到具体需求的话并不是很严格要连得那么密,可以不需要
兄赵 21:50:11
  考虑第一象限
兄赵 21:50:23
  你刚才给定了A和B两个值嘛
李瑾 21:50:30
  恩
兄赵 21:50:41
  那么可以由勾股定理得到一个距离值
兄赵 21:50:43
  对吧
李瑾 21:51:02
  是的
兄赵 21:51:05
  现在,算每个点到0,0的距离
兄赵 21:51:16
  并按照这个距离从小到大排序
兄赵 21:51:44
  然后从最小的点(最靠近0,0的点)开始健图
兄赵 21:52:43
  向后遍历满足两个距离之差小于那个距离值的点
兄赵 21:54:02
  就是两个点离0,0距离差小于那个可联通距离且两个点的相对距离也小于可联通距离
兄赵 21:54:13
  这样就缩小的搜索范围了
兄赵 21:54:54
  n + nlogn + nlogn
兄赵 21:54:58
  大约是这个
兄赵 21:55:19
  从预处理+排序+健表
李瑾 21:56:43
  也是每个点开始向后遍历吗?
李瑾 21:56:55
  从每个点开始向后遍历?
兄赵 21:57:43
  是的
兄赵 21:57:56
  因为是无向图嘛
李瑾 21:59:44
无向图算法图2
兄赵 22:00:22
  你可以画出很多同心圆
兄赵 22:00:38
  只有一定范围环内的点才被搜索
李瑾 22:00:54
  不明白
兄赵 22:01:50
  。。。。
兄赵 22:02:05
  比如最上面那个点A
兄赵 22:02:25
  点0,0设为0
兄赵 22:02:30
  o点
兄赵 22:02:58
  那么你可以以o为圆心,其他点离o距离为半径,画出好多好多同心圆
李瑾 22:03:04
无向图算法图1
兄赵 22:03:22
  同心的,不会有交点的
李瑾 22:03:32
  所有○圆心都是原点?
兄赵 22:03:42
  恩
兄赵 22:03:55
  这样就会出现好多环了吗
李瑾 22:04:01
  一下子画不出来
李瑾 22:04:05
  恩
兄赵 22:04:18
  那么只有环间距小于某些值的你才搜索
兄赵 22:04:30
  看看是不是他们的相对距离也满足可联通距离
兄赵 22:04:35
  这样就缩小了搜索范围
兄赵 22:04:47
  分治的思想
李瑾 22:07:12
  恩,明白了

2010年1月

标题目录