如何使用鄰接表/集來實現圖。它是如何工作的有向圖？無向圖？加權圖？

Question

您可以給我一些線索，說明如何使用鄰接列表/集來實現一個圖，以及它對 有向圖的工作方式如何？無向圖？加權圖？

Answer 1

考慮向無環圖是這樣的：

1->2 
1->3 
2->4 
2->5 
3->6 
3->7 

另一種方式來查看它是：

 1 
    / \ 
    2  3 
/ \ / \ 
4  5 6  7 

這真的只是一個小的二叉樹。鄰接列表表示如下：

1 -> {2, 3} 
2 -> {4, 5} 
3 -> {6, 7} 

因此，請考慮這可能是指向整數集的整數HashMap。

現在考慮原始圖是無向的，換句話說就是有父指針。

1<->2 
1<->3 
2<->4 
2<->5 
3<->6 
3<->7 

現在表示需要更多的條目：

1 -> {2, 3} 
2 -> {1, 4, 5} 
3 -> {1, 6, 7} 
4 -> {2} 
5 -> {2} 
6 -> {3} 
7 -> {3} 

允許返回圖表和重量的定向版本吧：

權重是元組的第一項和孩子是第二個入口。所以它看起來像
Parent->(Weight, Child)。

1->(.9,2) 
1->(.1,3) 
2->(.9,4) 
2->(.1,5) 
3->(.5,6) 
3->(.5,7) 

因此90％的時間，我們從1->2那麼，我們是在2，我們會去2->4 90％的時間去。

的表示可以看起來非常相似，有向圖：

1 -> {(.9,2), (.1,3)} 
2 -> {(.9,4), (.1,5)} 
3 -> {(.5,6), (.5,7)} 

希望這有助於。