看板Programming
标 题Re: [问题] 想请问一个graph的写法
发信站交大资讯次世代BS2 (Wed Jun 6 13:55:34 2007)
转信站ptt!ctu-reader!ctu-peer!news.nctu!news.cis.nctu!BS2
※ 引述《[email protected] (☆杨培安 完美世界☆)》之铭言:
> 我想请问一个graph的演算法
> 就是输入的部份...任意决定现在有几个点
> 然後会自动产生每一个点都可以走的到任意点的graph
既然你只能决定有几个点,不能决定他们的几何位置
那我只要出一种图给你就好
就是节点 1 , 2 , 3 , ... , n 连成一条线,这样就保证任何一点都可以走到任意点
> 例如:我输入 5,可能就会产生
> 3
> /
> 1—5—4
> \
> 2
这一样可以用 1 - 2 - 3 - 4 - 5 一条龙的方式解决。
有没有发现?只是决定有几个点,根本就不可能产生你画的这种图。
总之你没有定义他们的几何位置,那就是各自表述了
就算你有定义了几何位置,那也很简单,我称为flood:
从节点 1 开始,
每一个节点都向附近不受阻挡的各节点(先不管阻挡要怎麽表示)尽量连通
然後用dfs从节点 1 开始走,所有节点都走到,跳出回圈
不然,继续下去,一直到节点 n 为止
--
Opinions : 「大学炸弹客」是谁? : http://blog.bs2.to/post/GOLDMEMBER/9145
Censure : 夏天最「×」的享受 : http://blog.bs2.to/post/GOLDMEMBER/9168
美国战後战斗机发展时程,F-80 - XF-108 : http://blog.bs2.to/post/GOLDMEMBER/8981
The UNIVAC Biblestory : http://blog.bs2.to/post/GOLDMEMBER/9041
The James Bond Superweaponry : http://blog.bs2.to/post/GOLDMEMBER/9002
http://blog.bs2.to/GOLDMEMBER 法外科学暨工程顾问公司
--
▄▄▄▄▄▄▄ ▄▄▄▄ ▄▄▄▄▄▄ <telnet://bbs.cs.nctu.edu.tw>
█▄▄▄▄█ █ ▄▄▄▄▄█ Player: GOLDMEMBER
▄█▄▄▄▄█ ▄▄▄█ █▄▄▄▄▄ From: 218-160-88-100.dynamic.hine
☆ 次世代BS2 ☆ 可申请个人板
150MB 相簿 http://pic.bs2.to 交大资讯人 250MB
1F:→ xcycl:都说是乱数产生 ... 140.116.21.69 06/06 16:29