圖及其表示

圖是一種非線性資料結構。它使用節點表示資料，使用邊表示它們之間的關係。一個圖G有兩個部分：頂點和邊。頂點用集合V表示，邊用集合E表示。所以圖的表示法是G(V,E)。讓我們看一個例子來了解一下。

在這個圖中，有五個頂點和五條邊。這些邊是有向的。例如，如果我們選擇連線頂點B和D的邊，則源頂點是B，目標頂點是D。所以我們可以從B移動到D，但不能從D移動到B。

圖是非線性的，它沒有規則的結構。為了在記憶體中表示圖，有幾種不同的方式。這些方式包括：

• 鄰接矩陣表示
• 邊表表示
• 鄰接表表示

鄰接矩陣表示

我們可以使用鄰接矩陣來表示圖。給定的矩陣是一個鄰接矩陣。它是一個二進位制方陣，如果從第i行到第j列存在一條邊，則該位置標記為1。當我們嘗試使用鄰接矩陣表示無向圖時，矩陣將是對稱的。

邊表表示

圖也可以使用一維陣列表示。這稱為邊表。在這種表示中，存在五條邊，對於每條邊，第一個元素是源，第二個元素是目標。對於無向圖表示，邊表中的元素數量將加倍。

鄰接表表示

這是另一種圖表示型別。它被稱為鄰接表。這種表示基於連結串列。在這種方法中，每個節點都包含一個節點列表，這些節點直接與該頂點連線。在列表的末尾，每個節點都連線到空值，以指示它是該列表的末尾節點。

Arnab Chakraborty

更新於：2019年8月5日

7K+ 次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始