[理工] 关于Transitive closure的疑问 jojoboy0115 PTT批踢踢实业坊

[理工] 关于Transitive closure的疑问

楼主: jojoboy0115 (jojo) 2019-01-23 14:48:19

https://i.imgur.com/QRxie58.jpg
https://i.imgur.com/y4hIJMG.jpg
为什么这两题的第0次矩阵定义不一样？
一个是离散的，一个是算法/资结的，
神奇的是两个都是用Floyd-Warshall
来求transitive closure。
我以为如果用离散的定义，应该先求出矩阵各个次方后，再联集起来...
还是有什么方法来分辨要用那个定义？

作者: destiny3952 (戴斯泰尼3952) 2019-01-23 16:16:00

算法好像定义对角项是1？

作者: sdfg014025xx (随便就好) 2019-01-23 17:17:00

定义的问题算法对角线定义1 离散0

作者: cvn21 (你是中国人) 2019-01-23 17:30:00

是因为A+还有A*的差异吗？

作者: sooge (老衲) 2019-01-23 17:35:00

求矩阵各次方再加起来不就是在求算法的Floyd Warshall吗你要问的是对角线的问题吧? 不然只是做法不同考算法对角线就设1，考数学就照adjacency matrix算

楼主: jojoboy0115 (jojo) 2019-01-23 19:30:00

是的算法定义对角项都是1感谢 cvn 大提醒所以应该是当题目有特别提到A+就用离散的定义因为成大这题是考在资料结构@@

作者: sooge (老衲) 2019-01-23 19:51:00

竟然是考在资结....

继续阅读

[理工] 作业系统 deadlock avoidance题目susukila [理工] 算法 flow、NPsdfg014025xx [理工] 106中央线代bmpss92196 [理工] 计组 CPI计算jojoboy0115 [理工] 计组 pipeline 问题matt530 [理工] 台大资工102 资演kaidi620 103中兴计组winson910343 [理工] 102台大电机丙计系paralyzation [理工] 中兴104 资概o5739201 [理工] 时间复杂度一题OwTaingJune