[情报] PA3 is_spanning_tree指令

楼主: shefiroth26 (shefiroth)   2013-05-01 19:47:00
is_spanning_tree这指令原本是想设计来让同学有机会
可以互相检查对方的DFS/BFS/MST 的output file是否正确
所以在读入的dot file中 会出现的状况没有特别默认是什么
依照doc内的定义:
Check if the dot file is a spanning tree of the existing graph.
所以同学们至少要check以下的条件
1) tree : 没有 cycle
2) spanning : 包含所有 vertices
3) of the existing graph : spanning tree中edge是原本的graph中的edge
也就是edge的两个端点和weight和原本graph中的一样
助教在这部分会用一些case来测试同学程式的这个指令
当然测试的case会符合dot原本的format,这点请不用担心
作者: SamsungDog (三星王)   2013-05-02 19:12:00
请问第三个条件是什么意思!?
楼主: shefiroth26 (shefiroth)   2013-05-02 21:44:00
换一种叙述方式 这样应该比较好懂
作者: SamsungDog (三星王)   2013-05-02 22:02:00
所以dot_file的edge = 一开始read的graph的edge ?
作者: newacc (XD)   2013-05-02 22:17:00
需要考虑在read_graph前就直接问is_spanning_tree的情况吗

Links booklink

Contact Us: admin [ a t ] ucptt.com