在學最大流時看到了這個東西，感覺名字聽起來很酷，于是就研究了一下。

前向星：一種數據結構，以儲存邊的方式來存儲圖。構造方法如下：讀入每條邊的信息，將邊存放在數組中，把數組中的邊按照起點順序排序(可以使用基數排序，如下面例程)，前向星就構造完了。通常用在點的數目太多，或兩點之間有多條弧的時候。一般在別的數據結構不能使用的時候才考慮用前向星。除了不能直接用起點終點定位以外，前向星幾乎是完美的。【引自百度百科】

鏈式前向星存儲邊的代碼：

void add(int u,int v,int w)?? ?
{?? ?
??? edge[cnt].c= w;?? ?
??? edge[cnt].to = v;?? ?
??? edge[cnt].next = head[u];?? ?
??? head[u] = cnt++;?? ?
}

介紹一下這里面的一些東西：

edge.c——權重

edge.to——這條邊的終點

edge.next——它指向同一起點的上一條邊

那head數組是干啥的呢——head[u]代表以u為起點的邊上一次出現的邊的編號

我們可以使用它進行一個bfs

然后就沒什么好講的了......

轉載于:https://www.cnblogs.com/yzxverygood/p/8417157.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的图的存储之链式前向星的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。