回 帖 发 新 帖 刷新版面

主题:一笔画

输入:网络G的邻接矩阵
输出:
(1):G能否一笔画;
----------------如果(1)成立----------------
(2):G的一笔画路径是否封闭(回到起点);
(3):G得一笔画路径。
(假定:网络中没有端点相同而弧不同的弧
如下图:
              A
         (m) / \ (n)
             \ /
              B
改为

              A
             / \
            C   D     
             \ /
              B
)。

回复列表 (共4个回复)

沙发

图的遍历?

板凳


3 楼

本人也是初学

4 楼

图的一笔画问题:
直接开个数组统计每个点出现的次数
举例:1与2有连边,则c[1]:=c[1]+1    c[2]:=c[2]+1   (当然这要在确定没有重边的情况下)
然后统计数组里某个点i它对应的c[i]的奇偶性(这里统一把c[i]是奇数的叫做奇点,c[i]是偶数的叫做偶点),如果这个图没有奇点或者有2个奇点,那它就可以一笔画,否则不行(当然每个c[i]都不为0才行,这样就保证了它是连通图)没有奇点的可以回到原点,2个奇点的不行。

路径就简单了,2个奇点的必定从一个奇点出发,从另一个奇点结束,没奇点的随便从哪个点出发都OK。深搜就行了。。。

以上。。。

我来回复

您尚未登录,请登录后再回复。点此登录或注册