![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
试用有向图描述出以下问题的解法路径: 一个人m带一条狗d,一只猫c,一只兔子r过河,没有船,他每
试用有向图描述出以下问题的解法路径:
一个人m带一条狗d,一只猫c,一只兔子r过河,没有船,他每次游过河时只能带一只动物,而没有人管理时,狗和兔子不能相处,猫和兔子也不能相处,在这些条件约束下,他怎样才能将3只动物从左岸带往右岸?(提示:用结点代表状态,例如初始状态可记为人和兔子过河后的状态可记为< (d,c),(m,r)>,若从状态S1可变为状态S2,则从结点S1画一条弧到结点S2).
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
试用有向图描述出以下问题的解法路径:
一个人m带一条狗d,一只猫c,一只兔子r过河,没有船,他每次游过河时只能带一只动物,而没有人管理时,狗和兔子不能相处,猫和兔子也不能相处,在这些条件约束下,他怎样才能将3只动物从左岸带往右岸?(提示:用结点代表状态,例如初始状态可记为人和兔子过河后的状态可记为< (d,c),(m,r)>,若从状态S1可变为状态S2,则从结点S1画一条弧到结点S2).
有向图可以刻画一个系统的状态转换。例如用图8.17的有向图可以描述接收010*10序列(0*表示任意个0,例如0110,01010,01000010等等)的线路的状态转换,其中S0是初始状态,S6是收到010°10序列后的结束状态,S6是收到非010*10序列后的结束状态。
试用类似方法作出接收01(10)*1序列的状态转换图,这里(10)*表示任意个10(可以一个也没有)。
已知以下的有向图,用Dijkstra算法求出从顶点1出发到各顶点的最短路径(按步给分)。
点到某一指定顶点v的最短路径,例如,对于图8-47(a)所示的带权有向图,用该算法求得的从各顶点到顶点2的最短路径如图8-47(b)所示.
关于最短路径的读法以顶点0为例,在从顶点0到顶点2的最短路径上,顶点0的后继为顶点1(即path[0]=1),顶点1的后继为顶点3(即path[1]=3),顶点3的后继顶点为2(即path[3]=2).
编写一个算法,求解一个带权有向图的单目标最短路径问题。假设图G的顶点数据的类型为char,边上权值的数据类型为float。
图的m着色问题描述如下:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法,使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法.
算法设计:对于给定的无向连通图G和m种不同的颜色,计算图的所有不同的着色法.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n,k和m,表示给定的图G有n个项点和k条边,m种颜色.顶点编号为1,2,...,n接下来的k行中,每行有2个正整数u、v,表示图G的一条边(u,v).
结果输出:将计算的不同的着色方案数输出到文件output.txt.
在以下假设下,重写Djkstra算法:
(1)用邻接表表示有向带权图G,其中每个边结点有3个域:邻接顶点vertex,边上的权值length和边链表的链接指针link
(2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合),利用链表来表示集合T。
试比较新算法与原来的算法,计算时间是快了还是慢了,给出定量的比较。
A.主图所展示的价格或优惠不准确或已过期
B.优惠获取路径描述不明确,例如未标注具体的计算方式
C.主图所展示的价格及优惠获取有条件限制且过于复杂
D.商品主图价格与官方系统计算价格展示不一致时,商家在主图价格旁的横条上展示该价格的计算公式