圖的表示

圖的表示是指用於將某些圖儲存到計算機記憶體中的技術。

有兩種方法可以將圖儲存到計算機的記憶體中。在本教學的這一部分中，將詳細討論它們。

1. 順序表示

在順序表示中，使用鄰接矩陣來儲存由頂點和邊表示的對映。在鄰接矩陣中，行和列由圖頂點表示。 具有n個頂點的圖將具有尺寸n×n。

如果在Vi和Vj之間存在邊緣，則無向圖G的鄰接矩陣表示中的專案Mij將為1。

無向圖及其鄰接矩陣表示如下圖所示。

在上圖中，可以看到頂點(A，B，C，D，E)之間的對映是通過使用也在圖中示出的鄰接矩陣來表示的。

對於有向圖和無向圖存在不同的鄰接矩陣。 在有向圖中，只有當存在從Vi指向Vj的邊時，條目Aij才為1。

有向圖及其鄰接矩陣表示如下圖所示。

權重有向圖的表示是不同的。 不是通過1填充條目，而是通過各個邊的權重來表示鄰接矩陣的非零條目。

權重有向圖以及鄰接矩陣表示如下圖所示。

2. 連結表示

在連結表示中，鄰接列表用於將圖儲存到計算機的記憶體中。考慮下圖中顯示的無向圖並檢查鄰接列表表示。

要為圖中存在的每個節點維護鄰接列表，鄰接列表將節點值和指向下一個相鄰節點的指標儲存到相應節點。 如果遍歷所有相鄰節點，則將NULL儲存在列表的最後一個節點的指標欄位中。 鄰接列表的長度之和等於無向圖中存在的邊數的兩倍。

考慮下圖中顯示的有向圖，並檢視圖的鄰接列表表示。

在有向圖中，所有鄰接列表的長度之和等於圖中存在的邊的數量。

在加權有向圖的情況下，每個節點包含一個額外的欄位，稱為節點的權重。 有向圖的鄰接列表表示如下圖所示。