有N个集合,它们彼此之间有连接,可以通过连接取到对方的值,也可以通过连接的连接取到其他的值,当取到自身时停止,直到所有集合的值不再变化为止。

举例:A(a1),B(b1),C(c1). A通过Sab指向B,B通过Sbc指向C,C通过Sca指向A。最后的结果应该是:A(a1, Sab-b1, Sab-Sbc-c1),B(b1, Sbc-c1, Sbc-Sab-b1), C(c1, Sca-a1, Sca-ab-b1)。

当然这是一种简单的环形,复杂一点的情况是有更多的集合,并且有些集合之间有连接,有些没有,有些集合之间是双向连接。这种问题在数学领域属于什么问题?或者用Python该怎么写?


图论。有向图。


图的邻接矩阵,然后矩阵做乘方运算,直到不再变化

也可以是关系矩阵,矩阵的1次方就是单次可达关系,矩阵的2次方就是两次可达关系。


我听著像 有向图和有向网路;

当然有向图和有向网路本身也是和(它们的表示)矩阵这些同构的(可以理解抽象之后是一样的东西);

你只是说了模型,还没说你的问题是什么。你想做什么?


你可以做一个类似链表的东西,把链表的next改成数组,包含所有指向的vertex,进行遍历

BFS,DFS随便吧,遍历的时候维护一个set,如果某条路添加到重复的就剔除这条路,直到没有路可走

想简单搞搞就写个递归,规模太大就自己维护一个递归栈。。


最终想要得到什么?


PageRank?


推荐阅读:
相关文章