浙江大學-數據結構-小白專場：C語言實現如何建立圖-6.5.5

02-25

用鄰接表表示圖

那麼接下來我們再看怎麼處理用鄰接表表示的圖，所謂鄰接表就是一個指針的數組，這個數組裡的每一個指針，對應一個矩陣每行一個鏈表，只存非0元素，

那這個是鄰接表表示圖的例子，那麼這一串裡頭,拿G[2]來舉例，後面串的這個鏈表就表示，就有一條邊是從2到1，從2到5，從2到4，如果我們在說無向圖的話呢，那麼一條邊會被存兩次，比如說從1到5有一條邊的話，那麼從5到1，也應該有一條邊，那麼當我們在定義這個圖的結點的時候，其實大部分內容都跟前面是一樣的，就是它也得有頂點數，它也得有邊數，然後它這邊有一個pointer,然後把這個鄰接表方式存儲的圖類型定義為指向這個結點的指針，最關鍵的就是定義struct GNode{int Nv; int Ne; AdjList G;}是不一樣的，在前面這一塊的核心是鄰接矩陣，在這裡的核心就應該是鄰接表,那我仍然把這個鄰接表的名字取為G,這個AdjList是這個鄰接表的縮寫，那這個類型是要我們自己去定義的，它實際上是一個數組，

它實際上是一個數組，這個數組的大小就是我們一共有多少個頂點，這個數組就有多大，所以它是MaxVertexNum,它的每一個元素都是一個結點，這個結點我們取名叫Vnode,這個頭結點應該包含什麼東西呢？首先它要包含一個指針，指向這麼一個邊的結點，那麼我們把邊結點指針的類型，定義為PrtToAdjVNode,這個是邊結點的類型，等一下我們再定義，把這個指針我們命名為FirstEdge,也就是第一條邊，當然你可以根據自己的喜好給它取另外的名字，那在這我們把它叫做FirstEdge的原因是說，它總是指向鏈表裡的第一條邊，如果頂點裡面沒有要存其它元素呢，這樣就可以了，如果在有的情況下，每一個頂點還要存一堆亂七八糟的東西的話，那麼這個亂七八糟的東西就把它取一個名字叫Data,存為DataType

那麼跟前面一樣，這個DataType,有可能是整型，有可能是Double類型，也可能複雜一點是一個結構體，接下來我們在來看AdjVNode,就是這個鏈表裡面代表每一條邊的這個結構，他應該包含什麼東西呢？

雖然說它代表的是一條邊，但是它需要存兩個頂點嗎？想一下，好像是不需要的，因為它必定是放在某一個頂點的鏈表裡，那麼這條邊的出發點就已經決定了，它在誰家的鏈表裡，誰就是它的出發點，所以在這條邊的結點裡面，我只需要存它的終點，也就是這個頂點它的鄰接點，所以我們把它取個名字叫鄰接點AdjV,它的類型是鄰接點的下標，Vertex,這個Vertex還向前面一樣把它定義為整型，除此之外，如果我們是在說一個有權圖的話，還得有一個變數來存邊的權重，然後呢，這是鏈表裡的一個結點，所以它還有一個指向下一個結點的指針，

到此為止，我們就完成了用鄰接表表示的這個圖的所有結構的定義，那接下來呢，就是來建立這個圖。