Digraph弧列表實現

Question

我想實現圖作爲弧列表，雖然這種實現工作效率是可怕的，我錯過了什麼讓它如此緩慢？時間是衡量從每個節點到/到每個節點的弧的平均值。

​​

Answer 1

那麼，你的實現是最糟糕的可能性：爲了找到進/出邊緣，你已經遍歷整個圖。

你真的需要一個弧列表嗎？通常一個鄰接表更有效率。

一個簡單的鄰接表實現將保持一個vector> arcs，其中arc的大小是節點的數量。

給定一個節點u，arcs [u]給出所有的邊。你可以弄清楚如何在邊緣上優化它。