有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?


推薦閱讀:
相關文章